## 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 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.$