187 – Quiz 10

Here is quiz 10. 

Problem 1 asks to solve in {\mathbb Z}_{37} the equation 17x+12=5

This equation is equivalent to 17x=-7. Since {\rm gcd}(17,37)=1, there is a b such that 17b=1, and multiplying by b both sides of 17x=-7 gives us x=-7b. To finish the problem, it then suffices to find b. For this, we use the Euclidean algorithm:

37=17\times 2+3.

17=3\times 5+2.

3=2\times 1+1.

Now we work backwards from these equalities:

1=3-2.

1=3-(17-3\times5)=17\times(-1)+3\times6.

1=17\times(-1)+(37-17\times2)\times 6=37\times 6+17\times(-13).

This means that, in {\mathbb Z}_{37}, if we let b=-13=24, then 17\otimes b=1.

(In effect, 17\otimes 24=(408\mod37)=1, because 408=37\times 11+1.)

And the value of x we are looking for is x=-7\otimes(-13)=(91\mod37)=17.

Problem 2 asks for a solution to the equation x^2=-1 in {\mathbb Z}_{13}.

This can be done by direct computation. We have that 5 and 8 are solutions, since 5^2=25\equiv-1\mod13, and 8^2=64\equiv-1\mod13.

Remark: This is related to the fact, that you may have conjectured through the homework, that an odd prime p is a sum of two squares iff p\equiv1\mod4. We have 13=3^2+2^2. The relation with the problem is that, in {\mathbb Z}_{13}, this equation becomes

3^2\oplus2^2=0, or 3^2=-2^2, or (3\oslash2)^2=-1, where 3\oslash2=3\otimes b for the b such that 2b=1, namely b=7. Note that 3\otimes7=8. 

Similarly, 3^2\oplus2^2=0 gives 2^2=-3^2 or (2\oslash3)^2=-1. But 2\oslash3=2\otimes c, where 3\otimes c=1, i.e., c=9. Note that 2\otimes9=5.

Problem 3 asks to find o(3), the order of 3, in {\mathbb Z}_{100}, i.e., the smallest n such that 3^n=1.

 There are two ways of solving this problem. One is to simply write down the powers of 3 until we reach 1:

3,9,27,81,43,29,87,61,83,49,47,41,23,69,7,21,63,89,67,1. This means that o(3)=20.

The other way is perhaps less computational, but it requires a bit more theory. Recall form lecture Euler’s theorem stating that if {\rm gcd}(a,n)=1, then o(a)|\varphi(n), where \varphi(n) is the number of numbers k with 0\le k<n such that k and n are relatively prime.

From the formula mentioned in lecture, \displaystyle \varphi(100)=100\left( 1-\frac12\right)\left(1-\frac15\right)=100\cdot\frac12\cdot\frac45=40.

This means that o(3) is a divisor of 40, so it is one of 1,2,4,5,8,10,20,40. These are the only powers we need to compute. This is faster than computing all the powers since, for example, 3^8=(3^4)^2. We have:

3^1=3, 3^2=9, 3^4=(3^2)^2=81, 3^5=81\otimes3=43, 3^8=(3^4)^2=61, 3^{10}=3^8\otimes3^2=49=50-1, 3^{20}=(50-1)^2=1, and we have o(3)=20.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: