0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ No worries; I was half teasing anyway. $\endgroup$ – amWhy Feb 1 '15 at 22:50
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.