2003 IMO Problems/Problem 6

Problem

Let $p$ be a prime number. Prove that there exists a prime number $q$ such that for every integer $n$ , the number $n^p-p$ is not divisible by $q$ .

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

Let N be $1 + p + p^2 + ... + p^{p-1}$ which equals $\frac{p^p-1}{p-1}$ $N\equiv{p+1}\pmod{p^2}$ Which means there exists q which is a prime factor of n that doesn't satisfy $q\equiv{1}\pmod{p^2}$ . \unfinished

Solution 2

For $p$ prime and $gcd(n, p) = 1$ , $n^{p}\equiv{n}\pmod{p}$ simply by Fermat's Little Theorem. Therefore, $n^{p} - p \equiv{n}\pmod{p}$ . We are going to prove by contradiction. Let $q$ be a prime that divides $n^{p} - p$ . If $q$ divides this quantity, then it must also divide $pk + n$ . But on the other hand, clearly $p$ doesn't divide this quantity. $p$ is a prime and so is $q$ . If $p$ doesn't divide this, then no other prime should divide $n^{p} - p$ so we have proved the problem statement is true for $gcd(n, any prime) = 1$ . Now, consider the case where $gcd(n, p) = p$ . Then, $n^{p} - p = p^{p}*k^{p} - p$ which is divisible by $p$ . Notice $n^{p} = p^{p}*k^{p}$ . This has $(p + 1)^{2}$ factors if $k$ is prime. We assumed that $q$ also divided this original quantity. If $q$ divided this quantity, then the expression must have at most $4$ factors: $1, p , q, pq$ . In fact, since $p$ is prime, $(p + 1)^{2}$ is at least $9$ meaning this tends towards the claim that we must have at least $9$ factors. But this is absurd! So we have proved the problem statement is true if $k$ is prime. If $k$ isn't prime, then by inspection, we will have way more than $9$ factors, and by similar logic, $q$ cannot divide the above quantity. Therefore, we are done.

(This is my first IMO problem 6 and the solution is probably all wrong. If someone can correct my solution mistake(s), feel free to edit my solution or put down comments.)

2003 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Problem
All IMO Problems and Solutions

Page

Toolbox

Search

2003 IMO Problems/Problem 6

Contents