This is ISL 2005 and is designed by Mohsen Jamali an Iranian teacher, the designer of IMO 2004 Problem 6

ZetaX ---

Omid Hatam wrote: ## This is ISL 2005 and is designed by Mohsen Jamali, ## an Iranian teacher, the designer of IMO 2004 Problem 6. To stress it once again: The problem IMO 2004/6 on "alternating" numbers is just a rewritten version of the "wobbly" number problem from the IMO 1994 shortlist. Using it for IMO'2004 was nothing but a bad mistake of the problem selection committee. http://www.mathlinks.ro/Forum/resources-1-16-2004-99760.html http://www.kalva.demon.co.uk/short/soln/sh94n7.html

Let's take a prime $p>b-a$. Then we take an integer $k>1$ s.t. $(k,p-1)=1$. We have that $a^k \equiv -x \pmod{p}$. Now we can find two numbers $y,z \geq 0$ s.t. $k+y(p-1) = x+zp = N$. Now we have $a^N \equiv -N \pmod {p}$ and so $p|a^N+N|b^N+N$ and so $a^N+N \equiv b^N + N \pmod{p}$. Now we can say that $a^k \equiv b^k \pmod{p}$ and so $a \equiv b \pmod{p}$ (we remember that $(k,p-1)=1$) and so $a=b$ because $p|b-a$ but $b-a<p$

I'm sorry, i don't understand the first part of your solution Could you explain it to me, please ?

Quote: The problem IMO 2004/6 on "alternating" numbers is just a rewritten version of the "wobbly" number problem from the IMO 1994 shortlist may be he don't know this however problem3 may be known before by contestant too

Is there anyone who can explain this problem ? Please can you help ... is there any other solutions ? Davron

There is an asymptotical solution by Peter Scholze, but it's long and ugly... (mine is more or less the same as above: look for some big prime $\mod$ that they are equal)

Thank you very much but what is going on there i couldn't understand, i will try my best to get the solution. Please help me with some points i will ask you : -which method of problem solving there used ? Davron

The main ideas (what exactly do you call a method¿) for mine are: If $p \nmid a,b$ is any prime and we have any $k$ with $p|a^{k}+k$, then $p|a^{k}+k|b^{k}+k \implies p|b^{k}+k$, thus $a^{k}+k \equiv 0 \equiv b^{k}+k \mod p \iff a^{k}\equiv b^{k}\mod p$. If we additionally would have $k \equiv 1 \mod (p-1)$, then Fermats Little Theorem gives $a \equiv a^{k}\equiv b^{k}\equiv b \mod p$. But for $k \equiv 1 \mod (p-1)$ we have also $a^{k}+k \equiv a+k$, so to get $p|a^{k}+k$ we just need $p|a+k$. So lets look for some $k \equiv 1 \mod (p-1)$ and $k \equiv-a \mod p$, which can be found by the Chinese Remainder Theorem or directly as $k=(p-1)(a+1)+1$. Till now we didn't use any special property of $p$ except that it doesn't divide $a,b$. But we know that for any such prime we have $p|(a-b)$ from chossing a suitable $k$ with $p|a^{k}+k$, thus if $a \neq b$ we would get a contradiction by choosing a big prime.

But what about the other cases, what will happen when k doesn't give a remainder 1 up on the division with p . Thank you ZetaX. Sincerely Davron

We ignore that cases since we don't need them.

More than if $ P(n)=xn+y$ and $ a^n+P(n)|b^n+P(n)$ then $ a=b$

EDIT: Another proof of the lemma:

The QuattoMaster 6000 wrote:

EDIT: Another proof of the lemma:

$3^6=1^6\pmod{4}$ don't say $(1/3)^6\pmod{4}$???

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\nmid 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.

Wouldn't $a+1$ divide $b-a$ $a+2$ divide $(b-a)(b+a)$ $a+3$ divide $(b-a)(b^2+ab+a^2)$ (all by euclidean algorithm) we conclude $b-a=1,0$ or $-1$.($a$ is coprime with $a+1$) Then by simple experiments, we get $b-a=0$ Is this counted a proper solution? it seems too easy to be true

Contrary to your suggestion, I found a+1 divide b-a a^2+2 divide (b-a)(b+a) a^3+3 divide (b-a)(b^2+ab+a^2)

Une solution que j'ai trouvée sur le net est comme suit: Assuming b \&=a (ça veut dire b différent de a), it trivially follows that b>a. Let p>b be a prime number and let n= (a+1)(p−1)+1.We note that n≡1(mod p−1)and n≡ −a(mod p). It follows that: r^n = r·(r^(p−1))^(a+1)≡r(mod p)for every integer r. We now have a^n+n≡a−a=0(mod p). Thus, a^n+n is divisible by p, and hence by the condition of the problem b^n+n is also divisible by p. However, we also have b^n+n ≡ b−a (mod p), i.e., p | b−a, which contradicts p>b. Hence, it must follow that b = a. We note that b = a trivially fulfills the conditions of the problem for all a∈ N.

Almost the same as others. Solution: By ``Chinese Remainder Theorem'', there exists a $n$ such that \begin{align*} n & \equiv -\frac{1}{a} \pmod{p} \\ n & \equiv -1 \pmod{p-1}. \end{align*}for an arbitrary prime $p$. Call the $n$ which satisfies these congruences as ``constructive''. One can show that $p \mid a^n + n$ for all such constructive $n$ for any prime $p$ with the aid of ``Fermat's Little Theorem''. Clearly \[a^n + n \mid b^n + n \iff a^n + n \mid b^n - a^n.\]Pick a constructive $n$ in the above relation. We would get $p \mid a - b$ for any prime $p$. Since $a-b$ have infinitely many divisors, we must have $a = b$ and we are done. $\blacksquare$

Let $p$ be any prime. Then $p\mid a^n+n\mid b^n-a^n$. Choosing $n=k$ such that $k\equiv 1\mod{p-1}$ and $k\equiv -a\mod p$, gives $a^n+n\equiv 0\mod p$. Therefore, \[b^n-a^n\equiv b-a\mod p\]choosing $p$ large gives $a=b$, as needed.

Obviously $a\le b$. Now consider a prime $p>b+1434$. Now let $n$ be a positive integer such that $n\equiv 1\pmod{p-1}$ and $n\equiv p-a\pmod{p}$. Clearly $p$ divides $a^n+n$. The only way that $p$ divides $b^n+n$ is if \[p\mid (b+p-a)\rightarrow a=b.\]QED.

Let $p>b\ge a$ be a prime and let $n\equiv -a\pmod p$ and $n\equiv 1\pmod {p-1}$. The latter means that $x^n\equiv x\pmod p$ for all $a$. Thus, \[a^n+n\equiv a+n\equiv 0\pmod p\]and so $p\mid b^n+n\implies p\mid b-a$. Since $b-a<b<p$, $b-a=0$ as desired.

Oops...

Condition becomes \[ a^n + n \mid b^n - a^n \]for all positive integers $n$. Let $p > 2541434198442069459ab$ be a prime. Choose $n=1+(a+1)(p-1).$ FLT gets that $p$ divides $a^n + n$, but also $p$ cannot possibly divide $b-a$ unless $b=a$ due to how stupidly large $p$ was chosen to be.

ISL 2005 N6 Very easy construction problem

@above why such a weird number lol i see 1434 but what else bruh

Rewrite the relation as $a^n+n \mid b^n-a^n$. WLOG $b \geq a$. Take a prime $p > b$ and allow $n \equiv 1 \pmod {p-1}$ and $n \equiv -a \pmod {p}$ which exists by CRT. It follows that $a^n+n \equiv a-a \equiv 0 \pmod p$ so $p \mid a^n+n$. This means that $p \mid b^n-a^n$ but since $b^n \equiv b \pmod {p}$ and $a^n \equiv a \pmod p$ we have $p \mid b-a$ which means $b-a = 0$ or $a=b$ as desired.

Claim: There are infinitely many primes $p$ such that $a^n + n \equiv 0 \pmod{p}$ and $\gcd(n, p-1) = 1$ for some $n$. Proof. We show this holds for all odd primes $p$. Take $n = 1 + (a+1)(p-1)$. By FLT it follows that $a^{1 + (a+1)(p-1)} + 1 + (a+1)(p-1) \equiv a - a \equiv 0 \pmod{p}.$ $\blacksquare$ Note that this is equivalent to \[ a^n + n \mid b^n - a^n. \]Taking this $n$, we then get that \[ p \mid a^n + n \mid b^n - a^n \]so $b^n \equiv a^n \pmod{p}$, and since $\gcd(n, p-1) = 1$ it follows that $b \equiv a \pmod{p}$. Equality follows as there are infinitely many such primes.

We claim $p \mid b-a$ for all primes $p$, which directly implies the desired. Construct a value of $n$ such that \begin{align*} n &\equiv 1 \pmod{p-1} \\ n &\equiv -a \pmod p, \end{align*}which must exist by CRT. Then $a^n + n \equiv a-a \equiv 0 \pmod{p}$, so \[0 \equiv b^n + n \equiv b-a \pmod{p}.~\blacksquare\]

BTW I believe a very nice solution is possible using limits... Will upload if I finish it

We choose $n = (p-1)(a+1)+1$ for a large prime $p > a > |a-b|.$ Then, \[p \mid a^n+n \mid b^n - a^n \implies p \mid b - a \implies a = b\] as needed.

Consider a prime $p \nmid a$. For such a prime $p$, we must have $p \nmid b$,as seen from say $n = p-1$. Now we choose $n$ such that $n \equiv 1 \pmod{p-1}$, and $n \equiv -a^n \pmod{p}$, which exists by CRT. Choosing such an $n$, we have $ p \mid a^n + n \mid a^n -b^n \implies p \mid a-b$. But since this is true for all $p \nmid a$, we have $a-b = 0 \implies \boxed{a = b}$.

Consider some prime $p$. Then, let $n=(a+1)(p-1)+1$. We see that $a^n+n\equiv 0\pmod{p}$. Therefore, $b^n+n\equiv 0\pmod{p}$. Since $n\equiv 1\pmod{p-1}$, $b\equiv n\pmod{p}$. Therefore, $n\equiv a\equiv b\pmod{p}$. Therefore, $a=b$.