187 – Quiz 10

Here is quiz 10. 

Problem 1 asks to solve in the equation . 

This equation is equivalent to Since , there is a such that and multiplying by both sides of gives us . To finish the problem, it then suffices to find . For this, we use the Euclidean algorithm:

Now we work backwards from these equalities:

This means that, in , if we let then

(In effect, because )

And the value of we are looking for is

Problem 2 asks for a solution to the equation in

This can be done by direct computation. We have that 5 and 8 are solutions, since and

Remark: This is related to the fact, that you may have conjectured through the homework, that an odd prime is a sum of two squares iff We have The relation with the problem is that, in this equation becomes

or or where for the such that namely Note that  

Similarly, gives or But where i.e., Note that

Problem 3 asks to find the order of in i.e., the smallest such that

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

This means that

The other way is perhaps less computational, but it requires a bit more theory. Recall form lecture Euler’s theorem stating that if then where is the number of numbers with such that and are relatively prime.

From the formula mentioned in lecture,

This means that is a divisor of 40, so it is one of These are the only powers we need to compute. This is faster than computing all the powers since, for example, We have:

and we have

Advertisement