Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A^(de) = a mod n

  1. Jul 24, 2009 #1
    So I came across this problem in my textbook, but couldn't seem to solve it...

    Let n be any squarefree integer (product of distinct primes). Let d
    and e be positive integers such that de — 1 is divisible by p — 1 for every prime divisor p of n. (For example, this is the case if [tex] de \equiv 1 mod \phi(n) [/tex].) Prove that
    [tex] a^{de} \equiv a mod n [/tex] for any integer a (whether or not it has a common factor with n).
    Last edited: Jul 24, 2009
  2. jcsd
  3. Jul 24, 2009 #2
    I'm new here so hope it's ok to give a pretty much complete answer as this doesn't seem to be homework.

    The fact that n is a squarefree integer strongly suggests that it would be simpler to show,
    [tex]a^{de} \equiv a \textrm{ (mod p)}[/tex]
    For all prime factors p in n. We then use that all the prime factors are relatively prime to get the original congruence.

    To establish such identities we normally require that gcd(p,a) = 1 so we can use Fermat's little theorem, but the problem explicitly states that we are not allowed to assume that so we need to consider the case p | a. However if this is the case clearly both sides of the congruences are congruent to 0 so we have established
    [tex]a^{de} \equiv a \textrm{ (mod p)}[/tex]
    for primes p that divide a. Now we can assume gcd(p,a) = 1 in which case Fermat's Little theorem tells us
    [tex]a^{p-1} \equiv 1 \textrm{ (mod p)}[/tex]
    Now we can raise both sides to the (de-1)/(p-1) power to get (this is integral since p-1 | de-1),
    [tex]a^{de-1} \equiv 1 \textrm{ (mod p)}[/tex]
    From which the problem trivially follows when you multiply by a.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook