Results 1 to 10 of 10

Thread: 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 $\displaystyle a $and $\displaystyle n$ be integers such that $\displaystyle n \geq 1$ and $\displaystyle a \geq 2$.

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

    the following identity was given to us to use:

    Let $\displaystyle b$ and $\displaystyle k$ be integers and $\displaystyle k \geq 1$, then
    $\displaystyle (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 $\displaystyle k$ on the top of the $\displaystyle \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 $\displaystyle a $and $\displaystyle n$ be integers such that $\displaystyle n \geq 1$ and $\displaystyle a \geq 2$.

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

    the following identity was given to us to use:

    Let $\displaystyle b$ and $\displaystyle k$ be integers and $\displaystyle k \geq 1$, then
    $\displaystyle (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 $\displaystyle k$ on the top of the $\displaystyle \sum$
    Since its a challenge task, I will give you a hint. Enjoy solving it

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

    Step 2) $\displaystyle 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 $\displaystyle a $and $\displaystyle n$ be integers such that $\displaystyle n \geq 1$ and $\displaystyle a \geq 2$.

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

    the following identity was given to us to use:

    Let $\displaystyle b$ and $\displaystyle k$ be integers and $\displaystyle k \geq 1$, then
    $\displaystyle (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 $\displaystyle k$ on the top of the $\displaystyle \sum$
    The question is equivalent to: If $\displaystyle n$ is not a power of 2, then $\displaystyle a^n+1$ is not prime.

    Let $\displaystyle n=2^mk$ for some odd integer $\displaystyle k>1.$ Then, writing $\displaystyle b=a^{2^m},$ we have
    $\displaystyle a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)$
    and $\displaystyle 1<b+1<b^k+1.$ This shows that $\displaystyle 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 $\displaystyle n$ is not a power of 2, then $\displaystyle a^n+1$ is not prime.

    Let $\displaystyle n=2^mk$ for some odd integer $\displaystyle k>1.$ Then, writing $\displaystyle b=a^{2^m},$ we have
    $\displaystyle a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)$
    and $\displaystyle 1<b+1<b^k+1.$ This shows that $\displaystyle 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 $\displaystyle k$ be odd and greater than 1. Do you know why it fails if $\displaystyle k$ is even or $\displaystyle 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 $\displaystyle k$ be odd and greater than 1. Do you know why it fails if $\displaystyle k$ is even or $\displaystyle k=1?$
    Is it because $\displaystyle a^n + 1$ would no longer be prime if $\displaystyle 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 $\displaystyle a^n + 1$ would no longer be prime if $\displaystyle 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
    6
    Let's start by observing that every n>1 which is not a power of 2 can be written as...

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

    Now we consider the identity...

    $\displaystyle (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 $\displaystyle 1 + a^{n}$ is prime, n must be a power of 2...

    Kind regards

    $\displaystyle \chi$ $\displaystyle \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

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

    This is for $\displaystyle k$ odd but not for $\displaystyle k$ even. Why? Because if $\displaystyle k$ is even, and you go $\displaystyle b^{k-1}-b^{k-2}+b^{k-3}-b^{k-4}+\cdots$ then your last term is going to be $\displaystyle -1$ not $\displaystyle +1.$ In that case multiplying by $\displaystyle b+1$ will not give $\displaystyle b^k+1$. Only when $\displaystyle 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 $\displaystyle 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 $\displaystyle b\le1?$ Luckily the question says $\displaystyle a\ge2$ so $\displaystyle 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: Oct 22nd 2011, 12:37 PM
  2. Prime numbers.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 21st 2010, 01:03 PM
  3. Replies: 45
    Last Post: Jun 6th 2010, 06:18 PM
  4. prime numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 31st 2010, 09:44 AM
  5. Prime Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 9th 2007, 12:53 PM

Search Tags


/mathhelpforum @mathhelpforum