$(a+1)^n=a^n (mod \ n) \Longrightarrow (a,n)=1,b^n=1(mod \ n)$, were a(b-1)=1(mod n). It give algoritm: If (c(n),n)=d>1 we have not trivial solutions b^d=1(mod n). If (b-1,n)=1, it give solutions a=1/(b-1) (mod n).

ehm...i don't understand;here is my solution: at first, let's suppose $(a;n)=1$ take the smaller prime factor of $n$ and let's call it $p$, with $n=p^ck$ so, it must be $(a+1)^{p^ck}\equiv a^{p^ck}$ $(\mod p)$ by Fermat's theorem $(a+1)^{k}\equiv a^{k}$ $(\mod p)$ $[(a+1)\cdot a^{-1}]^k\equiv 1$ $(\mod p)$ so the smaller number $x>0$ such that $[(a+1)\cdot a^{-1}]^x\equiv 1$ $(\mod p)$ is a divisor of $k$. we now also that that this number x is a divisor of $\phi(p)=p-1$, but all divisors of $k$ are greater than $p$ and so $x=1$. $(a+1)\cdot a^{-1}\equiv 1$ $(\mod p)$ $a+1\equiv a$ $(\mod p)$ $1\equiv 0$ $(\mod p)$ so this smaller prime does'n't exist,and there can be only $n=1$. in fact, with $n=1$ we have solution for every $a$. it remain only the case of $(a;n)=d>0$ but in this case the numerator becomes $\equiv 1$ $(\mod d)$ and so it cannot be a multiple of $n$. the only solution are so $(a;1)$ for each $a\in\mathbb{N}$

Suppose $p$ is the smallest prime divisor of $n$ the $p|(a+1)^n-a^n\Rightarrow p|(a+1)-a=1$. So contradiction proves that $n=1$

Omid Hatami wrote: Suppose $p$ is the smallest prime divisor of $n$ the $p|(a+1)^n-a^n\Rightarrow p|(a+1)-a=1$. So contradiction proves that $n=1$ So simple and elegant, excellent!!!!!

Another thing... These three problems are the only 3 or there is another round in China TST?? And another question: These 3 problems are really difficult to solve, aren´t they?????? (as any China TST) or any high-school olympiad student can solve them?????

dear omid : I dont follow your solution could you put more details in? p.s. your solution is very interesting.

$p|(a+1)^n-a^n\Rightarrow p|(a+1)-a=1$ is definitely correct, but I think you have jumped too many steps Omid Hatami. To see why this is correct, we first let $b$ be the unique inverse such that $ab\equiv 1 \pmod{p}$. We have $(a+1)^n \equiv a^n \pmod{p}$, and multiplying both sides by $b^n$, we get $((a+1)b)^n \equiv 1 \pmod{p}$. Letting $d$ be the order of $((a+1)b) \mod p$, we have $d\mid n$. Yet, by Fermat's Little Theorem, we have $((a+1)b)^{p-1}\equiv 1 \pmod{p}$, so $d\mid p-1 \Rightarrow d < p \Rightarrow \gcd (d,n)=1$, due to the definition of $p$ as the smallest prime divisor of $n$. Thus $d=1$, implying that $(a+1) \equiv a \pmod{p}$, which is the contradiction we want.

obviously $n$ isn't even. Let $p$ be the smallest prime divisor of $n$.and let $g$ be a primitive root modulo $p$ . Let $a+1\equiv g^k,a\equiv g^l \pmod{p}$ so ve have : $g^{kn} \equiv g^{ln}\pmod{p}$ so $p-1|n(k-l)$ so $p-1|k-l$.so$p|g^k-g^l$ so $p|(a+1)-a$ so $p=1$.

In fact there are 8 round in the China TST and in the first six round every problem is worth 7 points and in the last 2 days every one 21.So when we say China TST,we often means the last two days.And this 3 problem is the first round of 8! First two problems is very easy but I think no one can complete the third one in the exam. This 3 problems is from Zuming Feng,the IMO team leader of USA in 2005.

I see jin... and what's the difficulty of this problem????? (really hard?)Is it like what number of an IMO problem?????? or it is easier like an IMO problem?

This one?the second one is really easy, I think almost every one in the exam can solute it. But I made a very silly mistake(forgot n=1)

Hmmm ... I am really new to number theory and I can not understand most of what you guys did and when I can I am not always able to figure out how you got there so I tried to go for it myself. Anyways, this is what I got and please tell me where any errors occur. ((a+1)^n - a^n) / n == 0 (mod m) (== means congruent to) multiply both sides of congrunce by n to get (a+1)^n - a^n == 0 (mod m) now we can add a^n to both sides to produce (a+1)^n == a^n (mod m) I think that this means n must equal 1, therefore we say (a+1) == a (mod m) substracting a from both sides we see that 1 == 0 (mod m) which is the same as saying (1-0)/m is an integer this is only true if m =1 (we are dealing with only positive integers in this problem) so going back to our original equation we plug in n=1 and m=1 for the integer our equation must yield ((a+1)^1 - a^1)/1 = 1 => a+1 - a = 1 => 1=1 since this is true for any 'a' our solution is (a,1) Thank you for any help you can provide me with!

Here are some of my comments on your solution. From the first line of your solution, you have defined $m$ as some divisor of $\frac{(a+1)^n-a^n}{n}$. Even if you eventually show that $m=1$, you have only shown that $\frac{(a+1)^n-a^n}{n}$ is indeed an integer, which was what you have assumed right from the start. For this problem, you do not want to investigate the divisors of $\frac{(a+1)^n-a^n}{n}$; rather, you want to investigate the divisors of $n$. So you should just let your $m$ be any divisor of $n$, and what you want to show in the end is that this arbitrary divisor of $n$ has to be $1$. Your first line of the solution should just be ${(a+1)^n-a^n \equiv 0 \pmod{m}}$, where $m\mid n$. Next, we arrive at your step of $(a+1)^n \equiv a^n \pmod{m}$ implying $(a+1) \equiv a \pmod{m}$. Though this is true in reality, you did not provide any justification to this step. Remember, you want to show that $m=1$ in the end, so we want to assume $m>1$ and derive a contradiction. Now, if we know $m>1$, definitely, $m$ must have at least one prime divisor. The trick we use here is to let $p$ be the smallest such prime divisor of $m$ to derive the contradiction we want. Now we have $(a+1)^n \equiv a^n \pmod{p}$. We notice that $p$ does not divide both $(a+1)$ and $a$ (Why? Look back at our original problem..), so there must exist a unique inverse of $a$ (Why?). letting $b$ be that unique inverse, we have $ab \equiv 1 \pmod{p}$ by definition. Thus, back to our congruence $(a+1)^n \equiv a^n \pmod{p}$, by multiplying both sides by $b^n$, we get $((a+1)b)^n \equiv 1 \pmod{p}$. For the rest of the solution, refer to my previous post, or Omid Hatami's solution (behzad's solution uses a slightly different approach, but it is still similar in idea). Recall that if $d$ is the order of $x \mod y$, then $d$ is the smallest positive integer such that $x^d \equiv 1 \pmod{y}$. If we have $x^M \equiv 1 \pmod{y}$, then we must necessarily have $d\mid M$. (Why? Try convincing yourself on this first.) I hope you can understand better now.

I really understand the solutions now. Using be was pure genius and I understand why m=1 by the contradiction. Thanks for all the help dblues!

,how can recent chinese tst pro. stolen from previous romanian tst? l.panaitopols pro. of romtstaround 88-90,asks for a=2,but idea is essentially same.

Haha.. This idea is very common, so you can't exactly say it was stolen.

frengo wrote: $(a+1)^{p^ck}\equiv a^{p^ck}$ $(\mod p)$(*) by Fermat's theorem $(a+1)^{k}\equiv a^{k}$ $(\mod p)$(**) I think you can't say that from *, ** is true. @all: please can you say what does let x be the order of d mod p, mean? sincerely davron

@Davron if $x$ is smallest number such that $d^x \equiv 1 (mod p)$ then we say that $x$ is order of $d$ $(modp)$

well, using the number theory to solve it is very beautiful, but... when i read the problem, i just thought about open the polynome by Newton´s formula, and as we have n multiplying all $a^{n}$ terms, we would only have 1/n in the last term (all the others are necessarily integers) , so... n may be 1.

for teaching the smallest prime divisor idea

handwritten solution images attached

The answer is $(1, a)$ only. The idea is to pick a minimal prime $p \mid n$, such that $a+1 \equiv a \pmod p$ for order reasons. This implies $p=1$, thus only $n=1$ can work.

The condition is essentially just $$(a+1)^n\equiv a^n\pmod{n}$$ Case 1: $n$ does not divide $a$. Then, let $p$ be the smallest positive integer that divides $n$ but not $a$. Then, we have $$(\frac{a+1}{a})^n\equiv 1\pmod{p}.$$Therefore, the order of $(a+1)/a$ mod $p$ divides $n$. However, this is smaller than $p$, and by definition, all divisors of $n$ smaller than $p$ are also divisors of $a$. Thus, unless the order of $(a+1)/a$ is 1 (i.e. $a+1\equiv a\pmod{n}$ so $n=1$, contradiction since $n$ does not divide $a$), $a$ and $n$ are not relatively prime, since this order divides both of them. Suppose $q\mid a$ and $q\mid n$. Then, taking $(a+1)^n\equiv a^n\pmod n$ mod $q$ reveals that $$1\equiv 0\pmod{q},$$contradiction. Case 2: $n$ divides $a$. Then, this is just $$(a+1)^n\equiv a^n\pmod n$$$$1\equiv 0\pmod{n},$$so $n=1$. Thus, the answer is $n=1$ and we are done.

Some months later solve: Clearly, $n=1$ and $a\in\mathbb{Z}^+$ work. Therefore, assume $n>1$ from now on. Let $p$ be the smallest prime divisor of $n$, so that \[(a+1)^n\equiv a^n\mod p\]Let $g$ be a primitive root mod $p$, and let $0\le\alpha,\beta\le p-2$ such that $g^{\alpha n}\equiv(a+1)^n\equiv a^n\equiv g^{\beta n}\mod p$. We get \[g^{n(\alpha-\beta)}\equiv 1\mod p,\]meaning $p-1\mid n(\alpha-\beta)$. However, as $p$ is the smallest prime dividing $n$, $\gcd(p-1,n)=1$, so $p-1\mid \alpha-\beta$. As $0\le\alpha,\beta\le p-2$ we must have $\alpha=\beta$. We get get $a+1\equiv g^{\alpha}\equiv g^{\beta}\equiv a\mod p$, implying $0\equiv 1\mod p$, which is impossible, so we have no more solutions.

Here's an attempt at a different solution Let $a=\prod_{i=1}^{k}p_i^{\alpha_i}$. Now using this observe that $$(a+1)^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n\equiv 1\pmod {p_1}\text{ thus }\operatorname{ord}{p_1}(a+1)=\operatorname{ord}{p_1}\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)=n\mid p_1-1\Longleftrightarrow p_1\equiv1\pmod n$$$$\text{ Furthermore } (a+1)^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n\equiv1\pmod {p_2}\text{ thus }\operatorname{ord}{p_2}(a+1)=\operatorname{ord}{p_2}\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)=n\mid p_2-1\Longleftrightarrow p_2\equiv1\pmod n$$$$\vdots$$$$\text{ Now } (a+1)^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n\equiv1\pmod {p_k}\text{ thus }\operatorname{ord}{p_k}(a+1)=\operatorname{ord}{p_k}\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)=n\mid p_k-1\Longleftrightarrow p_k\equiv1\pmod n$$$$\text{ Using all these together we obtain that }\prod_{i=1}^{k}p_i^{\alpha_i}\equiv1\pmod n$$Moreover notice that our original condition is equivalent to $\frac{(a+1)^n-a^n}{n}\Longleftrightarrow(a+1)^n-a^n\equiv0\pmod n$ However $(a+1)^n-a^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n-\left(\prod_{i=1}^{k}p_i^{\alpha_i}\right)^n\equiv (1+1)^n-1^n\equiv 2^n-1\pmod n$ Therefore the condition transforms into $2^n-1\equiv0\pmod n\Longleftrightarrow 2^n\equiv 1\pmod n$ Claim: $2^n\equiv 1\pmod n$ if and only if $n=1$ Proof: Notice that if $n\equiv 0\pmod 2$ we have that $2^n-1\equiv 1\pmod 2\text{ while }n\equiv0\pmod 2$ which is clearly a contradiction, thus $n\equiv 1\pmod 2\Longleftrightarrow\gcd(2,n)=1$ Now since $\gcd(2,n)=1$ we have that $2^n\equiv1\pmod n\Longrightarrow\operatorname{ord}_{n}(2)=n\mid\phi(n)\Longrightarrow n\mid\phi(n)\Longleftrightarrow\frac{\phi(n)}{n}\in\mathbb{Z}$ Furthermore let $n=\prod_{i=1}^{t}q_i^{\beta_i}$ and recall that $\frac{\phi(n)}{n}=\frac{\phi(\operatorname{rad} (n))}{\operatorname{rad}(n)}$ thus $\frac{\phi(n)}{n}=\frac{\phi\left(\prod_{i=1}^{t}q_i^{\beta_i}\right)}{\prod_{i=1}^{t}q_i^{\beta_i}}=\frac{\phi\left(\operatorname{rad} \left(\prod_{i=1}^{t}q_i^{\beta_i}\right)\right)}{\operatorname{rad}\left(\prod_{i=1}^{t}q_i^{\beta_i}\right)}=\frac{\phi\left(\prod_{i=1}^{t}q_i\right)}{\prod_{i=1}^{t}q_i}$ Furthermore since $\gcd(q_1,q_2,\dots,q_t)=1$ we have that $\phi\left(\prod_{i=1}^{t}q_i\right)=\prod_{i=1}^{t}\phi(q_i)=\prod_{i=1}^{t}q_i-1$ Therefore we need to have $\frac{\prod_{i=1}^{t}q_i-1}{\prod_{i=1}^{t}q_i}\in\mathbb{Z}$ which is clearly only the case when $n=1$ $\square$. So plugging in $n=1$ into our original equation yields $\frac{a+1-a}{1}=1$ which is clearly an integer. Thus $(a,n)=(a,1)$ for any integer $a$ is the only solution $\blacksquare$.

I claim the only solutions are $(a, n) = (x, 1).$ Henceforth assume $n > 1.$ Claim: $\gcd(a, n) = \gcd(a + 1, n) = 1$ Proof. Let $\gcd(a, n) = d > 1,$ then we have $d \mid a^n,$ but we must have $d \nmid a + 1,$ since if $d \mid a + 1,$ $d \mid \gcd(a, a + 1) = 1,$ contradiction. So, $d \nmid (a + 1)^n - a^n,$ but $d \mid n \mid (a + 1)^n - a^n,$ contradiction. Similarly, $\gcd(a + 1, n) = 1.$ Thus, there exist inverse of $a$ modulo $n$, so $(a + 1)^n \equiv a^n \pmod{n} \implies \left(\frac{a + 1}{a}\right)^n \equiv 1 \pmod{n},$ let $\frac{a + 1}{a} \equiv a^{*} \pmod{n},$ so let $p$ be the smallest prime divisor of $n$, this gives that $\mathrm{ord}_p(a^{*}) \mid \gcd(n, p - 1) = 1,$ so $a^{*} \equiv 1 \pmod{p},$ so $\frac{a + 1}{a} \equiv 1 \pmod{p},$ a contradiction, since $p > 1.$

Had solved this way back. Felt like posting now Its clear that $\gcd(a, n) = 1$.Its also clear that $n$ is odd. Let $p$ be the minimal prime dividng $n$. $(a+1)^n \equiv a^n (mod p) $. But we also have that, $(a+1)^{p-1} \equiv a^{p-1} (mod p) $. Its easy to see that due to this $p=2$. A contradiction. This implies $n=1$. Thus $(a,1)$ is the only solution

We claim the solutions are $(a, 1)$ for all positive integers $a$. Note that the condition reduces to $(a+1)^n \equiv a^n$ mod $n$. Assume that $n > 1$. In this case, let $p$ be the smallest prime divisor of $n$. Clearly $(a+1)^n \equiv a^n$ mod $p$. Also observer that $gcd(a, n) = gcd(a+1, n) = 1$, so from Fermat's Little Theorem, $(a+1)^{p-1} \equiv a^{p-1}$ mod $p$. Combining these two and applying the Euclidean Algorithm, we get $a^{gcd(p-1, n)} \equiv (a+1)^{gcd(p-1, n)} \text{ mod } p \implies a+1 \equiv a \text{ mod } p \implies p = 1$ But $p$ is prime so this is not possible. Therefore $n = 1$. But it is clearly visible that any $a$ works for $n = 1$, so we have our solutions. $\square$

I claim that all solutions of the form $\boxed{(a, 1)}$ where $a \in \mathbb{Z}^+$. Assume then $n \neq 1$, as $n = 1$ is trivial. Let $p$ be the smallest prime dividing $n$. Also (as the inverse exists) let $b$ denote the inverse of $a + 1$. Then we have $(a + 1)b \equiv 1 \pmod p \implies (a + 1)^nb^n \equiv 1 \pmod p$, so that \[\implies o((a + 1)b)_p \mid p - 1 \text{ and } o((a + 1)b)_p \mid n \implies o((a + 1)b)_p \mid \gcd(n, p - 1).\]However as $p$ is the smallest prime that divides $n$, we must have $\gcd(n, p - 1) = 1$, so that $o((a + 1)b)_p = 1$. Therefore if $b$ is to be $a^{-1}$, then $a + 1 \equiv a \pmod p \implies 1 \equiv 0 \pmod p$, which is a contradiction. Hence $\boxed{n = 1}$ is the only such solution. $\blacksquare$

Here's a worse solution than the other ones in this thread. Note that if $n=1$ then all $a$ works, so suppose $n>1$. Then $(a+1)^n \equiv a^n \mod{n} \implies \gcd(a,n)=1$. Note that $2 \nmid n$ since $2^n-1^n \equiv 1 \mod{2}$. Denote $s=\frac{a+1}{a}$. Thus $(\frac{a+1}{a})^n \equiv 1 \mod{n} \implies \mathrm{ord}_n(s) \mid n$. Suppose that order is not 1. Then for any $p^k \mid n$ we have that $s^{\mathrm{ord}_n(s)} \equiv 1 \mod{p^k}$ so $\mathrm{ord}_{p^k}(s)|\mathrm{ord}_n(s)|n$. Now note that $s^{\mathrm{ord}_{p^k}(s)} \equiv 1 \mod{p^k} \implies s^{\mathrm{ord}_{p^k}(s)} \equiv 1 \mod{p}$. So $\mathrm{ord}_{p^k}(s) \mid n, \mathrm{ord}_{p^k}(s) \mid p-1 \textrm{ or } p-1 \mid \mathrm{ord}_{p^k}(s)$. If $\mathrm{ord}_{p^k}(s) \neq 1$ then it either contains non-1 factors of $p-1$ or contains the entirety of $p-1$ which isn't $1$. Either way, it cannot divide $n$ since $\gcd(n, p-1)=1$. Thus $\mathrm{ord}_{p^k}(s)=1$ which implies $\frac{a+1}{a} \equiv 1 \mod{p^k}$ for all $p^k \mid n$, by CRT that implies $\frac{a+1}{a} \equiv 1 \mod{n} \implies n=1$. A contradiction, thus $n>1$ has no solutions.

The case $n = 1$ is trivially true, so assume $n \neq 1$. Let $p$ denote the smallest prime divisor of $n$. Note that $p \mid (a + 1)^n - a^n \implies (a + 1)^n \equiv a^n \mod{p}$. If $p \mid a + 1$, then $p \nmid a$, a contradiction. Similarly for $p \mid a, p \nmid a + 1$, and of course $p$ can't divide both $a + 1, a$ since $\gcd(a + 1, a) = 1$. Therefore, $p \nmid a, a + 1$. So,$$\left(\frac{a + 1}{a}\right)^n \equiv 1\mod{p}$$Let $\frac{a + 1}{a} = \alpha$. We have $\text{ord}_p(\alpha) \mid n$, $\text{ord}_p(\alpha) \mid p - 1$ by Fermat's Little Theorem, so $\text{ord}_p(\alpha) \mid \gcd(n, p - 1)$. Note that that $\gcd(n, p - 1) = 1$, else we have a smaller prime divisor of $n$ than $p$. So, $\alpha \equiv 1\mod{p} \implies a + 1 \equiv a \mod{p}$, an obvious contradiction. Hence, we are done.

We claim that the only pairs of solutions are $(a,n)=(m,1)$ for all positive integers $m$. It is easy to see that all such pairs are indeed solutions. Now, we show that they are the only ones. When $n>1$ and $n$ is even, \[2\mid n \mid (a+1)^n-a^n\]But it is clear that the right hand side is odd, which is a clear contradiction. Thus, any solution must have odd $n$. When $n>1$ and $n$ is odd, consider the smallest prime factor $p$ of $n$. Clearly $p\nmid a,a+1$ since these are relatively prime. Further, \begin{align*} (a+1)^n &\equiv a^n \pmod{p}\\ \left(\frac{a+1}{a}\right)^n \equiv 1 \pmod{p} \end{align*}Thus, $\text{ord}_p\left(\frac{a+1}{a}\right)\mid n$. Also, we know that $\text{ord}_p\left(\frac{a+1}{a}\right) \mid p-1$ by Fermat's Little Theorem. Now, $\text{ord}_p\left(\frac{a+1}{a}\right) \ne 1$ since this implies $a+1\equiv a \pmod{p}$ which is a contradiction. Thus, there exists a prime factor $q$ of $\text{ord}_p\left(\frac{a+1}{a}\right)$. Since, $\text{ord}_p\left(\frac{a+1}{a}\right) \le p-1 < p$ it follows that $q<p$ but since $\text{ord}_p\left(\frac{a+1}{a}\right) \mid n$, this implies that $q$ is a smalle prime factor of $n$ than $p$. This is a clear contradiction! Thus, we have no solutions where $n>1$ as desired.

I claim that the only solutions are $(a,1)$ for all positive integers $a$. Clearly these work, since $1$ divides anything. Now, I claim that $n$ cannot take any other values. First, note that $n$ cannot be even, as if $n$ is even, then one of $(a+1)^n$ and $a^n$ is even and the other is odd, making the difference odd and therefore not divisible by $2$. This means that $n$ must be odd. Assume that $n$ is not $1$, and consider the smallest prime that divides $n$, or $p$. Notice that both $a+1$ and $a$ must be relatively prime to $p$, or else one of $(a+1)^n$ and $a^n$ will be divisible by $p$ while the other is not. This makes the difference not divisible by $p$, and therefore not divisible by $n$. However, if both $a+1$ and $a$ are relatively prime to $p$, modular inverses exist, so we can get that \[n\mid (a+1)^n-a^n \implies a^n\equiv (a+1)^n \mod p,\]\[\implies \left(\frac{a+1}{a}\right)^n\equiv 1\mod p,\]which implies that the order of $\frac{a+1}{a}$ mod $p$ must divide into $n$. However, notice that this order must divide $p-1$ (by FLT) and it cannot be $1$, since $\frac{a+1}{a}$ is clearly not $1$ mod $p$. This means that a number $\leq p-1$ and therefore $<p$ that is not $1$ divides into $n$, implying that a prime smaller than $p$ must divide into $n$. This is a clear contradiction to our assumption that $p$ was the smallest prime that divided $n$, meaning that no primes $p$ can divide $n$. Therefore $n$ can only be $1$, so our solutions of $(a,1)$ are the only possible solutions, which we proved worked. This finishes the problem.

Only $n=1$ (and all $a$) works. Suppose FTSOC $n>1$ and there exists $a$ such that $(a+1)^n\equiv a^n\pmod{n}$. Clearly $a$ and $a+1$ must be relatively prime to $n$ so $(1+1/a)^n\equiv 1\pmod {n}$. Let $p$ be the smallest prime factor of $n$. Then $(1+1/a)^n\equiv 1\pmod{p}$ so $1+1/a\equiv 1\pmod{p}$ because $\gcd(p-1,\,n)=1$, a contradiction. $\square$