# Divisibility and congruence.

How to prove that: $$32 | \phi(51^5) \tag{1}$$ and $$51^{442} \equiv 2 \mod 31\tag{2}$$ Thanks in advance.

## 2 Answers

For the first:
$51 = 3\cdot 17$. Use this to compute $$\phi(51^5) = \phi(3^5 17^5) = 2 \cdot 3^4 \cdot 16 \cdot 17^4 = 2^5 3^4 17^4$$ Can you see now why $32|\phi(51^5)$?
The second one is false: $$51^{442} \equiv 20^{22} \equiv 28^{10}\cdot 28 \equiv 9^4 \cdot 9 \cdot 28 \equiv 19^2 \cdot 4 \equiv 20\cdot 4 \equiv 18 \pmod{31}$$ The algorithm used here is called square-and-multiply in case you want to know how to compute such modular powers efficiently; It should be obvious that $2\not\equiv 18\pmod{31}$. Indeed if you want $$51^k \equiv 2 \pmod{31}$$ You must chose $k$ such that $k\equiv 3\pmod{15}$, because the discrete logarithm and order are $$\log_{51}2 \pmod{30} = 3\\ \mathrm{ord}_{31}(51) = 15$$

• No worries; I was half teasing anyway. – amWhy Feb 1 '15 at 22:50

The first question : $\phi(51^5)=(3^5-3^4)(17^5-17^4)=3^4\times 2\times 17^4\times 16$

The second question : Take the base modulo 31 and the exponent modulo $\phi(31)=30$

The result should be $18$ instead of $2$.