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