Maths Olympiad Prep

Library / /2 of 16

Number theory Difficulty 5.2 AIME, harder Prove it JBMO

Problem:
Determine the largest positive integer nn that divides p61p^{6}-1 for all primes p>7p>7.

Solution

Solution:
Note that
p61=(p1)(p+1)(p2p+1)(p2+p+1) p^{6}-1=(p-1)(p+1)\left(p^{2}-p+1\right)\left(p^{2}+p+1\right)
For p=11p=11 we have
p61=1771560=2332571937 p^{6}-1=1771560=2^{3} \cdot 3^{2} \cdot 5 \cdot 7 \cdot 19 \cdot 37
For p=13p=13 we have
p61=2332761157 p^{6}-1=2^{3} \cdot 3^{2} \cdot 7 \cdot 61 \cdot 157
From the last two calculations we find evidence to try showing that p61p^{6}-1 is divisible by 23327=5042^{3} \cdot 3^{2} \cdot 7=504 and this would be the largest positive integer that divides p61p^{6}-1 for all primes greater than 7.
By Fermat's theorem, 7p617 \mid p^{6}-1.
Next, since pp is odd, 8p21=(p1)(p+1)8 \mid p^{2}-1=(p-1)(p+1), hence 8p618 \mid p^{6}-1.
It remains to show that 9p619 \mid p^{6}-1.
Any prime number p,p>3p, p>3 is 1 or -1 modulo 3.
In the first case both p1p-1 and p2+p+1p^{2}+p+1 are divisible by 3, and in the second case, both p+1p+1 and p2p+1p^{2}-p+1 are divisible by 3.
Consequently, the required number is indeed 504

Let qq be a (positive) prime factor of nn. Then q7q \leq 7, as qq61q \nmid q^{6}-1. Also, qq is not 5, as the last digit of 136113^{6}-1 is 8.
Hence, the prime factors of nn are among 2, 3, and 7.
Next, from 1161=233257193711^{6}-1=2^{3} \cdot 3^{2} \cdot 5 \cdot 7 \cdot 19 \cdot 37 it follows that the largest integer nn such that np61n \mid p^{6}-1 for all primes pp greater than 7 is at most 233272^{3} \cdot 3^{2} \cdot 7, and it remains to prove that 504 divides p61p^{6}-1 for all primes greater than 7.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.