IMO Shortlist 2005 N6

[Phlembac Adib Hasan]

Let $a,b$ be two positive integers. Suppose $a^n+n$ divides $b^n+n\quad \forall n\in\mathbb N$. Prove that $a=b$.

Comment: এত সুন্দর প্রবলেম মানুষের মাথায় আসে ক্যামনে?

[Masum]

আমার কমেন্টঃ এইটা মানুষ সুন্দর বলে কেমনে? ধরতে গেলে কিছুই তো নাই। :S যাই হোক, আমার কাছে প্রব্লেম তখনই সুন্দর হয় যখন এর এমন একটা ইনজিনিয়াস সমাধান থাকে যেটা করার জন্য প্রায় কিছুই জানা লাগে না, খালি চিন্তা করেই পারা যায়।

[Masum]

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

[Phlembac Adib Hasan]

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

হুম। অফিশিয়ালে $n=$something বসিয়ে প্রবলেমটাকে একেবারে খুন করে ফেলা হয়েছে। মাত্র তিন লাইন!

আর আমি একটা বিশেষ $p$-র জন্য দেখিয়েছি এরকম একটা $n$ আছে, কিন্তু সেটা exactly বের করি নাই। কিন্তু আমার নেয়া প্রাইম, আর ওদের নেয়া প্রাইমের মাঝে বিস্তর পার্থক্য আর একইসাথে $n$-এর কন্সট্রাকশনেও বিশাল পার্থক্য।

[Masum]

এইটার অফিশিয়াল সল্যুশন দেখসেন? বেশি সুন্দর। ফার্মার লিটল থিওরেম ছাড়া আর কিছু জানা লাগে না। সেটা অতিমাত্রায় জিনিয়াস সমাধান এবং এমন একখান ক্রাক্স মুভ আছে যেটা ছয় ঘন্টার কাছাকাছি একটানা চিন্তা করেও আমার মাথায় আসে নাই। এবং আমার নিজের সল্যুশন অফিশিয়াল থেকে সম্পূর্ণ আলাদা, সেইটা করতে খুব কঠিন কিছু লাগে না। (একটা জিনিস বাদে, আপনাকে অই প্রশ্নটা করেছিলাম এই কারণেই)

আচ্ছা আমার কথা মতেই যদিও এইটা প্রায় সুন্দর প্রব্লেমের কাতারে চলে যায়, তাও কেন জানি ভাল মনে হয় নাই। যাই হোক, আমি এইখানে প্রধান আইডিয়াগুলা কিভাবে আসে সেটা দেখাইতে চেষ্টা করতেছি।

$b\geq a$ এটা পরিষ্কার. এখন $a|b-c$ যদি $b\geq c$ এবং $b-c<a$, তাহলে $b-c=0$ হতে হবে. আমরা একটি মৌলিক সংখ্যা $p>b$. তাহলে এমন $n$ বের করা লাগবে যাতে $a^n+n|b^n+n$ ঠিক না থাকে. আমাদের এমন $n$ নেওয়া লাগবে যাতে $n\equiv1\pmod{p-1}$(যাতে ফার্মা খাটানো যায়) এখন $a^{p-1}\equiv b^{p-1}\pmod p$ and $a^n\equiv b^n\equiv\pmod p$. This gives $a^{\gcd(n,p-1)}\equiv b^{\gcd(n,p-1)}\pmod p$.(এটা যে কত সমস্যায় কাজে লাগে তার কোন ঠিক নাই, এখন বুঝার কথা কেন আমি এই $n$ কে নিতে হইছে) $a\equiv b\pmod p$. কিন্তু এটা সম্ভব না যেহেতু $p|b-a<p$. এই জায়গায় একটা ব্যাপার আমরা এখনো দেখাই নাই, $p|a^n+n$. এটা দেখানোর জন্য $a^n\equiv-n\pmod p$ লাগবে। এই $n$ যে আসলেই থাকবে সেটা প্রমাণ আমি ছেড়ে দেই।

[Fahim Shahriar]

$b^n+n \equiv 0 (mod a^n+n)$
$b^n \equiv -n (mod a^n+n)$
$b^n \equiv a^n (mod a^n+n)$
$b^n-a^n \equiv 0 (mod a^n+n)$

$(b^n-a^n)=(b-a)(....)$
$(b-a)$ will be divisible by $(a^n+n)$ for any value of $n$. Then $(b-a)$ has infinite factors which implies $b-a=0$.

Am I correct? I think the 2nd part isn't. Can we go to the end following the 1st part ?
What's the official solution?

[Phlembac Adib Hasan]

Am I correct? I think the 2nd part isn't. Can we go to the end following the 1st part ?
What's the official solution?

Absolutely not. The following thing is not true:

$(b-a)$ will be divisible by $(a^n+n)$ for any value of $n$.

[Phlembac Adib Hasan]

My Solution:
আগে এত সময় লাগার কারণ বলি। প্রথমে আমি ট্রাই দিছিলাম $a-b$-র উৎপাদক সংখ্যা অসীম সেইটা দেখানোর জন্য। এরপর ট্রাই মারি $b$-কে বাউন্ড করতে। এটাতে যথেষ্ট সাফল্য আসছিল, শুধু দুইটা কেস করা যায় নাই। তারপর গ.সা.গু. নিয়ে খানিকক্ষণ গুঁতাগুঁতি, এটাও প্রায় সফল, খালি একটা কেস পারা যায় না। তারপর পাওয়ার দিয়া অসমতা আনার চেষ্টা, তারপর খানিকটা রিফর্ম করে এল.টি.ই. দিয়ে ফিনিশ করার চেষ্টা- সব বিফল। প্রাইম ধরে contradiction আনার চিন্তা বহু পরে মাথায় আসছে।

Let $p$ be a very large prime (larger than $b^2$). Since $p$ and $a$ are coprime, the modular equation $ax\equiv -1\pmod{p}$ has solution. Let the solution be $g,g>0$. Hence
$ag\equiv -1\pmod{p}\Longleftrightarrow (ag)^m\equiv -1\pmod {p}$ for all natural odd numbers $m$.
Since $\gcd (g,p)=1$, the following modular equations has solution.
$g^mx\equiv -1\pmod{p}$. Let $-d$ be the solution where $d\in \mathbb N$. Then $a^m\equiv -d\pmod{p}$.
So $a^m+m\equiv m-d\pmod{p}$. Note that when $m$ is of the form $cp+d,c\in \mathbb N$, $a^m+m$ is divisible by $p$.
Take $m=p+d$ or $2p+d$ depending on which one is odd. Below I completed the proof for $m=2p+d$. You can do the same task for $m=p+d$.
So $p|a^{2p+d}+2p+d$. But $b^{2p+d}+2p+d\equiv b^{d+2}+d\pmod{p}$
So if $p\not \mid b^{d+2}+d$, we are done. So let's consider the case when $p\mid b^{d+2}+d$. Take $n=4p+d$. So $p|a^n+n$. Then it should divide $b^n+n$. But notice that
$b^{4p+d}+4p+d\equiv b^{d+4}+d\equiv d(1-b^2)\pmod {p}$. Remember that $d$ is co-prime with $p$. So $p$ must divide $b^2-1$, but it is not possible because we assumed $p>b^2$ at the first line.

এডিট: অবশেষে দিরিশ্লে ছাড়াই করা গেল।

[asif e elahi]

At first we prove the following lemma.

Lemma:If $p$ be any prime divisor of $a+1$ then for all positive integer $k$,there exists a positive integer $n$ such that $p^{k}\mid a^{n}+n$.

Proof: We proceed by induction.For $k=1$ we can choose $n=1$.Now we assume that this is true for $k$.So there exists $f$ such that $p^{k}\mid a^{f}+f$. Let $a^{f}+f=p^{k}g$. If $ p$ divides $g$,we are done.So we assume that $(g,p)=1$. As $p$ divides $a+1,p$ and $a$ are coprime.So $a^{\phi (p^{k+1})}\equiv 1 $(mod $p^{k+1})$
or, $a^{p^{k}(p-1)}\equiv 1$(mod $p^{k+1})$.
Let $n=p^{k+1}g-a^{f}$. Then $a^{n}\equiv a^{p^{k+1}g-a^{f}}\equiv a^{p^{k}(p-1)g+p^{k}g-a^{f}}\equiv a^{p^{k}g-p^{k}g+f}\equiv a^{f}\equiv -(p^{k+1}g-a^{f})\equiv -n$(mod $p^{k+1})$.So $p^{k+1}\mid a^{n}+n$.Thus our induction is complete.

Main proof: $a^{n}+n\mid b^{n}+n$ or $a^{n}+n\mid b^{n}-a^{n}$. Setting $n=1$,we get $a+1$ divides $b-a$.We take a n such that $p^{k}\mid a^{n}+n$. As (p,$a^{n}$)=1,(p,n)=1.So by LTE theorem $\nu _{p}(b^{n}-a^{n})=\nu _{p}(b-a)+\nu _{p}(n)=\nu _{p}(b-a)$. But for $k> \nu _{p}(b-a)$, the right hand side is not divided by $p^{k}$. So $b^{n}-a^{n}$ must be equal to 0.This implies $b=a$.