91Ó°ÊÓ

(a) If \(\operatorname{gcd}(a, 35)=1\), show that \(a^{12} \equiv 1(\bmod 35)\). [Hint: From Fermat's theorem \(a^{6} \equiv 1(\bmod 7)\) and \(\left.a^{4}=1(\bmod 5) .\right]\) (b) If \(\operatorname{gcd}(a, 42)=1\), show that \(168=3 \cdot 7 \cdot 8\) divides \(a^{6}-1\). (c) If \(\operatorname{gcd}(a, 133)=\operatorname{gcd}(b, 133)=1\), show that \(133 \mid a^{18}-b^{18}\).

(a) Let \(p\) be a prime and \(\operatorname{gcd}(a, p)=1\). Use Fermat's theorem to verify that \(x \equiv a^{p-2} b\) (mod \(p\) )is a solution of the linear congruence \(a x \equiv b(\bmod p)\). (b) By applying part (a), solve the congruences \(2 x \equiv 1(\bmod 31), 6 x \equiv 5(\) mod 11\()\), and \(3 x \equiv 17(\bmod 29)\)

Using Wilson's theorem, prove that for any odd prime \(p\). $$ 1^{2} \cdot 3^{2} \cdot 5^{2} \cdots(p-2)^{2} \equiv(-1)^{(p+1) / 2} \text { (mod } $$

Show that \(561 \mid 2^{561}-2\) and \(561 \mid 3^{561}-3 .\) It is an unanswered question whether there exist infinitely many composite numbers \(n\) with the property that \(n \mid 2^{n}-2\) and \(n \mid 3^{n}-3 .\)