1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modulo arithmetic - fact?

  1. Jan 1, 2013 #1
    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.
  2. jcsd
  3. Jan 1, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You need to assume gcd(a,N)=1 as well.
  4. Jan 1, 2013 #3
    The more popular format is

    [itex]a^{\varphi(n)}\equiv 1 (mod \;n)[/itex] where [itex] gcd(a,n)=1[/itex]
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Modulo arithmetic - fact?
  1. Modulo a prime (Replies: 1)

  2. Congruences / modulo (Replies: 3)