Prove that $\frac{2^{122}+1}{5}$ is a composite number

As in the title. It's very easy to show that $5|2^{122}+1$, but what should I do next to show that $\frac{2^{122}+1}{5}$ is a composite number? I'm looking for hints.

Solution 1:

Suppose a prime $p$ divides $2^{122} + 1$. This means exactly that $2^{122} \equiv -1 \bmod p$. In particular, $2^{244} \equiv 1 \bmod p$ but $2^{122} \not \equiv 1 \bmod p$, which means (if $p \neq 2$, which is clear) that $2$ has order dividing $244$ but not dividing $122$ in the multiplicative group $\mathbb{F}_p^{\times}$. The orders with this property are $244$ and $4$. In the latter case,

$$2^{122} \equiv 2^2 \equiv 4 \equiv -1 \bmod p$$

implies that $p = 5$. In the former case, since $\mathbb{F}_p^{\times}$ has order $p - 1$, it follows that $244$ must divide $p - 1$; equivalently,

$$p \equiv 1 \bmod 244.$$

So when you search for primes dividing $2^{122} + 1$ other than $5$, you can restrict your attention to primes congruent to $1 \bmod 244$. The sequence of positive integers congruent to $1 \bmod 244$ begins

$$1, 245, 489, 733, \dots$$

and of these $5 \mid 245, 3 \mid 489$, and $733$ is prime (by trial division). From here you just need to compute $2^{122} \bmod 733$, e.g. using binary exponentiation. This isn't so bad, especially if you write it as $2^{2^7 - 4 - 2}$.

This is a special case of a more general fact about the cyclotomic polynomials $\Phi_n(x)$, which is that all primes dividing $\Phi_n(a)$ are congruent to $1 \bmod n$. Here $n = 244$ and $\Phi_{244}(2) = \frac{2^{122} + 1}{5}$. This observation can be used to prove that there are infinitely many such primes without using Dirichlet's theorem.

Solution 2:

$$1+2^{122}=\left(1+2^{61}\right)^2-\left(2^{31}\right)^2$$

$$=\left(1+2^{61}+2^{31}\right)\left(1+2^{61}-2^{31}\right)$$

Both factors are larger than $5$, also $$2^{122}\equiv \left(2^4\right)^{30}\cdot 2^2\equiv (1)^{30}\cdot 2^2\equiv -1\pmod{5},$$ so your result follows.

More generally, the following is called the Sophie-Germain identity (for all $a,b\in\mathbb R$):

$$a^4+4b^4=\left(a^2+2b^2\right)^2-\left(2ab\right)^2$$

$$=\left(a^2+2b^2+2ab\right)\left(a^2+2b^2-2ab\right)$$

The following factorization is a Aurifeuillean factorization (for all $k\in\mathbb R$):

$$2^{4k+2}+1=\left(2^{2k+1}-2^{k+1}+1\right)\left(2^{2k+1}+2^{k+1}+1\right)$$

Some other Aurifeuillean factorizations (not related to the Sophie-Germain identity):

$$3^{6k+3}+1=\left(3^{2k+1}+1\right)\left(3^{2k+1}-3^{k+1}+1\right)\left(3^{2k+1}+3^{k+1}+1\right)$$

$$5^{10k+5}-1=\left(5^{2k+1}-1\right)\left(5^{4k+2}+5^{3k+2}+3\cdot 5^{2k+1}+5^{k+1}+1\right)\times$$

$$\times \left(5^{4k+2}-5^{3k+2}+3\cdot 5^{2k+1}-5^{k+1}+1\right)$$

$$6^{12k+6}+1=\left(6^{4k+2}+1\right)\left(6^{4k+2}+6^{3k+2}+3\cdot 6^{2k+1}+6^{k+1}+1\right)\times$$

$$\times \left(6^{4k+2}-6^{3k+2}+3\cdot 6^{2k+1}-6^{k+1}+1\right)$$

There are a lot more of these on the Wikipedia page about Aurifeuillean factorization.

Solution 3:

$2^{122}+1=(2^{61}+2^{32}+1)*(2^{61}-2^{32}+1)$

This is a gaussian factorisation based on $(2x²+2x+1)(2x²-2x+1)=4x^4+1$.

The first of these is a multiple of $5$.

In fact, the gaussian factors (in any base) divide the algebraic roots they are meant to into two divisors, and the same divisors always appear in the same side (here multiple of $5$ vs non-multiple of $5$). So eg we always find $29$ in the $5$ factor, and $113$ opposite it.