Find the prime factors of $3^{32}-2^{32}$

Question

I'm having a go at BMO 2006/7 Q1 which states: "Find four prime numbers less than 100 which are factors of $3^{32}-2^{32}$."

My working is as follows (basically just follows difference of two squares loads of times):

$$3^{32}-2^{32}$$ $$=(3^{16}+2^{16})(3^{16}-2^{16})$$ $$=(3^{16}+2^{16})(3^{8}+2^{8})(3^{8}-2^{8})$$ $$=(3^{16}+2^{16})(3^{8}+2^{8})(3^{4}+2^{4})(3^{4}-2^{4})$$ $$=(3^{16}+2^{16})(3^{8}+2^{8})(3^{4}+2^{4})(3^{2}+2^{2})(3^{2}-2^{2})$$ $$=(3^{16}+2^{16})(3^{8}+2^{8})(3^{4}+2^{4})(3^{2}+2^{2})(3+2)(3-2)$$ $$=(3^{16}+2^{16})(3^{8}+2^{8})(3^{4}+2^{4})(3^{2}+2^{2})(3+2)$$

Now it is simple to get $3$ of the primes here: $$3+2=5$$ $$3^2+2^2=13$$ $$3^4+2^4=97$$

Now I was having some trouble with finding the fourth prime. It's clear that the fourth prime must either be a prime factor of $3^8+2^8$ or $3^{16}+2^{16}$. I started off with $3^8+2^8$:

$$3^8+2^8$$ $$=3^{4^2}+256$$ $$=81^2+256$$ $$=6561+256$$ $$=6817$$

Here is where I am stuck because google tells me that $6817=17*401$ and so the fourth prime is $17$. But this is a non-calculator paper so is there a way of working out this answer without working out $\frac{6817}{3},\frac{6817}{7},\frac{6817}{11}$ etc until one of them is an integer solution?

Finally, before anyone says this is a duplicate, there is a similar question here (prime factors of $3^{32}-2^{32}$) that I didn't know existed until writing this question. However, none of those answers give a way of finding $17$ without using any computational methods. So are they just expecting you to essentially do trial and error throughout all of the primes under $100$ until one works?

Answer 1

Apply Fermat's little theorem:

$17$ is prime, so

$$3^{16}\equiv1\pmod{17}$$ $$2^{16}\equiv1\pmod{17}$$

Answer 2

Note that $\forall a \perp p, a^{p-1\over2} \equiv \pm 1 \pmod p$

2 and 3 are already coprime to the other primes you're looking for. $8*2+1=17$ is a strong candidate. In fact, it is the only strong candidate for this method of attack.

Answer 3

I checked this in Python and there are only 4 such primes, $5$, $13$, $17$ and $97$. As has been noted, FLT implies $17$ is such a prime, and we can get $5$ the same way. We also get $13$ as a prime factor of $3^4-2^4$, and $97$ as a prime factor of $3^8-2^8$.

In the timed conditions of an olympiad, it helps to first seek prime factors of $3^2-2^2$, then the remaining prime factors of $3^4-2^4$ (i.e. those of $3^2+2^2$) etc. In particular $5=3^2-2^2,\,13=3^2+2^2,\,97=3^4+2^4,\,17\times 401=3^8+2^8$.