Results 1 to 4 of 4

Math Help - Help with Fermat's Little Theorem

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    2

    Help with Fermat's Little Theorem

    using fermat's little theorem show that each prime divisor of (2^p) -1, where p is a prime is greater than p.

    any help on this would be appreciated. thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by thebrownguy01 View Post
    using fermat's little theorem show that each prime divisor of (2^p) -1, where p is a prime is greater than p.

    any help on this would be appreciated. thanks in advance!
    Since q|(2^p-1) it means 2^p\equiv 1(\bmod q). Let k be the order of 2 modulo q then 2^k \equiv 1(\bmod q), but by properties of orders we know k|p since k\not = 1 it means k=p thus the p is the order of 2 modulo q. But by Fermat's little theorem we know 2^{q-1} \equiv 1(\bmod p) and hence k|(q-1)\implies p|(q-1) by properties of order. In particular, this means p\leq q-1 < q. Thus, q, a prime divisor of 2^p-1, is greater than p.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2008
    Posts
    2
    thanks for the response but I don't quite understand still. Is there a way you could explain it some more or provide a link to a place where I might find something to help me understand it?
    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by thebrownguy01 View Post
    thanks for the response but I don't quite understand still. Is there a way you could explain it some more or provide a link to a place where I might find something to help me understand it?
    Thanks
    Given a prime p and an integer a (with \gcd(a,p)=1) we define the order of a mod p to be the least positive exponent k such that a^k \equiv 1(\bmod p). Of course such a k can always be found and furthermore k\leq p-1 because a^{p-1} \equiv 1(\bmod p) and k is the least (smallest) such exponent. For example, take p=5 and a=4 then k=2 because 4^2 \equiv 1(\bmod 15). Now there is a simple theorem with orders. Suppose n is a positive integer such that a^n \equiv 1(\bmod p) then k|n*. This theorem is telling us that the order must divide any exponent which raises a congruent to 1. So in the above proof we concluded that k|p but since p is a prime it forces k=p.


    *)In case you want to see the proof it is simple. We can write n=qk+r where 0\leq r < k by the division algorithm. That means a^n = a^{qk+r} = \left( a^k \right)^q a^r \equiv a^r (\bmod p) but a^n \equiv 1(\bmod p) so a^r \equiv 1(\bmod p) but that is impossible since r<k and k is least so r=0. Which means n=qk+r\implies n=qk. And so clearly k|n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermatís Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2011, 06:52 PM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 09:47 PM
  5. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 08:15 AM

Search Tags


/mathhelpforum @mathhelpforum