Competition problem — Number theory

Library / /50 of 133

Number theory Difficulty 5.4 AIME, harder Prove it Saudi Arabia

Let $p$ be a prime number and $n \geq 2$ a positive integer, such that $p \mid (n^{6}-1)$ . Prove that $n > \sqrt{p} - 1$ .

Solution

Because $p$ is prime and divides
$n^{6}-1 = (n-1)(n+1)(n^{2}-n+1)(n^{2}+n+1),$
it divides at least one of these positive factors. The prime number $p$ is therefore less or equal to at least one of these factors. Because
$n-1 < n+1 \leq (n-1)n+1 = n^{2}-n+1 < n^{2}+n+1 < (n+1)^{2},$
we have $p < (n+1)^{2}$ and therefore $\sqrt{p} - 1 < n$ .

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 and solution reproduced as published; topic and difficulty added by this site.