SOLUTION: Suppose a >= 2 and n is a natural number larger than 1. How can I prove that if n is odd, then a^n+1 is not prime?

Algebra.Com
Question 1208953: Suppose a >= 2 and n is a natural number larger than 1.
How can I prove that if n is odd, then a^n+1 is not prime?
Found 2 solutions by math_tutor2020, ikleyn:
Answer by math_tutor2020(3816)   (Show Source): You can put this solution on YOUR website!

It wasn't stated, but I'm assuming 'a' is an integer.
I'll also assume the +1 is not in the exponent.
If the +1 was in the exponent, then it's very easy to show that a^(n+1) is always composite regardless if n was even or odd.

To factor a polynomial, it's often most efficient to look for the roots.
For instance, to factor x^2+5x+6, set it equal to zero and use the quadratic formula. You should determine the roots are x = -2 and x = -3.
Those lead to the factors (x+2) and (x+3). Hence x^2+5x+6 = (x+2)(x+3).
You can use guess-and-check for small values like this, but it gets tricky when trying to factor something like x^2+31x+238.

Anyways, the roots are closely connected to the factorization of the polynomial.
Consider the polynomial equation y = (x^n)+1.
Using the rational root theorem, we see that x = -1 is a potential root.
If x = -1 and n is odd, then x^n+1 = (-1)^(2k+1)+1 = -1*( (-1)^2 )^k+1 = -1+1 = 0 which confirms that x = -1 is a root when n is odd.
x = -1 being a root leads to x+1 being a factor after adding 1 to both sides.

Use a graphing tool like GeoGebra or Desmos to look at the graphs of y = (x^3)+1, y = (x^5)+1, y = (x^7)+1, etc.
All of those graphs have x = -1 as an x intercept and hence (x+1) as a factor.
This will prove (x^n)+1 is composite when n is odd and x is an integer.
By extension it does the same for (a^n)+1.
Here are a few select examples:
n = 3:
	a = 2;  (a^n)+1 = (2^3)+1 = 9 is composite because 9 = 3*3
	a = 3;  (a^n)+1 = (3^3)+1 = 28 is composite because 28 = 4*7
	a = 4;  (a^n)+1 = (4^3)+1 = 65 is composite because 65 = 5*13
n = 5:
	a = 2;  (a^n)+1 = (2^5)+1 = 33 is composite because 33 = 3*11
	a = 3;  (a^n)+1 = (3^5)+1 = 244 is composite because 244 = 4*61
	a = 4;  (a^n)+1 = (4^5)+1 = 1025 is composite because 1025 = 5*205
n = 7:
	a = 2;  (a^n)+1 = (2^7)+1 = 129 is composite because 129 = 3*43
	a = 3;  (a^n)+1 = (3^7)+1 = 2188 is composite because 2188 = 4*547
	a = 4;  (a^n)+1 = (4^7)+1 = 16385 is composite because 16385 = 5*3277

Note thatAll of what is mentioned is where n is odd. This wraps up the proof.

------------------------------------------------------------

If you're curious what happens when n is even then the graph of y = (x^n)+1 is always above the x axis.
It won't have any real number roots.
The roots will be complex numbers of the form a+bi where i = sqrt(-1)
An example would be y = x^2+49 which has the complex roots 7i and -7i.
So it's not clear if (a^n)+1 is composite or prime when n is even.
Turns out it depends. Here are some examples.
n = 2:
	a = 2;  (a^n)+1 = (2^2)+1 = 5 is prime (the only factors are 1 and 5)
	a = 3;  (a^n)+1 = (3^2)+1 = 10 is composite since 2*5 = 10
	a = 4;  (a^n)+1 = (4^2)+1 = 17 is prime (the only factors are 1 and 17)
n = 4:
	a = 2;  (a^n)+1 = (2^4)+1 = 17 is prime (the only factors are 1 and 17)
	a = 3;  (a^n)+1 = (3^4)+1 = 82 is composite since 82 = 2*41
	a = 4;  (a^n)+1 = (4^4)+1 = 257 is prime (the only factors are 1 and 257; see "primality check" below)
n = 6:
	a = 2;  (a^n)+1 = (2^6)+1 = 65 = 5*13 is composite
	a = 3;  (a^n)+1 = (3^6)+1 = 730 = 10*73 is composite
	a = 4;  (a^n)+1 = (4^6)+1 = 4097 = 17*241 is composite

Primality Check: To determine if 257 is prime or not, divide it over each item in the list of primes smaller than sqrt(257) = 16.0312
You'll divide 257 over the following primes: 2,3,5,7,11, and 13
You should find that the result of each division is a non-integer decimal value.
This proves none of those values are a factor of 257 and proves 257 is prime.
Answer by ikleyn(52776)   (Show Source): You can put this solution on YOUR website!
.
Suppose a  is a natural number  >= 2 and n is a natural number larger than 1.
How can I prove that if  n  is odd,  then    is not a prime?
~~~~~~~~~~~~~~~~~~~~~~~


        I edited your post - see the underlined fragment - to make it precisely correct. 


If n is an odd positive integer number greater than 1, then there is a decomposition


     = 


(the signs at degrees of "a" alternate " + " and " - ").


It is a well known formula. To prove it, it is enough to open parentheses.


This formula shows and tells that every integer number of the form   
with integer positive  " a "  and natural odd  n > 1  is a composite number.


It is what you want to prove.

Solved.


For  n=3,  the decomposition   =  is studied explicitly
in standard school  Math curriculum as the sum of cubes decomposition.


For other odd natural integer  " n "  greater than  3,  it can be
easily obtained from the formula of the sum of a geometric progression
1,  -a,  a^2,  -a^3,  a^4,  -a^5, . . . ,  a^(n-1)

with alternate signs,  which corresponds to the case of common ratio  " -a ".



RELATED QUESTIONS

Using direct proof, prove that if n is a natural number, then n(n+1) is... (answered by Theo)
if 'n' is odd, then prove that (x + 1) is a factor of x^n +... (answered by rothauserc)
Find all natural n such that n^2 − 1 is a cube of a prime... (answered by richard1234)
I am struggling with this question, can someone help? thanks so much. Select any odd... (answered by amine)
given d|n+1 and d|n^2+1 and d|2 prove that if n is odd then gcd(n+1,n^2+1) =... (answered by ikleyn)
) Show that if n is a natural number such that 2n-1 is prime, thenn n is a prime. Is the... (answered by richard1234)
prove, using the direct method of proof, that if n is a natural number, n(n+1) is an even (answered by josgarithmetic,robertb)
This is a Number Theory proof: If N = abc + 1, prove that (N, a) = (N, b) = (N, c) =... (answered by KMST)
Let A = {n C Z | n is odd} and B = {n C Z | n^2 - 1 mod 4}. Prove that A is included in... (answered by ikleyn)