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
    10
    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
    10
    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, 07:52 PM
  2. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 02:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 10:47 PM
  5. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 09:15 AM

Search Tags


/mathhelpforum @mathhelpforum