Prime factoring $2^{22} + 1$ the sneaky way? As the title suggests, how to prime factorize $2^{22} + 1$ without any excessively long computation? There has got to be some trick here. I know that the expression can be factored as$$(2^2 + 1)(2^{20} - 2^{18} + 2^{16} - 2^{14} + \ldots - 2^2 + 1).$$But not sure where to go from here.
 A: $22=4\cdot5+2$, so $2^{22}+1$ has an Aurifeuillean factorisation:
$$2^{22}+1=(2^{11}-2^6+1)(2^{11}+2^6+1)=1985×2113$$
The numbers are now within the point where trial division with primes up to $97$ will easily find all factors. In fact, other than the $5$ that appears with the naive factorisation, these are the only prime factors:
$$2^{22}+1=5×397×2113$$
A: It is well known that $2048 = 2^{11}$, by the famous game 2048, so I won't count that as "excessively long computation".
So $2^{22}+1=4194305$. You've already got a factor $5$: $$2^{22}+1 = 5\times838861.$$
Now to find other factors of $2^{22}+1$, you need to know which primes $p$ satisfies $$2^{22}\equiv -1 \pmod p.$$ So let's tackle the easier: $$2^{44}\equiv 1 \pmod p.$$ This is likely to happen when $p = 44k + 1$. And $k \equiv 0,2 \pmod 3$ to make $p$ a prime. And we have the fast exponentiation algorithm that enables us to quickly find $2^{44}$ modulo a number, taking $k=9$ as an example:
$$\begin{align}
2^{44} &\equiv 4^{22}\\
&\equiv 16^{11}\\
&\equiv (-141)^{5} \times 16 \\
&\equiv 31^{2} \times 16 \times (-141)\\
&\equiv 167 \times 16 \times (-141)\\
&\equiv -290 \times 141 \\
&\equiv 1 \pmod 397
\end{align}$$
This says $397 \mathop{|} 2^{44}-1$, so possibly $397 \mathop{|} 2^22+1$. And by division we see that it is indeed the case. $$2^{22} + 1 = 5 \times 397 \times 2113.$$
And 2113 is prime.
