Odd Numbers not Sum of Prime and Power

From ProofWiki
Jump to navigation Jump to search

Theorem

The sequence of odd numbers which cannot be expressed as the sum of a perfect power and a prime number begins:

$1, 5, 1549, 1 \, 771 \, 561, \ldots$

This sequence is A119747 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


It is not known if there are any more terms.


Proof

The cases $1$ and $5$ are trivial.

Now we show that $1549 - a^b$ is never prime for $a \ge 1$ and $b \ge 2$.

It suffices to show the result for prime values of $b$.

We first prove:

\(\text {(1)}: \quad\) \(\ds 2\) \(\divides\) \(\ds a\)
\(\text {(2)}: \quad\) \(\ds 3\) \(\divides\) \(\ds a\) \(\ds \text {if } b = 2\)
\(\text {(3)}: \quad\) \(\ds a^b\) \(\not \equiv\) \(\ds 4\) \(\ds \pmod {10}\)


For $(1)$:

Suppose $a$ is odd.

Then so is $a^b$.

Therefore $1549 - a^b$ is even.

Hence $1549 - a^b$ is prime only if it is equal to $2$.

But $1547$ is not a perfect power.

$\Box$


For $(2)$:

Suppose $b = 2$ and $a$ is not divisible by $3$.

By Corollary to Square Modulo $3$:

$3 \divides \paren {a^2 - 1}$

Hence:

$3 \divides \paren {1548 - a^2 + 1} = 1549 - a^b$

So $1549 - a^b$ is prime only if it is equal to $3$.

But $1546$ is not a perfect square.

$\Box$


For $(3)$:

Suppose $a^b \equiv 4 \pmod {10}$.

Then $1549 - a^b \equiv 5 \pmod {10}$

So $1549 - a^b$ is prime only if it is equal to $5$.

But $1544$ is not a perfect power.

$\Box$


Hence we only need to check the cases:

For $b = 2: \: 6^2, 12^2, 18^2, 24^2, 30^2, 36^2$ since $42^2 > 1549$
For $b \ne 2: \: 2^3, 2^5, 2^7, 4^3, 4^5, 6^3, 8^3, 10^3$ since $2^{11}, 4^7, 6^5 > 1549$

of which $12^2 \equiv 18^2 \equiv 4^3 \equiv 4^5 \equiv 4 \pmod {10}$, so they are rejected.


We have:

\(\ds 1549 - 6^2\) \(=\) \(\ds 1513\)
\(\ds \) \(=\) \(\ds 17 \times 89\)
\(\ds 1549 - 24^2\) \(=\) \(\ds 973\)
\(\ds \) \(=\) \(\ds 7 \times 139\)
\(\ds 1549 - 30^2\) \(=\) \(\ds 649\)
\(\ds \) \(=\) \(\ds 11 \times 59\)
\(\ds 1549 - 36^2\) \(=\) \(\ds 253\)
\(\ds \) \(=\) \(\ds 11 \times 23\)
\(\ds 1549 - 2^3\) \(=\) \(\ds 1541\)
\(\ds \) \(=\) \(\ds 23 \times 67\)
\(\ds 1549 - 2^5\) \(=\) \(\ds 1517\)
\(\ds \) \(=\) \(\ds 37 \times 41\)
\(\ds 1549 - 2^7\) \(=\) \(\ds 1421\)
\(\ds \) \(=\) \(\ds 7^2 \times 29\)
\(\ds 1549 - 6^3\) \(=\) \(\ds 1333\)
\(\ds \) \(=\) \(\ds 31 \times 43\)
\(\ds 1549 - 8^3\) \(=\) \(\ds 1037\)
\(\ds \) \(=\) \(\ds 17 \times 61\)
\(\ds 1549 - 10^3\) \(=\) \(\ds 549\)
\(\ds \) \(=\) \(\ds 3^2 \times 61\)

and none of the above are prime.

$\Box$


For $11^6$, note the factorizations from Difference of Two Powers:

$11^6 - m^2 = \paren {11^3 - m} \paren {11^3 + m}$
$11^6 - n^3 = \paren {11^2 - n} \paren {1 + 11^2 n + 11^4 n^2}$

therefore if $11^6 - a^b$ is a prime, $b$ cannot be divisible by $2$ or $3$, unless $11^3 - m$ or $11^2 - n$ is equal to $1$.

For $m = 11^3 - 1$ and $n = 11^2 - 1$:

$11^6 - m^2 = 2661 = 3 \times 887$
$11^6 - n^2 = 1757161 = 7 \times 173 \times 1451$

and both are not primes.

Hence none of the above cases hold.

$\Box$


Since $\log_2 \paren {11^6} \approx 20.8$, we must have $b \le 19$.

By the conditions above, $b$ can only be one of $5, 7, 11, 13, 17, 19$.

Moreover $a$ cannot be odd unless $11^6 - a^b = 2$.

However $11^6 - 2 = 1771559$ is prime, and thus not a perfect power.

The cases we need to check are:

$a^b = 2^5, 6^5, 10^5, 12^5, 14^5, 2^7, 6^7, 2^{11}, 2^{13}, 2^{17}, 2^{19}$

since $18^5, 10^7, 6^{11} > 11^6$, and $4, 8, 16$ are square/cube.


We have:

\(\ds 11^6 - 2^5\) \(=\) \(\ds 1771529\)
\(\ds \) \(=\) \(\ds 23 \times 77023\)
\(\ds 11^6 - 6^5\) \(=\) \(\ds 1763785\)
\(\ds \) \(=\) \(\ds 5 \times 352757\)
\(\ds 11^6 - 10^5\) \(=\) \(\ds 1671561\)
\(\ds \) \(=\) \(\ds 3^2 \times 79 \times 2351\)
\(\ds 11^6 - 12^5\) \(=\) \(\ds 1522729\)
\(\ds \) \(=\) \(\ds 13 \times 117133\)
\(\ds 11^6 - 14^5\) \(=\) \(\ds 1233737\)
\(\ds \) \(=\) \(\ds 311 \times 3967\)
\(\ds 11^6 - 2^7\) \(=\) \(\ds 1771433\)
\(\ds \) \(=\) \(\ds 31 \times 57143\)
\(\ds 11^6 - 6^7\) \(=\) \(\ds 1491625\)
\(\ds \) \(=\) \(\ds 5^3 \times 11933\)
\(\ds 11^6 - 2^{11}\) \(=\) \(\ds 1769513\)
\(\ds \) \(=\) \(\ds 17 \times 104089\)
\(\ds 11^6 - 2^{13}\) \(=\) \(\ds 1763369\)
\(\ds \) \(=\) \(\ds 41^2 \times 1049\)
\(\ds 11^6 - 2^{17}\) \(=\) \(\ds 1640489\)
\(\ds \) \(=\) \(\ds 31 \times 52919\)
\(\ds 11^6 - 2^{19}\) \(=\) \(\ds 1247273\)
\(\ds \) \(=\) \(\ds 17 \times 73369\)

and none of the above are prime.

$\Box$


This theorem requires a proof.
In particular: In addition to the above, we also need to demonstrate that for $5 < n < 1549$, an odd number does have such an expression.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Odd_Numbers_not_Sum_of_Prime_and_Power&oldid=524637"