91Ó°ÊÓ

If \(m\) and \(n\) are relatively prime positive integers, prove that $$ m^{\varphi(n)}+n^{\phi(m)} \equiv 1(\bmod m n) $$

Show that there are infinitely many integers \(n\) for which \(\phi(n)\) is a perfect square.

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

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

For any integer \(a\), show that \(a\) and \(a^{4 n+1}\) have the same last digit.

(a) If \(\phi(n) \mid n-1\), prove that \(n\) is a square-free integer. [Hint: Assume that \(n\) has the prime factorization \(n=p_{1}^{k_{1}} p_{2}^{k_{1}} \cdots p_{r}^{k}\), where \(k_{1} \geq 2\). Then \(p_{1} \mid \phi(n)\), whence \(p_{1} \mid n-1\), which leads to a contradiction.] (b) Show that if \(n=2^{k}\) or \(2^{k} 3^{j}\), with \(k\) and \(j\) positive integers, then \(\phi(n) \mid n\).

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]\)

Verify that \(\phi(n) \sigma(n)\) is a perfect square when \(n=63457=23 \cdot 31 \cdot 89\).