Prove that numbers in the form of 2^k + 1 are not prime numbers. For example 2^{2017} + 1

[stan]

I need to show that numbers in the form of [MATH]2^k+1[/MATH] are not prime numbers. For example [MATH]2^{2017}+1[/MATH].
I don't know how to do that, could someone give me some advice?

 

[tkhunny]

You probably should pick a starting place.
k = 1, Prime
k = 2, Prime
k = 3, Composite
k = 4, Prime
k = 5, Composite

 

[stan]

I tried thinking about this way but couldn't see any patterns which k-s are giving prime as a result and which are not

 

[Dr.Peterson]

I need to show that numbers in the form of [MATH]2^k+1[/MATH] are not prime numbers. For example [MATH]2^{2017}+1[/MATH].
I don't know how to do that, could someone give me some advice?

It's not quite clear what you are trying to do.

I would read your statement, "numbers in the form of [MATH]2^k+1[/MATH] are not prime numbers" as "any number in the form of [MATH]2^k+1[/MATH] is not a prime number". But that is false: there are numbers of that form that are prime.

It could also be taken to mean, "some numbers in the form of [MATH]2^k+1[/MATH] are not prime numbers". You can do that by finding one, as tkhunny did.

But since some are and some are not, I think you are asking how to determine "whether a particular number in the form of [MATH]2^k+1[/MATH] is a prime number". In that case, this is a very hard problem. To see some techniques for determining this, and for evidence of its difficulty, see this page, for example: https://primes.utm.edu/mersenne/ .

On the other hand, in one sense it is easy: to show that it is not a prime number, you have to find a factor. That, of course, is easier said than done ...

EDIT: Oops. I misread the sign ...

 

[ksdhart2]

I tried thinking about this way but couldn't see any patterns which k-s are giving prime as a result and which are not

Suppose \(\displaystyle k\) is odd and \(\displaystyle k \ge 3\). Then we can say: \(\displaystyle 2^{k} + 1 = 2^{2n + 1} + 1, \: n \in \mathbb{Z^+}\). Going one step further, we have \(\displaystyle (2n + 1) = (2n - 1) + 2\) and thus \(\displaystyle 2^{2n + 1} = 4 \cdot 2^{2n - 1}\). Using this result, what can you say about:

\(\displaystyle (2^{2n + 1} + 1) - (2^{2n - 1} + 1) = \text{???}\)

What does that tell you about if \(\displaystyle 2^k + 1\) is prime for odd \(\displaystyle k \ge 3\)? Can you see why \(\displaystyle k = 1\) is a special case and needs to be handled separately?

Next suppose \(\displaystyle k\) is even and \(\displaystyle k = 4n +2, \: n \in \mathbb{Z^+}\) (i.e. \(\displaystyle k\) is not a multiple of 4). By a similar logic to above, we have \(\displaystyle (4n + 2) = (4n - 2) + 4\) and thus \(\displaystyle 2^{4n + 2} = 16 \cdot 2^{4n - 2}\). Using this result, what can you say about:

\(\displaystyle (2^{4n + 2} + 1) - (2^{4n - 2} + 1) = \text{???}\)

What does that tell you about if \(\displaystyle 2^k + 1\) is prime for \(\displaystyle k = 4n + 2 \ge 6\)? Can you see why \(\displaystyle k = 2\) is a special case and needs to be handled separately?

That leaves only the cases where \(\displaystyle k = 4n, \: n \in \mathbb{Z}\) (i.e. \(\displaystyle k\) is a multiple of 4), for which I don't see any obvious rules off the top of my head. For some multiples of 4, \(\displaystyle 2^k + 1\) is prime (e.g. \(\displaystyle 2^8 + 1 = 257, \: 2^{16} + 1 = 65537\)) but for others it's composite (e.g. \(\displaystyle 2^{12} + 1 = 4097, \: 2^{24} + 1 = 16777217\))