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.

$$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.
