0
$\begingroup$

I would like to prove it using Euler's Theorem, which states that if $\gcd(a,n)=1$,then $a^{\phi(n)}=1 \pmod{n}$. Then, $480$ should be factored, but I am unsure how to proceed with the proof. Thanks in advance.

$\endgroup$
9
  • $\begingroup$ Did you at least calculate $\phi(480)$? $\endgroup$ – Ben Grossmann Nov 10 '20 at 1:57
  • $\begingroup$ Yes! $\phi(480)=128$, but I do not understand how that helps. $\endgroup$ – qt_314 Nov 10 '20 at 1:59
  • $\begingroup$ @qt_314, s use mathworld.wolfram.com/CarmichaelFunction.html $\endgroup$ – lab bhattacharjee Nov 10 '20 at 2:08
  • $\begingroup$ Same proofs as in the dupe work here. $\endgroup$ – Bill Dubuque Nov 10 '20 at 2:12
  • $\begingroup$ @BillDubuque Thank you so much! I apologize for posting a duplicate question. $\endgroup$ – qt_314 Nov 10 '20 at 2:14
2
$\begingroup$

Hint: $480 = 2^5 \cdot 3 \cdot 5$. By the Chinese remainder theorem, we see that $a^k \equiv 1 \pmod {480}$ if and only if we have $$ \begin{cases} a^k \equiv 1 \pmod{2^5},\\ a^k \equiv 1 \pmod 3,\\ a^k \equiv 1 \pmod 5. \end{cases} $$

$\endgroup$
4
  • $\begingroup$ Thank you. Can you explain how this relates to Euler's Theorem? $\endgroup$ – qt_314 Nov 10 '20 at 2:02
  • $\begingroup$ @qt_314 The approach I suggest to this problem does not involve Euler's theorem at all, if that's what you mean. When I made my earlier comment, I had not yet thought of this approach. $\endgroup$ – Ben Grossmann Nov 10 '20 at 2:03
  • $\begingroup$ Oh, I see. Thank you for the clarification. $\endgroup$ – qt_314 Nov 10 '20 at 2:07
  • $\begingroup$ @qt_314 See also here for motivation on the relationship between little Fermat and Euler. $\endgroup$ – Bill Dubuque Nov 10 '20 at 2:25

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