Let \(F=\mathbb Z/(179)\).
Prove that \(10\) is not a square in \(F\).
Prove that \(10\) generates the multiplicative group \(F^\times\).
Solution
1. The element \(-1\) is not a square in \(F\).
Suppose for contradiction that \[ y^2=-1 \] for some \(y\in F\). Then \(y\ne0\), so Fermat’s little theorem gives \[ y^{178}=1. \] On the other hand, \[ y^{178} = (y^2)^{89} = (-1)^{89} = -1, \] a contradiction. Thus \(-1\) is not a square.
2. In \(F\),\[ 10=-13^2. \]
One has \[ 13^2=169\equiv-10\pmod{179}. \] Multiplying by \(-1\) gives the claim.
3. The element \(10\) is not a square in \(F\).
1. Hence \(10\) is not a square. This provespart (a).
4. One has\[ 10^{89}=-1 \]in \(F\).
Using step 2, \[ \begin{aligned} 10^{89} &= (-13^2)^{89}\\ &= -13^{178}. \end{aligned} \] Since \(13\ne0\) in \(F\), Fermat’s little theorem gives \[ 13^{178}=1. \] Therefore \[ 10^{89}=-1. \]
5. The multiplicative order of \(10\) in \(F^\times\) is\[ 178. \]
The group \(F^\times\) has \[ 179-1=178=2\cdot89 \] elements. By Lagrange’s theorem, the order of \(10\) divides \(178\), whose positive divisors are \[ 1,\ 2,\ 89,\ 178. \]
The order is not \(1\), since \(10\ne1\). It is not \(2\), since \[ 10^2=100\ne1 \] in \(F\). It is not \(89\) because step 4 gives \[ 10^{89}=-1\ne1. \] Thus the only remaining possibility is order \(178\).
6. Hence \(10\) generates \(F^\times\).
By step 5, the cyclic subgroup generated by \(10\) has \(178\) elements. Since \(F^\times\) itself has \(178\) elements, \[ \langle10\rangle=F^\times. \] This proves part (b).
7. Q.E.D.
Step 3 proves part (a), and step 6 proves part (b).