# $2^{8420} - 9$ is prime or not

How to prove $2^{8420} - 9$ is or isn't a prime number?

I tried modding it by 10 to get the last digit, but that's a 7 which doesn't help.

We've only been covering successive squaring in this chapter (and modular arithmetic).

• A related question. :-) – Lucian Sep 19 '14 at 4:36

Hint: Use the factorization $a^2-b^2 = (a-b)(a+b)$ for a useful choice of values for $a$ and $b$.

When you do this, it should be fairly obvious that both factors are bigger than $1$.

• 2^(8420) = 2^(2*4210)(2^4210)^2 and 2^(8420) - 9 = (2^4210)^2 - 3^2 = (2^4210-3)(2^4210+3) ... So this shows I have found 2 factors that are not the number itself and 1. Proving that this number is not prime. Is this the most correct way to show this? – mar10 Sep 19 '14 at 7:31
• That is one correct way to show that $2^{8420}-9$ is not prime, but of course, there are other ways as well. – JimmyK4542 Sep 19 '14 at 17:29

The number is a multiple of $13$ because $2^{12} \equiv 1 \bmod 13$, $8240 \equiv 8 \bmod 12$, and $2^8 \equiv 9 \bmod 13$.

• The smallest prime factors of $2^{8420} - 9$ are $13$, $21649$, $2201539$, ... – lhf Sep 19 '14 at 4:48