# Thread: Problem #8 - Number Theory

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

2. ## 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

3. ## Re: Problem #8 - Number Theory

Originally Posted by muddywaters
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, ...... ?

4. ## 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*}

5. ## 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?

6. ## Re: Problem #8 - Number Theory

Originally Posted by Hartlw
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.

7. ## 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.

8. ## Re: Problem #8 - Number Theory

Originally Posted by Hartlw
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.

9. ## 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