91Ó°ÊÓ

Use Euler's theorem to establish the following: (a) For any integer \(a, a^{37} \equiv a\) (mod 1729\()\). [Hint: \(1729=7 \cdot 13 \cdot 19 .]\) (b) For any integer \(a, a^{13} \equiv a(\bmod 2730)\). [Hint: \(2730=2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 .]\) (c) For any odd integer \(a, a^{33} \equiv a\) (mod 4080 ). \([\) Hint: \(4080=15 \cdot 16 \cdot 17 .]\)

Find the units digit of \(3^{100}\) by means of Euler's theorem.

(a) If \(\operatorname{gcd}(a, n)=1\), show that the linear congruence \(a x \equiv b(\bmod n)\) has the solution \(x \equiv b a^{\phi(n)-1}(\bmod n)\) (b) Use part (a) to solve the linear congruences \(3 x=5(\bmod 26), 13 x \equiv 2(\bmod 40)\), and \(10 x \equiv 21(\bmod 49)\).

For a square-free integer \(n>1\), show that \(\tau\left(n^{2}\right)=n\) if and only if \(n=3\).

Use Euler's theorem to evaluate \(2^{100000}\) (mod 77).

Find all solutions of \(\phi(n)=16\) and \(\phi(n)=24\). [Hint: If \(n=p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{r}^{k_{r}}\) satisfies \(\phi(n)=k\), then \(n=\left[k / \Pi\left(p_{i}-1\right)\right] \Pi p_{i} .\) Thus the integers \(d_{i}=p_{i}-1\) can be determined by the conditions (1) \(d_{i} \mid k\), (2) \(d_{i}+1\) is prime, and (3) \(k / \Pi d_{i}\) contains no prime factor not in \(\left.\Pi p_{i} .\right]\)