Number theory question.

[Nottom]

Yeah it's a HW question.

For what positive integers n is 4^n+n^4 a prime.

Obviously its true for n=1, (4+1=5)

Anyone have a clue how to find them all?

The problem comes from a section dealing with Wilson's theorem (http://primes.utm.edu/glossary/page.php?sort=WilsonsTheorem) , Fermat's Little Theorem (http://primes.utm.edu/glossary/page.php?sort=FermatsLittleTheorem) , and Pollard's p-1 factoring algorithm (http://en.wikipedia.org/wiki/Pollard's_p-1_algorithm) (although I doubt that would be used here)

[Isura]

You can elminate even numbers n (and n > 1) since 4^n is even, n^4 is even, and the sum of two even numbers is even.

[Nottom]

[ QUOTE ]
You can elminate even numbers n (and n > 1) since 4^n is even, n^4 is even, and the sum of two even numbers is even.

[/ QUOTE ]

Even I'm smart enough to figure that much out /images/graemlins/crazy.gif

Thanks anyway.

[bigpooch]

If n is even, you can do that! /images/graemlins/smile.gif

If n is odd, let's look at things modulo 5.

4^n is congruent to (-1)^n or (-1) when n is odd

and n^4 is congruent to 1 modulo 5 (you know this
by Fermat's little theorem as a^(p-1) is congruent
to 1 modulo p ) as long as n is not a multiple of 5.

Thus, (4^n) + (n^4) is congruent to (-1)+ 1 or 0 as
long as n is not a multiple of 5.

As, (4^n) + (n^4) is increasing, the sum is only prime
for n=1 or possibly when n is an odd multiple of 5.

Note that for n=5, 4^5+5^4 is composite but for n=15 maybe
you can use a computer to see if 4^15 + 15^4 is prime.

That's just a start! There will probably be many more
restrictions on n for the sum to be prime.

[Nottom]

Thanks, that should help a ton.

[AlphaWice]

Suppose n is even. Then n^4 + 4^n is obviously divisible by 2. Suppose n = 1, then n^4 + 4^n = 5, which is prime.

Else, suppose n = 2k+1, where k >= 1. Let x = 2^k. Then n^4 + 4^n = n^4 + 4*x^4 = (n^2 + 2x^2 - 2nx)(n^2 + 2x^2 + 2nx). Since n^2 + x^2 >= 2nx, it follows that both factors are greater than 1, and therefore n^4 + 4^n is composite.

In conclusion, only the positive integer n=1 makes n^4 + 4^n prime.

[Nottom]

Nice, thanks.