Results 1 to 10 of 10

Math Help - Prime numbers question

  1. #1
    Junior Member Nerdfighter's Avatar
    Joined
    May 2009
    From
    Washington
    Posts
    25

    Prime numbers question

    My teacher has given my class a challenge task: to prove the following implication:

    Let a and n be integers such that n \geq 1 and a \geq 2.

    Prove: If a^n + 1 is prime, then there exists an integer m such that n = 2^m

    the following identity was given to us to use:

    Let b and k be integers and k \geq 1, then
    (b^2)^k + b^1 + 1 = (b + 1)(b^2k - b^2k-1 + ... - b + 1) = (b + 1) \sum_{j=0}(-1)^jb^j <------ note, there should be a k on the top of the \sum
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Nerdfighter View Post
    My teacher has given my class a challenge task: to prove the following implication:

    Let a and n be integers such that n \geq 1 and a \geq 2.

    Prove: If a^n + 1 is prime, then there exists an integer m such that n = 2^m

    the following identity was given to us to use:

    Let b and k be integers and k \geq 1, then
    (b^2)^k + b^1 + 1 = (b + 1)(b^2k - b^2k-1 + ... - b + 1) = (b + 1) \sum_{j=0}(-1)^jb^j <------ note, there should be a k on the top of the \sum
    Since its a challenge task, I will give you a hint. Enjoy solving it

    Two hints:
    Step 1) x^n + 1 is never prime when n is odd and greater than 1.

    Step 2) x^n + 1 is never prime when n has an odd factor greater than 1(prove this using Step 1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Nerdfighter View Post
    My teacher has given my class a challenge task: to prove the following implication:

    Let a and n be integers such that n \geq 1 and a \geq 2.

    Prove: If a^n + 1 is prime, then there exists an integer m such that n = 2^m

    the following identity was given to us to use:

    Let b and k be integers and k \geq 1, then
    (b^2)^k + b^1 + 1 = (b + 1)(b^2k - b^2k-1 + ... - b + 1) = (b + 1) \sum_{j=0}(-1)^jb^j <------ note, there should be a k on the top of the \sum
    The question is equivalent to: If n is not a power of 2, then a^n+1 is not prime.

    Let n=2^mk for some odd integer k>1. Then, writing b=a^{2^m}, we have
    a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)
    and 1<b+1<b^k+1. This shows that a^n+1 is composite.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member Nerdfighter's Avatar
    Joined
    May 2009
    From
    Washington
    Posts
    25
    Quote Originally Posted by TheAbstractionist View Post
    The question is equivalent to: If n is not a power of 2, then a^n+1 is not prime.

    Let n=2^mk for some odd integer k>1. Then, writing b=a^{2^m}, we have
    a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)
    and 1<b+1<b^k+1. This shows that a^n+1 is composite.
    Ooh, I really liked this. Thanks, this is helping to push me in the correct direction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Nerdfighter View Post
    Ooh, I really liked this. Thanks, this is helping to push me in the correct direction.
    Youíre welcome.

    By the way, in the proof that I gave, it is essential that k be odd and greater than 1. Do you know why it fails if k is even or k=1?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member Nerdfighter's Avatar
    Joined
    May 2009
    From
    Washington
    Posts
    25
    Quote Originally Posted by TheAbstractionist View Post
    Youíre welcome.

    By the way, in the proof that I gave, it is essential that k be odd and greater than 1. Do you know why it fails if k is even or k=1?
    Is it because a^n + 1 would no longer be prime if k was even or equal to 1?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Nerdfighter View Post
    Is it because a^n + 1 would no longer be prime if k was even or equal to 1?
    Correct. But, why?

    There are a few details in the proof I glossed over, but it may well be worth checking everything to see that it works (or that I havenít made any mistake ).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member Nerdfighter's Avatar
    Joined
    May 2009
    From
    Washington
    Posts
    25
    Quote Originally Posted by TheAbstractionist View Post
    Correct. But, why?

    There are a few details in the proof I glossed over, but it may well be worth checking everything to see that it works (or that I havenít made any mistake ).
    Ahhh, the bane of my existence in the number theory class! Every time I come to a conclusion, my teacher will look at what I have written and then turn to me and ask: "why?"

    It's at that point that I kind of melt, and respond: "....because?"
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Let's start by observing that every n>1 which is not a power of 2 can be written as...

    n= (2m+1)\cdot k with m>0 and k>0 (1)

    Now we consider the identity...

    (1+a^{k})\cdot (1-a^{k} + a^{2k} -...+ a^{2mk}) = 1+ a^{k} - a^{k} - a^{2k} + ... +a^{2mk} + a^{(2m+1)k} = 1+ a^{(2m+1)k} (2)

    From (2) and (1) is evident that if 1 + a^{n} is prime, n must be a power of 2...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Nerdfighter View Post
    Ahhh, the bane of my existence in the number theory class! Every time I come to a conclusion, my teacher will look at what I have written and then turn to me and ask: "why?"

    It's at that point that I kind of melt, and respond: "....because?"
    All right. In my proof, I wrote

    a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)

    This is for k odd but not for k even. Why? Because if k is even, and you go b^{k-1}-b^{k-2}+b^{k-3}-b^{k-4}+\cdots then your last term is going to be -1 not +1. In that case multiplying by b+1 will not give b^k+1. Only when k is odd does the result stand.

    I didnít mention this because I thought you might want to check everything carefully yourself and make sure that what I wrote made sense.

    I also wrote 1<b+1<b^k+1. It might look okay, but donít be fooled. It might still break down if certain conditions are not met Ė for example, what if b\le1? Luckily the question says a\ge2 so b=a^{2^n}>1 and weíre safe. Everything has to be carefully checked and every gap must be covered.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Prime numbers.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 21st 2010, 01:03 PM
  3. Replies: 45
    Last Post: June 6th 2010, 06:18 PM
  4. prime numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 31st 2010, 09:44 AM
  5. Prime Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 9th 2007, 12:53 PM

Search Tags


/mathhelpforum @mathhelpforum