Results 1 to 3 of 3

Math Help - mods with prime powers

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    mods with prime powers

    Hey guys, cant get my head around this fact .If p is a prime, then  a^{p-1} = 1 (mod p) provided a \not\equiv 0 mod p. If someone could explain with an clear example of some sort it would be much appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by jvignacio View Post
    Hey guys, cant get my head around this fact .If p is a prime, then  a^{p-1} = 1 (mod p) provided a \not\equiv 0 mod p. If someone could explain with an clear example of some sort it would be much appreciated.
    This result is called Fermat's Little Theorem. I suppose the reason that it holds is because every number less than p is coprime to p and so there are no zero divisors. So every element has an inverse, but there is not enough space for it not to be of this form.

    For an example, try working mod 5 (this is small enough to work with).

    1^4 = 1
    2^4 = 16 = 15+1 \equiv 1 \text{ mod }5
    3^4 = 81 = 80+1 \equiv 1 \text{ mod }5
    4^5 = 16^2 \equiv 1^2 \equiv 1 \text{ mod }5.

    Alternatively, plug the following code into maple,

    p:=7;
    for n from 1 to (p-1) do
    a:=p^{n-1}:
    print(a, a mod p):
    od:

    and change the number p to be any prime.

    There actually exists a very beautiful proof of this result, which can be found on wikipedia. (Actually, this page contains many beautiful proofs of the theorem. If you really want to understand the theorem, read through as many of these proofs as you have the knowledge to grasp.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Swlabr View Post
    This result is called Fermat's Little Theorem. I suppose the reason that it holds is because every number less than p is coprime to p and so there are no zero divisors. So every element has an inverse, but there is not enough space for it not to be of this form.

    For an example, try working mod 5 (this is small enough to work with).

    1^4 = 1
    2^4 = 16 = 15+1 \equiv 1 \text{ mod }5
    3^4 = 81 = 80+1 \equiv 1 \text{ mod }5
    4^5 = 16^2 \equiv 1^2 \equiv 1 \text{ mod }5.

    Alternatively, plug the following code into maple,

    p:=7;
    for n from 1 to (p-1) do
    a:=p^{n-1}:
    print(a, a mod p):
    od:

    and change the number p to be any prime.

    There actually exists a very beautiful proof of this result, which can be found on wikipedia. (Actually, this page contains many beautiful proofs of the theorem. If you really want to understand the theorem, read through as many of these proofs as you have the knowledge to grasp.)
    Cheers, makes a lot more sense now!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 13th 2011, 12:32 PM
  2. Comparing large prime powers.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 9th 2010, 07:08 AM
  3. How many distinct prime powers divide n ?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 10th 2010, 10:12 PM
  4. proof of a congruence modulo prime powers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 21st 2009, 03:41 AM
  5. Prime powers
    Posted in the Algebra Forum
    Replies: 6
    Last Post: February 16th 2008, 08:11 AM

Search Tags


/mathhelpforum @mathhelpforum