43
$\begingroup$

Prove that $2^{218!} +1$ is not a prime number.

I can prove that the last digit of this number is $7$, and that's all.

Thank you.

$\endgroup$
  • 16
    $\begingroup$ What I love in elementary number theory questions is that you can tweak parameters so easily to make it computationally infeasible; but the proofs, once you know the method, are about the same. $\endgroup$ – Asaf Karagila Apr 10 '13 at 11:56
  • 11
    $\begingroup$ See the theorem here: $2^n+1$ prime implies $n=2^k$. Such primes are called Fermat primes. Interestingly, it is not knwon whether there are infinitely many Fermat primes, and the only ones known are $F_0,F_1,F_2,F_3,F_4$, where $F_k=2^{2^k}+1$. $\endgroup$ – Julien Apr 10 '13 at 12:14
77
$\begingroup$

$$218!=3n:\;\;\;2^{218!}+1=(2^{n}+1)(4^{n}-2^{n}+1)$$

$\endgroup$
45
$\begingroup$

Well, $a^3+1=(a+1)(a^2-a+1)$, so it's not prime, and we have $$2^{218!}=(2^{2\cdot4\cdot5\cdot..\cdot 218})^3\,.$$

$\endgroup$
  • 7
    $\begingroup$ Everybody took the $3$ out, but it also works with any odd exponent, as in general $a+1\,|\,a^m+1$ if $m$ is odd. $\endgroup$ – Berci Apr 10 '13 at 12:14
12
$\begingroup$

$x=1 \cdot 2 \cdot 4 \cdot 5 \dots 218$

$2^{218!}+1 =2^{3x}+1=(2^{x}+1)(2^{2x}-2^{x}+1)$

$\endgroup$
  • $\begingroup$ I think you want the $+1$ out the exponent there, since the left side is odd. $\endgroup$ – Thomas Andrews Apr 10 '13 at 12:23
  • 8
    $\begingroup$ Oh, cruel math world. One typo and a 5 seconds late of proof delivery costs 400 karma. $\endgroup$ – igumnov Apr 10 '13 at 16:39
  • $\begingroup$ @igf Don't worry about it too much, Stack Exchange sites cap you at a maximum of 200 rep gain per day. $\endgroup$ – Hooked Apr 10 '13 at 19:02
5
$\begingroup$

Another one: $2^{2^{213}}+1\mid2^{218!}+1$ because $218!=2^{213}\cdot k$ with $k$ odd.

$\endgroup$
5
$\begingroup$

Hint $\ $ If $\rm\: k\:$ is odd then $\rm\:a^n\!+\!1\mid a^{nk}\!+\!1\ $ by $\rm\ mod\ a^n\!+\!1\!:\ a^n\!\equiv -1\:\Rightarrow\:a^{nk}\!\equiv (a^n)^k\!\equiv (-1)^k\equiv -1.\:$

Or $ $ Factor Theorem $\rm\:\Rightarrow\: x\!-\!c\mid x^k\!-\!c^k\: $ in $\rm\:\Bbb Z[x],\:$ so $\rm\:c=-1\:\Rightarrow\: x\!+\!1\mid x^k\!+\!1,\:$ hence evaluating at $\rm\:x = a^n\:$ yields $\rm\:a^n\!+\!1\mid a^{nk}\!+\!1\:$ in $\,\Bbb Z.\:$ Thus this integer divisibility results is a special case of a polynomial divisibility result. Factors of this form are sometimes called algebraic factors.

Similar to the example above, often number identities are more perceptively viewed as special cases of function or polynomial identities. $ $ For example, $ $ Aurifeuille, Le Lasseur and Lucas $ $ discovered so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x)\, =\, C_n(x)^2\! - n\, x\, D_n(x)^2\;$. These play a role in factoring integers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations.

$$\begin{eqnarray} \rm x^4 + 2^2 &=\,&\rm (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\\\ \rm \frac{x^6 + 3^3}{x^2 + 3} &=\,&\rm (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\\\ \rm \frac{x^{10} - 5^5}{x^2 - 5} &=\,&\rm (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\\\ \rm \frac{x^{12} + 6^6}{x^4 + 36} &=\,&\rm (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \\\\ \end{eqnarray}$$

For more on this and related topics see Sam Wagstaff's introduction to the Cunningham Project.

$\endgroup$
3
$\begingroup$

In general, we the following to be true.

Claim:

If $a^n+1$ is a prime, then $n = 2^k$. To put it the other way around: If $n = 2^k \cdot m$, where $m$ is odd and greater than $1$, $a^n+1$ is composite.

Proof:

Let $k$ be the highest power of $2$ such that $2^k \vert n$, i.e., $2^k \Vert n$. We then have $n = 2^k \cdot m$, where $m$ is odd. Hence, we have $$a^n+1 = a^{2^k \cdot m} + 1 = \left(a^{2^k}\right)^m + 1$$ Now we have $$b + 1 \vert b^m+1$$whenever $m$ is odd. Hence, we have $$a^{2^k}+1 \vert \left(a^{2^k}\right)^m + 1 \implies a^{2^k}+1 \vert a^n+1$$ Hence, if $m \neq 1$, we have $a^n+1 > a^{2^k}+1$ and $a^{2^k}+1 \vert a^n+1$. Hence, if $m \neq 1$, we get that $a^n+1$ is not a prime. This forces $m$ to $1$. Hence, if $a^n+1$ is a prime, then $n = 2^k$.


In your case, take $a=2$ and $n = 218!$ and clearly (Why?) $218! \neq 2^k$, where $k \in \mathbb{Z}^+$. Hence, $2^{218!}+1$ is not a prime.

$\endgroup$
0
$\begingroup$

$$218! \equiv 0 \mod \left( \left\{3,5,7,9,11,13,15,...,217!! \right\}\right)$$

$$\left(2^{\frac {218!}{2k+1}} \right)^{2k+1}+1 \equiv 0 \left(\mod 2^{\frac {218!}{2k+1}}+1 \right)$$, where $k≤\frac {217!!+1}{2} .$

$\endgroup$