Results 1 to 6 of 6

Math Help - A Couple Problems with Primes

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    A Couple Problems with Primes

    1) Show that if a is a positive integer and a^m + 1 is an odd prime, then m = 2^n for some nonnegative integer n.

    2) Find all primes of the form 2^2^n + 5, where n is a nonnegative integer. (Its 2^(2^n), meaning the n is another exponent, I just couldn't get it to work with Latex.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    1) Show that if a is a positive integer and a^m + 1 is an odd prime, then m = 2^n for some nonnegative integer n.

    2) Find all primes of the form 2^2^n + 5, where n is a nonnegative integer. (Its 2^(2^n), meaning the n is another exponent, I just couldn't get it to work with Latex.)
    Well I find these to be interesting problems and have not studied enough number theory to know how to approach them, nevertheless I see you've made over 100 posts so by this time should know that MHF is not a homework service; please provide some partial work/say where you got stuck.

    To get a power tower in LaTeX use braces like this (double click to see source)

    2^{2^n}+5
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Ah I think I've solved the first problem. For a odd, m can't be odd because then a^m+1 is even. For a even, we have a \equiv -1 \pmod{ (a+1)} and for odd m we have -1^m \equiv -1 \pmod{ (a+1)} thus a^m+1 will be divisible by a+1. Thus m must be even in all cases. Then suppose m is divisible by any odd prime p. We write m=kp. Then we can write a^m = (a^k)^p which is just a positive integer to an odd power which we proved can't be one less than a prime above. Thus the only prime that can divide m is 2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    I think problem 2 is a trick question. Look at it mod 3, should see there are no such primes, except for n=0 giving the exponent odd, and the prime 7.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by undefined View Post
    Ah I think I've solved the first problem. For a odd, m can't be odd because then a^m+1 is even. For a even, we have a \equiv -1 \pmod{ (a+1)} and for odd m we have -1^m \equiv -1 \pmod{ (a+1)} thus a^m+1 will be divisible by a+1. Thus m must be even in all cases. Then suppose m is divisible by any odd prime p. We write m=kp. Then we can write a^m = (a^k)^p which is just a positive integer to an odd power which we proved can't be one less than a prime above. Thus the only prime that can divide m is 2.
    I think that the first few conclusions are not necessary for the proof. If some odd prime p divides m, such that m = kp, then a^m + 1 = (a^k + 1)((a^k)^{p-1} - ..... - a^k + 1) If no odd prime divides m then it can be nothing but a power of 2.
    Last edited by Traveller; September 23rd 2010 at 01:05 AM. Reason: corrected mistake in formula
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    I'm refering to problem 1). I will apply the following Algebraic identity: If k\ge1 is odd, then x^k+1=(x+1)(x^{k-1}-x^{k-2}+\cdots-x+1).

    Suppose that m has an odd prime divisor p . Then write m=pM for some integer M . Now a^{m}+1=a^{pM}+1=(a^M+1)((a^M)^{p-1}-(a^M)^{p-2}+\cdots-a^M+1) by the identity, and we see that a^M+1 divides a^{pM}+1.
    Since a^M+1<a^{pM}+1, it also follows that a^{pM}+1 is not prime.

    Therefore, m cannot have odd prime divisors, .i.e, m=2^n , where n is a nonnegative integer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Couple Problems with Primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 07:54 AM
  2. A couple of problems
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: April 29th 2010, 06:41 AM
  3. Couple of problems. help please
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 30th 2009, 02:03 PM
  4. Couple problems.
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: November 23rd 2008, 07:41 PM
  5. I need a help on a couple problems...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2008, 03:56 AM

Search Tags


/mathhelpforum @mathhelpforum