Modulo Arithmetic: Is a^{\varphi(n)}\equiv 1 (mod \;n) for gcd(a,n)=1?

  • Thread starter Thread starter Ted123
  • Start date Start date
  • Tags Tags
    Arithmetic
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
2 replies · 2K views
Ted123
Messages
428
Reaction score
0
Is it true that if [itex]A \equiv B \mod{\varphi(N)}[/itex] where [itex]\varphi (N)[/itex] is Euler's totient function then [itex]a^A \equiv a^B \mod{N}[/itex]?

I'm not after a proof or anything but I didn't do a number theory course and it seems that this fact is used in many questions I'm currently doing.
 
Physics news on Phys.org
You need to assume gcd(a,N)=1 as well.
 
The more popular format is

[itex]a^{\varphi(n)}\equiv 1 (mod \;n)[/itex] where [itex]gcd(a,n)=1[/itex]