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$
IMO 1999-4
- Nadim Ul Abrar
- Posts:244
- Joined:Sat May 07, 2011 12:36 pm
- Location:B.A.R.D , kotbari , Comilla
$\frac{1}{0}$
- FahimFerdous
- Posts:176
- Joined:Thu Dec 09, 2010 12:50 am
- Location:Mymensingh, Bangladesh
Re: IMO 1999-4
Firstly, it is a generalization of $IMO-1990, 3$.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$
আমার মনে হয় এই ধরনের প্রব্লেম এ সবার আগেই $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$.
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$.
- Nadim Ul Abrar
- 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}$
Re: IMO 1999-4
আমি ও তো ওইটা না ব্যবহার করি নাই। ভুলেই গেছিলাম ওইটার কথা। আসলে ওইটার কোন দরকার নাই। এম্নিতেই দেওয়া হইছে।
One one thing is neutral in the universe, that is $0$.