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 "1999 IMO Problems/Problem 4"
(→‎Solution)
 
Line 9: Line 9:
 
Clearly we have the solutions <math>(1,p)</math> and <math>(2,2)</math>, and for every other solution <math>p \geq 3</math>. It remains to find the solutions <math>(x,p)</math> with <math>x \geq 2</math> and <math>p \geq 3</math>. We claim that in this case <math>x</math> is divisible by p and <math>x y 2p</math>, whence <math>x = p</math>. This will lead to
 
Clearly we have the solutions <math>(1,p)</math> and <math>(2,2)</math>, and for every other solution <math>p \geq 3</math>. It remains to find the solutions <math>(x,p)</math> with <math>x \geq 2</math> and <math>p \geq 3</math>. We claim that in this case <math>x</math> is divisible by p and <math>x y 2p</math>, whence <math>x = p</math>. This will lead to
  
−
\[p^{p-1}|(p-1)^{p}+1=p^{2}\left(p^{p-2}-{p \choose 1}p^{p-3}+
+
<math>\[p^{p-1}|(p-1)^{p}+1=p^{2}\left(p^{p-2}-{p \choose 1}p^{p-3}+
−
\cdots + -{p \choose p-3}p-{p \choose p-2}+1\right)\]
+
\cdots + -{p \choose p-3}p-{p \choose p-2}+1\right)\]</math>
  
 
therefore, because all the terms in the brackets excepting the last one is divisible by <math>p</math>,<math>p-1 \leq 2</math>. This leaves only <math>p=3</math> and <math>x=3</math>. Let us prove now the claim. Since <math>(p-1)^{x}+1</math> is odd, so is <math>x</math> (therefore <math>x < 2p</math>). Denote by q the smallest prime divisor of <math>x</math>. <math>q|(p-1)^{x}+1</math> we get <math>(p-1)^{x} \equiv -1 \pmod {q}</math> and <math>(q,p-q)=1</math>. But <math>(x,p-q)=1</math> (from the choice of q) leads to the existence of integers <math>u,v</math> such that <math>ux+v(q-1)=1</math>, whence <math>p-1 \equiv (p-1)^{ux}</math>. <math>(p-1)^{v(q-1)} \equiv (-1)^{u} \cdot 1^{v} \equiv -1 \pmod {q}</math>, because <math>u</math> must be odd. This shows that <math>q|p</math>, therefore <math>q=p</math>. In conclusion the required solutions are <math>(2,2), (3,3)</math> and <math>(1,p)</math>, where <math>p</math> is an arbitrary prime.
 
therefore, because all the terms in the brackets excepting the last one is divisible by <math>p</math>,<math>p-1 \leq 2</math>. This leaves only <math>p=3</math> and <math>x=3</math>. Let us prove now the claim. Since <math>(p-1)^{x}+1</math> is odd, so is <math>x</math> (therefore <math>x < 2p</math>). Denote by q the smallest prime divisor of <math>x</math>. <math>q|(p-1)^{x}+1</math> we get <math>(p-1)^{x} \equiv -1 \pmod {q}</math> and <math>(q,p-q)=1</math>. But <math>(x,p-q)=1</math> (from the choice of q) leads to the existence of integers <math>u,v</math> such that <math>ux+v(q-1)=1</math>, whence <math>p-1 \equiv (p-1)^{ux}</math>. <math>(p-1)^{v(q-1)} \equiv (-1)^{u} \cdot 1^{v} \equiv -1 \pmod {q}</math>, because <math>u</math> must be odd. This shows that <math>q|p</math>, therefore <math>q=p</math>. In conclusion the required solutions are <math>(2,2), (3,3)</math> and <math>(1,p)</math>, where <math>p</math> is an arbitrary prime.

Latest revision as of 06:18, 17 July 2025

Problem

Determine all pairs $(n,p)$ of positive integers such that

$p$ is a prime, $n$ not exceeded $2p$, and $(p-1)^{n}+1$ is divisible by $n^{p-1}$

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it. official solution Clearly we have the solutions $(1,p)$ and $(2,2)$, and for every other solution $p \geq 3$. It remains to find the solutions $(x,p)$ with $x \geq 2$ and $p \geq 3$. We claim that in this case $x$ is divisible by p and $x y 2p$, whence $x = p$. This will lead to

$\[p^{p-1}|(p-1)^{p}+1=p^{2}\left(p^{p-2}-{p \choose 1}p^{p-3}+ \cdots + -{p \choose p-3}p-{p \choose p-2}+1\right)\]$ (Error compiling LaTeX. Unknown error_msg)

therefore, because all the terms in the brackets excepting the last one is divisible by $p$,$p-1 \leq 2$. This leaves only $p=3$ and $x=3$. Let us prove now the claim. Since $(p-1)^{x}+1$ is odd, so is $x$ (therefore $x < 2p$). Denote by q the smallest prime divisor of $x$. $q|(p-1)^{x}+1$ we get $(p-1)^{x} \equiv -1 \pmod {q}$ and $(q,p-q)=1$. But $(x,p-q)=1$ (from the choice of q) leads to the existence of integers $u,v$ such that $ux+v(q-1)=1$, whence $p-1 \equiv (p-1)^{ux}$. $(p-1)^{v(q-1)} \equiv (-1)^{u} \cdot 1^{v} \equiv -1 \pmod {q}$, because $u$ must be odd. This shows that $q|p$, therefore $q=p$. In conclusion the required solutions are $(2,2), (3,3)$ and $(1,p)$, where $p$ is an arbitrary prime.

See Also

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