Find two primes less than $500$ that divide $20^{22}+1$.
Note that $20^2+1=401$ divides the required number (since for any integer a, if k is odd, then $a+1$ divides $a^k+1$). Also, any prime dividing the given number must be congruent to $1$ modulo $4$ since $-1$ would be a quadratic residue modulo any such prime. Primes like $17$ and $13$ don't work. $20\equiv 7\mod 13, 20\equiv 3\mod 17,$ and in both cases $20$ is a primitive root with respect to the corresponding modulus. So it might be that we'll need to find a large prime. $a^k+1 = (a+1)(a^{(k-1)} – a^{(k-2)}+\cdots + 1),$ where $a = 20^2, k=11.$ I'm not sure if there's some way to factor $a^{(k-1)} -a^{(k-2)}+\cdots + 1.$
Best Answer
Suppose a prime $p$ (necessarily odd) divides $20^{22} + 1$. Then $20^{22} \equiv -1 \bmod p$ so $20^{44} \equiv 1 \bmod p$ and it follows that the order of $20 \bmod p$ divides $44$ but does not divide $22$. This means it must be divisible by $4$, so must be either $4$ or $44$. If $20^4 \equiv 1 \bmod p$ then $20^{22} \equiv 20^2 \equiv -1 \bmod p$ so we conclude that $p \mid 401$ and hence $p = 401$. Otherwise the order of $20 \bmod p$ is $44$, from which it follows that $p \equiv 1 \bmod 44$.
The smallest such prime is $p = 89$, and we have
$$\begin{align*} 20^{22} &= 400^{11} \equiv 44^{11} \\ & \equiv \left( \frac{89 - 1}{2} \right)^{11} \equiv \left( - \frac{1}{2} \right)^{11} \\ & \equiv - \frac{1}{32 \cdot 64} \equiv \frac{1}{32 \cdot 25} \\ & \equiv \frac{1}{800} \equiv - \frac{1}{90} \\ & \equiv - 1 \bmod 89 \end{align*} $$
so $p = 89$ works. This is a slightly annoying computation, though, so I don't know if it was what was intended. There were only three primes to check, namely $p = 89, 353, 397$ although if $89$ hadn't worked generating the rest of this list would've been slightly annoying and checking it would've been slightly annoying too, I think.