IMO 1999-4

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

IMO 1999-4

Unread post by Nadim Ul Abrar » Thu Mar 29, 2012 2:57 pm

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}$

User avatar
FahimFerdous
Posts: 176
Joined: Thu Dec 09, 2010 12:50 am
Location: Mymensingh, Bangladesh

Re: IMO 1999-4

Unread post by FahimFerdous » Thu Mar 29, 2012 7:34 pm

Small Hint:
Working with largest or smallest prime divisor often helps. And try to find co prime numbers.
Your hot head might dominate your good heart!

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: IMO 1999-4

Unread post by Masum » Thu Apr 05, 2012 12:38 pm

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

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: IMO 1999-4

Unread post by Masum » Thu Apr 05, 2012 12:48 pm

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

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

Re: IMO 1999-4

Unread post by Nadim Ul Abrar » Fri Apr 06, 2012 11:47 pm

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}$

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: IMO 1999-4

Unread post by Masum » Sun Apr 08, 2012 12:01 am

আমি ও তো ওইটা না ব্যবহার করি নাই। ভুলেই গেছিলাম ওইটার কথা। আসলে ওইটার কোন দরকার নাই। এম্নিতেই দেওয়া হইছে।
One one thing is neutral in the universe, that is $0$.

Post Reply