- #1
SrEstroncio
- 62
- 0
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.
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: