2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ A related question. :-) $\endgroup$ – Lucian Sep 19 '14 at 4:36
13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – mar10 Sep 19 '14 at 7:31
  • $\begingroup$ That is one correct way to show that $2^{8420}-9$ is not prime, but of course, there are other ways as well. $\endgroup$ – JimmyK4542 Sep 19 '14 at 17:29
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.