2
$\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$
8
  • 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$
    – Jean-Claude Arbaut
    Commented Jun 13, 2018 at 16:52
  • 1
    $\begingroup$ Well, you can notice that $68=4\cdot17$ which makes it easy. $\endgroup$
    – saulspatz
    Commented Jun 13, 2018 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
    Commented Jun 13, 2018 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
    Commented Jun 13, 2018 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
    Commented Jun 13, 2018 at 17:02

3 Answers 3

Reset to default
7
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .