How to prove that:
$$32 | \phi(51^5) \tag{1}$$
and
$$51^{442} \equiv 2 \mod 31\tag{2}$$
Thanks in advance.
Answer
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 comments:
Post a Comment