Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2003 IMO Problems/Problem 6"

(→‎Solution)
(→‎Solution 2)
 
(6 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
== Problem ==
 
== Problem ==
−
p is a prime number. Prove that for every p there exists a q for every positive integer n, so that <math>n^p-p</math> can't be divided by q.
+
Let <math>p</math> be a prime number. Prove that there exists a prime number <math>q</math> such that for every integer <math>n</math>, the number <math>n^p-p</math> is not divisible by <math>q</math>.
  
 
== Solution ==
 
== Solution ==
Line 11: Line 11:
 
Which means there exists q which is a prime factor of n that doesn't satisfy <math>q\equiv{1}\pmod{p^2}</math>.
 
Which means there exists q which is a prime factor of n that doesn't satisfy <math>q\equiv{1}\pmod{p^2}</math>.
 
\\unfinished
 
\\unfinished
 +
 +
== Solution 2 ==
 +
 +
For <math>p</math> prime and <math>gcd(n, p) = 1</math>, <math>n^{p}\equiv{n}\pmod{p}</math> simply by Fermat's Little Theorem. Therefore, <math>n^{p} - p
 +
\equiv{n}\pmod{p}</math>. We are going to prove by contradiction. Let <math>q</math> be a prime that divides <math>n^{p} - p</math>. If <math>q</math> divides this quantity, then it must also divide <math>pk + n</math>. But on the other hand, clearly <math>p</math> doesn't divide this quantity. <math>p</math> is a prime and so is <math>q</math>. If <math>p</math> doesn't divide this, then no other prime should divide <math>n^{p} - p</math> so we have proved the problem statement is true for <math>gcd(n, any prime) = 1</math>.
 +
Now, consider the case where <math>gcd(n, p) = p</math>. Then, <math>n^{p} - p = p^{p}*k^{p} - p</math> which is divisible by <math>p</math>. Notice <math>n^{p} = p^{p}*k^{p}</math>. This has <math>(p + 1)^{2}</math> factors if <math>k</math> is prime. We assumed that <math>q</math> also divided this original quantity. If <math>q</math> divided this quantity, then the expression must have at most <math>4</math> factors: <math>1, p , q, pq</math>. In fact, since <math>p</math> is prime, <math>(p + 1)^{2}</math> is at least <math>9</math> meaning this tends towards the claim that we must have at least <math>9</math> factors. But this is absurd! So we have proved the problem statement is true if <math>k</math> is prime.
 +
If <math>k</math> isn't prime, then by inspection, we will have way more than <math>9</math> factors, and by similar logic, <math>q</math> 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.)
  
 
==See Also==
 
==See Also==
 
{{IMO box|year=2003|num-b=5|after=Last Problem}}
 
{{IMO box|year=2003|num-b=5|after=Last Problem}}

Latest revision as of 21:22, 29 March 2025

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

See Also

2003 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Problem
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_IMO_Problems/Problem_6&oldid=246249"