## IMO 1999-4

Discussion on International Mathematical Olympiad (IMO)
Posts: 244
Joined: Sat May 07, 2011 12:36 pm
Location: B.A.R.D , kotbari , Comilla

### IMO 1999-4

Find all pairs of positive integer $(n,p)$ such that
$(i)$ . $p$ is a prime number
$(ii)$ . $n \leq2p$
$(iii)$ . $n^{p-1}$ divides $(p-1)^n+1$
$\frac{1}{0}$

FahimFerdous
Posts: 176
Joined: Thu Dec 09, 2010 12:50 am

### Re: IMO 1999-4

Small Hint:

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### Re: IMO 1999-4

Nadim Ul Abrar wrote:Find all pairs of positive integer $(n,p)$ such that
$(i)$ . $p$ is a prime number
$(ii)$ . $n \leq2p$
$(iii)$ . $n^{p-1}$ divides $(p-1)^n+1$
Firstly, it is a generalization of $IMO-1990, 3$.
আমার মনে হয় এই ধরনের প্রব্লেম এ সবার আগেই $LTE$ আর special primes এর কথা মনে করা উচিত। special primes মানে হচ্ছে যে prime গুলা নিয়ে কাজ করলে তাদের মান পাওয়া যায়। যেমন smallest prime factors or some arbitrary prime factors of $n$.
In this case, assume $q$ to be the smallest prime factor of $n$. Now if $p$ even, then we easily get $n|2\Rightarrow n=1,2$. Let's assume $n>1$ and odd. Then, $(p-1)^{2n}\equiv1\pmod q$
Also, $q|(p-1)^n+1$ easily shows $q$ is co-prime to $p-1$. Therefore, $(p-1)^{q-1}\equiv1\pmod q$
$(p-1)^{\gcd(2n, q-1)}\equiv1\pmod q$
Since $q$ is the smallest prime factor of $n$, every prime factor of $q-1$ is co-prime to $n$. Hence, $\gcd(2n,q-1)=\gcd(2,q-1)=2$. $(p-1)^2\equiv1\pmod q$
So we get $q|p-1+1$ or $q|p-1-1$ since $q$ is a prime(otherwise we could hardly conclude that). If $q|(p-1)-1$ then $q|(p-1)^n-1\Rightarrow q|2\Rightarrow q=2$. But this leaves a contradiction.
Thus, $q|p$ and so, $p=q$. Now, see the maximum powers of $p$ in both side to get the value of $p$. Assume $\nu_p(n)=\alpha$.
$\nu_p(n^{p-1})=(p-1)\alpha$
$\nu_p((p-1)^n+1)=\alpha+1$
Invoking $LTE$, $(p-1)\alpha\le \alpha+1$
$\Rightarrow (p-2)\alpha\le1$
which would be false for $p>3$. Hence, $p=3,\alpha=1$, $n=3k$. So we are reduced to $n^2|2^n+1$
We get $k^2|8^k+1$
Next assume $r$ to be the smallest prime factor of $k$. In a similar manner we did to find $p$, $8^2\equiv1\pmod r$
And since $3\not|q$, it must be $q=7$. On the other hand, $8^k+1\equiv2\pmod7$. This implies a contradiction. So, we can't have a $k$ such that $k$ has a prime factor. Thus, $k=1$ and then $n=3$
One one thing is neutral in the universe, that is $0$.

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### Re: IMO 1999-4

But I hardly believe that this problem is worth $4$-th place.
One one thing is neutral in the universe, that is $0$.

Posts: 244
Joined: Sat May 07, 2011 12:36 pm
Location: B.A.R.D , kotbari , Comilla

### Re: IMO 1999-4

Masum vaia , first time i did it in your way , But after solving the problem I noticed that " i haven't used the condition $(ii)$" . Using this we can prove that $k=1$ in $1$ line . Thanks .
$\frac{1}{0}$

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
One one thing is neutral in the universe, that is $0$.