Those numbers are getting awfully big

Number Theory Level 5

$\large 2^n + 3^n$

Find the sum of all non-negative integers $n$ such that $n \leq 100$ and the above expression is prime .

The answer is 7.

1 solution

Michael Mendrin
Jan 21, 2017

We know that any polynomial of the form

${x}^{2a+1}+{y}^{2a+1}$

is divisible by $x+y$ , and is composite for $a>0$

Hence, any polynomial of the form

${x}^{ b \left( 2a+1 \right) }+{y}^{ b \left( 2a+1 \right) }$

is divisible by ${x}^{ b }+{y}^{ b}$ , and is composite for $b>0$ and $a>0$

So, we can eliminate all $n$ of the form $b \left( 2a+1 \right)$ for $a>0$ and $b>0$ , which leaves us only $n=0, 1, 2, 4$ which adds up to $7$ , after verifying that ${2}^{n}+{3}^{n}$ are primes for these specific values.

Edit $\;$ Brian has pointed out that $n=8, 16, 32, 64$ slips through the cracks. Proof is incomplete.

Eliminating all such $b(2a + 1)$ gets rid of all odds and all evens with an odd prime divisor, but leaves us with $0$ and all powers of $2$ . $2^{8} + 3^{8}$ is divisible by $17$ , but I'm finding it a bit of a trick to eliminate $16, 32$ and $64$ without using a calculator.

Brian Charlesworth - 4 years, 4 months ago

oh yea I did miss those....ah, I'll get those in the morning or something

Michael Mendrin - 4 years, 4 months ago

Ugh, those are especially difficult. I find out that those are generalized Fermat numbers, and for $a=3, b=2$ there are only so many known to be primes. It's looking like proving them to be composite for $n=8, 16, 32, 64$ is going to be especially difficult.

A generalized Fermat number is of the form ${a}^{ {2}^{n} } + {b}^{ {2}^{n} }$ , usually tabulated in the form $a > b>0$ , and there's a whole field of literature on this one subject, i.,e., which ones are primes.

Michael Mendrin - 4 years, 4 months ago

Yes, I was surprised at how much heavy machinery is required to deal with higher powers of $2$ . Complexity is always lurking around the corner in math ....

Brian Charlesworth - 4 years, 4 months ago

According to WolframAlpha, $2^n + 3^n$ is a composite number for $n = 8,\, 16,\, 32$ and $64$ .

Ricardo Moritz Cavalcanti - 9 months, 3 weeks ago

Those numbers are getting awfully big

The answer is 7.

1 solution

0 pending reports