IMO 1999-4

[Nadim Ul Abrar]

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$

[FahimFerdous]

Small Hint:

Working with largest or smallest prime divisor often helps. And try to find co prime numbers.

[Masum]

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$

[Masum]

But I hardly believe that this problem is worth $4$-th place.

[Nadim Ul Abrar]

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 .

[Masum]

আমি ও তো ওইটা না ব্যবহার করি নাই। ভুলেই গেছিলাম ওইটার কথা। আসলে ওইটার কোন দরকার নাই। এম্নিতেই দেওয়া হইছে।