1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Well, you have only three primes to actually try ($3$ is obviously not a divisor). Of course, you don't know that beforehand. And you have only to try up to $79$, since $\sqrt{6817}<83$. $\endgroup$ – StayHomeSaveLives Jun 13 '18 at 16:52
  • 1
    $\begingroup$ Well, you can notice that $68=4\cdot17$ which makes it easy. $\endgroup$ – saulspatz Jun 13 '18 at 16:52
  • $\begingroup$ Yes I know I would reach the solution of $17$ quite quickly but that isn't really my point. I just wouldn't expect BMO to give something that essentially requires trial and error $\endgroup$ – Dan Jun 13 '18 at 16:53
  • $\begingroup$ @saulspatz ah yes that's a very good way of thinking about it. Is that what they would expect from you though or is there some kind of method they would want you to use? $\endgroup$ – Dan Jun 13 '18 at 16:55
  • 1
    $\begingroup$ Since $17$ is a prime, Fermat's little theorem tell us $2,3 \not| 17 \implies 2^{16} \equiv 3^{16} \equiv 0 \pmod 17$. One thing one can try is looking for prime of the form $2^k + 1$ for $k \le 5$, you immediate get $5$ and $17$. $\endgroup$ – achille hui Jun 13 '18 at 17:02
5
$\begingroup$

Apply Fermat's little theorem:

$17$ is prime, so

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.