Results 1 to 3 of 3

Math Help - Number theory

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Number theory

    (i) Let p the smallest prime divisor of n. Show that there exist integers a, b, such that an+b(p-1)=1

    (ii) For every n>1 show that n does not divide (2^n)-1

    Please ANY help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by AlexHall View Post
    (i) Let p the smallest prime divisor of n. Show that there exist integers a, b, such that an+b(p-1)=1
    Hint: n and p-1 must be co-prime (because any common factor would have to be less than p, and therefore could not divide n).

    Quote Originally Posted by AlexHall View Post
    (ii) For every n>1 show that n does not divide (2^n)-1
    (I was totally unable to see how to do this until I realised that you need to use part (i).)

    Suppose that n does divide 2^n-1. Let p be the smallest prime divisor of n, then p must divide 2^n-1. In other words, 2^n\equiv1\!\!\pmod p. Since p is prime, it follows from Fermat's Little Theorem that 2^{p-1}\equiv1\!\!\pmod p. Then by part (i), 2 = 2^{an+b(p-1)}= (2^n)^a(2^{p-1})^b\equiv1\!\!\pmod p, contradiction!

    Edit. I forgot to say that that proof doesn't work if p=2 (because 2 and p are not then co-prime, so Fermat's theorem goes wrong!). But the result is obvious when p=2, because n would then be even, and (2^n)-1 is odd.
    Last edited by Opalg; October 16th 2008 at 11:19 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    8
    Thank you so much.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 19th 2010, 07:51 PM
  3. Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 16th 2010, 05:05 PM
  4. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum