Results 1 to 9 of 9
Like Tree6Thanks
  • 1 Post By muddywaters
  • 1 Post By Idea
  • 1 Post By SlipEternal
  • 1 Post By Hartlw
  • 2 Post By SlipEternal

Math Help - Problem #8 - Number Theory

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,079
    Thanks
    375
    Awards
    1

    Problem #8 - Number Theory

    I got this one from our archives as well.

    Show that n^4 + 4^n is not prime for n \geq 2. (n is a positive integer!)

    This is a more of a Number Theory problem than algebraic. As my proof relies more on a College Algebra level rather than Number Theory I'm curious to see what you might come up with.

    -Dan
    Last edited by topsquark; June 1st 2014 at 04:37 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2012
    From
    malaysia
    Posts
    98
    Thanks
    15

    Re: Problem #8 - Number Theory

    all n values that are even will give a non-prime number, as (evennumber)^4 is always even and 4^n is always even. even+even gives even numbers bigger than 2, which are never prime. i can't continue from here though, dont know about the odd n values
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    175
    Thanks
    85

    Re: Problem #8 - Number Theory

    Quote Originally Posted by muddywaters View Post
    all n values that are even will give a non-prime number, as (evennumber)^4 is always even and 4^n is always even. even+even gives even numbers bigger than 2, which are never prime. i can't continue from here though, dont know about the odd n values
    if n is an odd integer >= 3 and n is not a multiple of 5 then n^4 + 4^n is a multiple of 5 and therefore not a prime
    Proof:
    n is 1,2,3,or 4 (mod 5)
    n^4 is 1 (mod 5)
    4^n is -1 (mod 5)
    So n^4 + 4^n is congruent to 0 (mod 5)

    How do we handle the case n=5, 15, 25, 35, 45, ...... ?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: Problem #8 - Number Theory

    If n\equiv 0\pmod{2}, then n^4+4^n \equiv 0\pmod{2}.

    If n\equiv 1\pmod{2}, then n+1\equiv 0\pmod{2}, so 2^{n+1} is a perfect square, and n^4+4^n factors as
    (n^2+n\sqrt{2^{n+1}}+2^n)(n^2-n\sqrt{2^{n+1}} + 2^n)

    So, all that is left is to show that for odd n>2, both terms are greater than 1. Since n^2+2^n>1, the first term is guaranteed to be greater than 1. So, we just need to show the second term is greater than one.

    Since (n^2-1)^2+2^{2n} \ge 2^{2n} > 2^{n+1} (for all n>1), we have

    \begin{align*}n^4-2n^2+1+4^n-2^{n+1} > 0 & \Rightarrow n^4-2n^2+1+4^n-2^{n+1}+n^2 2^{n+1} > n^2 2^{n+1} \\ & \Rightarrow (n^2+2^n-1)^2 > n^2 2^{n+1} \\ & \Rightarrow n^2 + 2^n - 1 > n\sqrt{2^{n+1}} \\ & \Rightarrow n^2-n\sqrt{2^{n+1}}+2^n > 1\end{align*}
    Last edited by SlipEternal; June 3rd 2014 at 08:22 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Problem #8 - Number Theory

    If n even, obvious.
    If n odd, 2n+1 is a perfect square and the factorization are really neat observations. Thanks.

    But what's the point of the congruences?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: Problem #8 - Number Theory

    Quote Originally Posted by Hartlw View Post
    But what's the point of the congruences?
    n\equiv 0\pmod{2} is the same as saying n is even.
    n\equiv 1\pmod{2} is the same as saying n is odd.

    I have been working with modular arithmetic long enough that it feels more natural for me to use congruences rather than the words even and odd. The meaning is the same either way.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Problem #8 - Number Theory

    You have shown n^4+4^n=rs where r and s are integers and r positive. Obviously s is positive.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: Problem #8 - Number Theory

    Quote Originally Posted by Hartlw View Post
    You have shown n^4+4^n=rs where r and s are integers and r positive. Obviously s is positive.
    If n=1, then the factorization I gave is 1^4+4^1 = (5)(1). However, 5 is a prime number. The problem asks to prove that for n\ge 2, n^4+4^n is NOT prime. So, to do that, it is not enough to show the factors are positive. You must show they are both greater than 1.
    Thanks from Hartlw and topsquark
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,079
    Thanks
    375
    Awards
    1

    Re: Problem #8 - Number Theory

    Hey, lots of action on this one! Thanks to all.

    SlipEternal gets some extra kudos for checking the "trivial" factorization problem. (That one of the factors might be 1.) I did eventually find the proof online (which was pretty much identical to Slip's and my own) but didn't address the trivial factorization problem.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number theory problem...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 1st 2009, 09:02 AM
  2. Number theory problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 16th 2009, 02:29 PM
  3. Number Theory Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 28th 2009, 02:44 PM
  4. number theory problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: March 11th 2009, 07:43 AM
  5. Replies: 2
    Last Post: December 18th 2008, 05:28 PM

Search Tags


/mathhelpforum @mathhelpforum