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.

Disappointingly simple problem...

I saw somwhere that taking $n=(a+1)(p-1)+1$ where $p$ is a prime $>b$ helps contradicting,but I don't remember where I saw it.But I would have preferred a proof using some kind of limits......when $n$ becomes very large,we cannot help avoiding the fact that $a=b$.......something like this kind of an approach.

Incorrect solution, please ignore

Disappointing France ain't that bad I'm sure

Let $q$ be a prime such that $\gcd(a,q)=1$ , $\gcd(b,q)=1$ and $q>b-a$. Let $t$ be a positive integer such that $q\mid t-a$. Let $N=t(q-1)+q$. Note that by Fermat's Little Theorem $a^N \equiv_q a\equiv_q -t(q-1) \implies$ $$\implies q\mid a^N+N \mid b^N+N \implies a^N \equiv_q b^N \implies a \equiv_q b \implies a=b$$

Take $p$ a very big prime >>$ab$. Take $n=1(mod$ $p-1)$,$n=-a(mod$ $p)$.It exists by CRT,and by FLT: $p\mid a^n+n\mid b^n+n$ But by FLT $b^n+n=b-a(mod p)$.Thus $p\mid b-a$,as p is as big as we want $\implies b=a$

Too easy! My solution: FTSOC assume that $b>a$. Choose some prime $p$ such that $p \nmid a,b$. Consider $n=(a+1)p-a$. Note that $p-1 \mid n-1$. Then we get that $$a^n+n \equiv a+n \equiv 0 \pmod{p} \Rightarrow p \mid a^n+n \mid b^n-a^n \Rightarrow 0 \equiv b^n-a^n \equiv b-a \pmod{p}$$where we use FLT to get that $a^n \equiv a \pmod{p}$ and $b^n \equiv b \pmod{p}$. Thus, there exist infinitely many primes $p$ such that $p \mid b-a$, which is only possible if $b=a$. Hence, done. $\blacksquare$

Here's my take on it: $Lemma 1:$ Let $u, v$ be coprime positive integers and $p$ be a prime. Then all of the prime divisors of the number $\frac{u^p-v^p} {u-v}$ are either $p$ or are congruent to $1 \mod p$. $Proof:$ Suppose that the prime number $q$ divides $u^{p-1}+\cdots+v^{p-1}$. Then we have $u^p \equiv v^p (\mod q) $. Multiply the congruence by $v^{-p}$ to obtain $w^p \equiv 1 (\mod q)$, where $w=uv^{-1}$. Let $w \in k \mod q$. Then $k \mid p$ and we have $2$ cases. $Case 1: k=1$ Now we have that $w \equiv 1 \mod q$ or in other words $u \equiv v \mod q$. But then we see that $u^{p-1}+\cdots+v^{p-1} \equiv p.u^{p-1} (\mod q)$ but this should be divisible by $q$. Now if $q \mid u$, then $q \mid v$, a contradiction, therefore $q \mid p$ and indeed $q=p$. $Case 2: k=p$ We obviously have $w^{q-1} \equiv 1 (\mod q)$ by FLT, so $p=k \mid q-1$ and indeed $q \equiv 1 (\mod p)$. $Lemma 2:$ Let $a$ be a positive integer and let $q>a$ be a prime number. Then there exists a prime $p$ such that $q \mid a^p+p$ and $p>q$. $Proof:$ Let us select $p=t(q^2-q)+(aq+q-a)$ where $t$ is some positive integer. Now $p$ is of the form $tx+y$ and if we can show that $(x, y)=1$, it would follow from Dirichlet's Theorem that there are infinitely many primes $p$ of this form. Suppose for the sake of contradiction that there exists a prime $r$ such that $r \mid q^2-q$ and $r \mid aq+q-a$. From the first condition we obtain that either $r=q$ or $r \mid q-1$. $Case 1: r=q$ Now we have $q=r \mid aq+q-a$, but then $q$ must divide $a$, a contradiction. $Case 2: r \mid q-1$ Now $r \mid a(q-1)+q$, so $r$ divides both $q-1$ and $q$ but they are obviously coprime so there doesn't exist such a prime $r$. Now from Dirichlet's Theorem we indeed have that there exist infinitely many primes $p$ of the desired form and for each of them we see that $p \equiv 1 (\mod q-1)$ and $p \equiv - a (\mod q) $, so $q$ indeed divides $a^p+p$. Now let's move on to the problem: From the divisibility condition we easily obtain $a^n+n \mid - (b^n+n-a^n-n) =a^n-b^n$. Let $a=du, b=dv$, where $(u, v) =1$ and $d=(a, b)$. We obtain $a^n+n \mid d^n(u^n-v^n)$. Now denote by $A$ the set of all primes strictly larger than $max(a, b) $. Let $q$ be a prime from this set. By $Lemma 2$, there is a prime $P$ such that $q \mid a^P+P$ and $P>q$. Select $n=P$. We have that $q \mid a^P+P \mid d^P(u-v)(u^{P-1}+\cdots+v^{P-1})$. Since $q>max(a, b) $ it follows that $(q, d) = 1$. But also $P>q$, so $q$ isn't congruent to $1 \mod P$ and by $Lemma 1$, $(q, (u^{P-1}+\cdots+v^{P-1}))$. This leaves us with $q \mid u-v$. But $u, v$ are fixed and we can do this trick for every prime in $A$. We will obtain that $u-v$ has infinitely many prime divisors and this is only possible when $u-v=0$, i. e. $a=b$, $\blacksquare$.

Redacted

mysteryguy6647 wrote: Please confirm my solution: Let $p$ be a prime such $p|a^n+n$ and $p|b^n+n$. Then $p|a^n-b^n=(a-b)(a^{n-1}+...+b^{n-1})$. FTSOC, assume that $p$ doesn't divide $a-b$. Then $p|a^{n-1}+...+b^{n-1}$. So, we also have $p|a+b$. Since $p|a^n+b^n+2n$, we can choose an odd prime $n$, thus $p|2n$. $p|2\implies p=2$ which is obviously not always true. $p|n$ is also not always true. Contradiction. It's not clear why $p$ must divide $a+b$.

Choose prime $p$ such that $p > b - a$, $n \equiv 1 (\mod p - 1)$ and $p | a^n + n$. Then FLT gives $a \equiv a^n \equiv b^n \equiv b (\mod p)$, so $p | a-b$. Case 1: If either of $a,b$ is divisible by $p$ then the other must also be divisible by $p$. This is impossible because $p > b-a$ Case 2: $p \nmid a,b$ then $p | b-a \implies a = b$

Redacted

mysteryguy6647 wrote: Illuzion wrote: mysteryguy6647 wrote: Please confirm my solution: Let $p$ be a prime such $p|a^n+n$ and $p|b^n+n$. Then $p|a^n-b^n=(a-b)(a^{n-1}+...+b^{n-1})$. FTSOC, assume that $p$ doesn't divide $a-b$. Then $p|a^{n-1}+...+b^{n-1}$. So, we also have $p|a+b$. Since $p|a^n+b^n+2n$, we can choose an odd prime $n$, thus $p|2n$. $p|2\implies p=2$ which is obviously not always true. $p|n$ is also not always true. Contradiction. It's not clear why $p$ must divide $a+b$. yes it is clear. because when $n=2$ we have $p|a+b$. can you please check my solution now? Thank you for your comment. How do you find $p$ such that $p \nmid a - b$, $p |a+b$, $p|a^n + n$?

Seems significantly easier than other N6s of this time period, but still not terribly trivial or anything, so seems fair to give it a pass: First let's restate the problem as following: $a^n+n \mid b^n-a^n$ for all $n$ $\implies$ Prove $a=b$. The trick here is to choose $n$ such that $p \mid b^n -a^n$ boils down really quickly- letting $a \equiv r^{\alpha}$ and $b \equiv r^{\beta} \pmod{p}$ (where $r$ is a primitive root $\pmod{p}$), we get $p \mid b^n-a^n \implies r^{n \alpha} \equiv r^{n \beta} \implies r^{n(\alpha-\beta)} \equiv 1 \pmod{p}$. Thus, if we choose $\text{gcd}(n,p-1)=1$, we get $ \alpha \equiv \beta \pmod{p-1} \implies a \equiv b \pmod{p}$. Thus our job reduces to finding a $(p,n)$ pair such that: a). $p \nmid b-a$ (Only possible if $b \neq a$) b). $\text{gcd}(n,p-1)=1$. c). $p \mid a^n+n$ We can deal with condition $b$ by simply choosing $n=k(p-1)+1$, and instead of directly dealing with condition $a$, we can replace it by choosing an arbitrarily large prime, which although far stronger should be easier to deal with. Hence we need to find $k$ such that $p \mid a^{k(p-1)+1} +kp-k+1 \implies a-k+1 \equiv 0 \implies k \equiv a+1 \pmod{p}$. Hence, for arbitrarily large $p$, we can choose $n=(tp+a+1)(p-1)+1$, and as that fulfils all 3 conditions, we're done, and thus $a=b$.

Does this work?

just take a prime $p$ and choose $n$ such that $n \equiv 1 \bmod p-1$ and $n \equiv -b \bmod p$ then $p|b^n+n \implies p|a^n +n $ but $a^n \equiv a \bmod p \implies p|a-b$ for any prime $p$ take $p \rightarrow \infty$ then $a=b$ and we win

First note $a \le b.$ Now, take prime $p$ arbitrarily large, then $n \equiv 1 \pmod{p-1}$ and $n \equiv -a \pmod{p}$. This forces $a^n \equiv a$ and $b^n \equiv b \pmod{p}$, so thus $p \mid a^n + n \mid b^n + n$. However, $b^n + n \equiv b - a \equiv 0 \pmod{p}$, which if we take $p > b$ forces $b = a$, done.

What a joke. Consider prime $p$ and $n$ such that $n \equiv 1 \pmod{p-1}$ and $n \equiv -a \pmod p$. Clearly such $n$ exists by CRT. Notice that by FLT we clearly must have $p\mid a^n - a \iff p \mid a^n + n$ so therefore $p \mid b^n + n$ and FLT again on $b^n$ gives $b \equiv a \pmod p$. Thus, $p \mid b - a$ and choosing sufficiently large $p$ forces $b = a$, as desired. $\blacksquare$

Oh I just got reminded to write this up For some large p take $n=a(p+1)-a$, clearly congruent to $1$ mod $p-1$ and $-a$ mod $p.$ This implies that $p\mid a^n+n,$ so we must have $b^n+n\equiv 0\pmod{p}$ as well. Note $b^n\equiv b\pmod{p}$ and $n\equiv -a\pmod{p}$ so $a\equiv b\pmod{p}$ for infinitely many primes $p.$ Thus, we have LAUNCHED a NUKE at this PROBLEM.

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