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

Help with proof of theorem related to Fermat's.

  1. Jan 16, 2010 #1
    Hello everyone, I have been trying to teach myself number theory and I am stuck trying to prove a (I am sure) very easy to prove theorem related to that of Fermat's.

    The theorem I am to prove states:

    Let [tex]e[/tex] be the lowest number (natural) such that [tex] a^e \equiv 1 (\bmod \ p) [/tex] for [tex] p [/tex] prime such that [tex] p [/tex] does not divide [tex] a [/tex]. Prove that [tex] p-1 [/tex] is a multiple of [tex] e [/tex].

    This theorem came after the proof of Fermat's Theorem, which I will also write for the sake of completeness.

    Let [tex] p [/tex] be a prime and let [tex] a [/tex] be an integer such that [tex] p [/tex] does not divide [tex] a [/tex] it follows that:
    [tex] a^{p-1} \equiv 1 (\bmod \ p) [/tex]

    The book I am reading from (What is mathemathics? by Richard Courant and Herbert Robbins) suggests that I use the fact that [tex] a^{p-1} \equiv a^e \equiv 1 (\bmod \ p) [/tex] and that I divide [tex] p-1 [/tex] by [tex] e [/tex] to get [tex] p-1 = ke + r [/tex]
    where r is the residue.

    I've given it some thought but I kinda blow at math and I've done no useful advances, I was wondering if anyone could provide some more more insight.
    Last edited: Jan 16, 2010
  2. jcsd
  3. Jan 17, 2010 #2
    Given that
    [tex]a^{p-1} = a^{ke+r} \equiv a^e \equiv 1 \pmod p[/tex]
    you are to prove that r=0. Consider that
    [tex]a^{ke+r} = a^{ke} a^r = (a^{e})^k a^r[/tex]
    (now, doing some more work, where can you get at?)
    and remember that r<e.
  4. Jan 17, 2010 #3
    Okay, here's what I've thought:

    We know that
    [tex] a^{p-1} = a^{ke+r} = (a^e)^k a^r \equiv a^e \equiv 1 (\bmod \ p) [/tex]
    We also know that
    [tex] a^e \equiv 1 (\bmod \ p) [/tex],
    we can infer from this that [tex]
    (a^e)^n \equiv 1(\bmod p) [/tex] for any integer n, thus the only way for
    [tex] (a^e)^k a^r \equiv a^e \equiv 1 (\bmod \ p) [/tex]
    to be true is to have
    [tex] a^r \equiv 1 (\bmod \ p) [/tex]
    which can only happen if [tex] r=0 [/tex] since we were supposing [tex] e [/tex] was the lowest power of [tex] a [/tex] that was congruent to 1 modulo [tex] p [/tex].
    So we conclude that
    [tex] p-1 = ke + r = ke + 0 = ke [/tex] and thus e must be a factor of [tex] p-1 [/tex].

    Tell me if I screwed up somewhere along the way.
  5. Jan 17, 2010 #4
    Looks accurate and well presented to me.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook