Results 1 to 2 of 2

Thread: Prime numbers problem

  1. #1
    Member
    Joined
    Oct 2006
    Posts
    84

    Prime numbers problem

    If anyone could explain how this is done, it would be very much appreciated!

    Fermatís Little Theorem states that if a is an integer with gcd(a,p) = 1, where p is a prime number, then:
    a^(p-1) ≡ 1 mod p

    Define e_p(a) to be the smallest number n>0 such that a^n ≡ 1 mod p. Compute e_p(a) for the prime p = 5 and 1≤a≤p-1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by clockingly View Post
    If anyone could explain how this is done, it would be very much appreciated!

    Fermatís Little Theorem states that if a is an integer with gcd(a,p) = 1, where p is a prime number, then:
    a^(p-1) ≡ 1 mod p

    Define e_p(a) to be the smallest number n>0 such that a^n ≡ 1 mod p. Compute e_p(a) for the prime p = 5 and 1≤a≤p-1
    There are only a limited number of possibilities here.

    Obviously 1 is a rather trivial example of this since $\displaystyle 1^n = 1$ for any n.

    We can look at 2 and get that $\displaystyle 2^4 \equiv 1 \text{ mod 5}$

    etc.
    $\displaystyle 3^4 \equiv 1 \text{ mod 5}$
    and
    $\displaystyle 4^2 \equiv 1 \text{ mod 5}$

    So I guess we have that
    $\displaystyle e_p(1) = 1$
    $\displaystyle e_p(2) = 4$
    $\displaystyle e_p(3) = 4$
    $\displaystyle e_p(4) = 2$

    Is this what you were looking for?

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Oct 22nd 2011, 12:37 PM
  2. Replies: 8
    Last Post: May 8th 2010, 08:52 AM
  3. Prime numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 20th 2009, 02:28 PM
  4. Number theory, prime numbers, interesting problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Oct 21st 2007, 01:23 AM
  5. Finding prime numbers - problem w/method
    Posted in the Algebra Forum
    Replies: 20
    Last Post: Dec 10th 2006, 11:04 AM

Search Tags


/mathhelpforum @mathhelpforum