Take $p$ divides $n$, so $a^3+a$ for $a={1,...p-1}$ $a^3+a$ needs to be ${1,...p-1}$ in some order. Clearly $p=2$ fails. Now, that means, the product of $a$ over $1 \le a \le p-1$ is equal to the product of $a^2+1$ over this. Dividing this through by $(p-1)!$, the product $(a^2+1)$ must be $1$ mod $p$, where it is taken over $0<a<p$. But this is the square of the product of the roots of $(x-1)^{\frac {p-1} {2} } = 1$ in mod $p$, which is $0$ or $4$. So $p$ divides $1$ or $3$ and $p=3$ is forced. Checking that powers of $3$ work is not hard using induction. If $a^3+a=r$ mod $3^k$, then $a^3+a$ is one of $r$, $r+3^k$, $r+2(3^k)$. But plugging in $a+3^r$ and $a+2(3^r)$ lets us cover all residues. Trivially $k=1$ works, so powers of $3$ is our answer.

Suppose $x^3 + x$ is a bijective map on the integers modulo $n$. Then take some prime $p|n$. As $f$ is bijective modulo $n$, it must also be bijective modulo $p$. Due to the fact $f(0) \equiv f(1) \pmod{p}$, we know $p$ is an odd prime. Let $f(x) = x^3 + x$. We have $f(0) = 0$ so we must have: \[ \prod_{x=1}^{p-1} f(x) \equiv (p-1)! \pmod{p} \] \[ (p-1)! \cdot \prod_{x=1}^{p-1} (x^2 + 1) \equiv (p-1)! \pmod{p} \] \[ \prod_{x=1}^{p-1} (x^2 + 1) \equiv 1 \pmod{p} \] Now, we have: \[ \prod_{x=1}^{p-1} (x^2 + 1) \equiv \prod_{x=1}^{p-1} (x+i) \cdot \prod_{x=1}^{p-1} (x-i) \equiv (i^{p-1} - 1)^2 \equiv 2-2i^{p-1} \pmod{p} \] where computations are done in $\mathbb{F}_{p^2}$. As $i^{p-1} \equiv \pm 1 \pmod{p}$, it follows we must have $2\pm 2 \equiv 1 \pmod{p}$, implying $p=3$. Thus the only prime divisor of $n$ must be $3$ so $n$ is a power of $3$. We shall prove all powers of three work. First remark that for $n=3$, $f(0) = 0, f(1) = 2, f(2) = 1$ so it works for $p=3$. Now, $f'(x) = 3x^2 + 1$ which has no root modulo $3$ so by Hensel's Lemma $f(x)$ is bijective modulo $3^k$ for all $k$. Thus $n$ works iff $n$ is a power of three as desired.

Wait darn, your solutions are quite troll. What I had in mind (and many others): We want to construct x,y with $p \nmid x,y$ and $p \mid x^3+x-y^3-y$, so $p \mid x^2+xy+y^2+1$. Then we complete the square to get $p \mid (2x+y)^2+3y^2+ 4$. Since there are $\frac{p+1}{2}$ quadratic residues mod $p$, and $\frac{p+1}{2}+\frac{p+1}{2}> p$, we must have some $x$,$y$ with $p \mid (2x+y)^2+3y^2+ 4$. (If $x = y$, we can fudge them around a little to make them different)

Right, the solution that dinoboy and I had was not what most people did, but at least I think it is better. I know mathocean97 had a solution similar to yours.

I'm quite surprised that the official solution is much-harder-to-find than the one ksun posted (which seems to be a more intuitive and common one). the official solution used inverses modulo p, and its application is not that straightforward. I'm actually more surprised that there wasn't any alternative solution given.

very nice proof, @dinoboy. Thanks. I think this problem, some easier than 2011,2012,2013(for me)

yugrey wrote: ... But this is the square of the product of the roots of $(x-1)^{\frac {p-1} {2} } = 1$ in mod $p$, which is $0$ or $4$.... @yugrey, I don't understand this part. Could you please explain it?

Sure. Things of the form $a^2+1$ are just roots of that thing mod $p$, and each one is counted twice so we square the product.

There exist a simple solution through the Cauchy-Davenport Inequality... and... just noticed something today... can't be a coincidence 1. The term "disjoint union" appears in the paper "Olympiad Number Theory: An Abstract Perspective" by Thomas J. Mildorf 2. The Cauchy Davenport Theorem (the magic theorem for Problem 3) is found in the same paper 3. Both problems 2 and 3 are written by Warut Suksompong, from Thailand.

First, it is not hard to see that, given a $p$ prime number that divides $n$, so $x^3 + x$ is a complete system remains $\pmod {p}$. Indeed, $x^3 + x \pmod{p}$ is not a complete system remains iff there are numbers $a, b$, with $a \not \equiv_p b$, such that $a^3 + a \equiv_p b^3 + b$, and it occurs iff $(a-b)(a^2 + ab+b^2) + (a-b) \equiv_p 0 \iff$ $a^2 + ab + b^2 + 1 \equiv_p 0\iff$ $(a+ \frac{b}{2})^2 + \frac{3}{4}b^2 + 1 \equiv_p 0$ and, since $p$ is odd (it is obvious, because $1^3 + 1 \equiv_2 0^3 + 0$), changing $b \rightarrow 2c$ such that $2c \equiv_p b$, we have $(a+c)^2 + 3c^2 + 1 \equiv_p 0$ and, finally, naming $a+c = d$, we have $d^2 + 3c^2 + 1 \equiv_p 0 \iff$ $d^2 + 1 \equiv_p -3c^2$. Thus, $x^3 + x \pmod{p}$ is a complete system remains iff there aren't $c, d \pmod{p}$ such that $d^2 + 1 \equiv_p -3c^2$. But there are $\frac{p+1}{2}$ possibilities to $d^2 - 1$, and, if $3\not | p$, there are $\frac{p+1}{2}$ possibilities to $-3c^2$ too. In this way, by the pigeonhole principle, there are $c, d$ satisfying $d^2 +1 \equiv_p -3c^2$, which is a contradiction! So, follows that $p = 3$ is the only prime that divides $n$, in other words, $n = 3^k$. Finally, to check that $x^3 + x \pmod{3^k}$ is a complete system remains, see that this is equivalent to the equation $d^2 +1 \equiv_{3^k} -3c^2$ has no solution, and this is easy by $\pmod {3}$, as desired.

Here's a different solution. It's easy to see we only need to check this for odd primes. If we have $a^3+a\neq b^3+b$, then setting $b=ka$ we get $k^2-k+1\neq\dfrac{-1}{a^2} \pmod p$ for all $k\neq 1$. Setting $k=1$ gives $p\equiv 3 \pmod 4$. So we have that as $k$ varies, $k^2-k+1$ takes only quadratic residues $\pmod p$. Furthermore, if $a^2-a+1\equiv b^2-b+1$, we must have $a+b\equiv 1$. So we get that the quadratic residues $\pmod p$ are the values of $k^2-k+1$ as $k$ ranges from $1$ through $\dfrac{p+1}{2}$. Adding them up we have $\dfrac{(p+1)(p+3)}{8}\equiv 0 \pmod p$, so $p=3$. And it's easy to check all powers of $3$ work.

yugrey wrote: Take $p$ divides $n$, so $a^3+a$ for $a={1,...p-1}$ $a^3+a$ needs to be ${1,...p-1}$ in some order. Clearly $p=2$ fails. Now, that means, the product of $a$ over $1 \le a \le p-1$ is equal to the product of $a^2+1$ over this. Dividing this through by $(p-1)!$, the product $(a^2+1)$ must be $1$ mod $p$, where it is taken over $0<a<p$. But this is the square of the product of the roots of $(x-1)^{\frac {p-1} {2} } = 1$ in mod $p$, which is $0$ or $4$. So $p$ divides $1$ or $3$ and $p=3$ is forced. I have trouble understanding how we must have square of the product solutions of $x$ to be $0$ or $4$

Depending on what p is mod 4 the last coefficient is either 0 or -2, so the square is 0 or 4.

If I understand correctly, yugrey is using Viete's formula for a product of roots of a polynomial, which apparently holds in $Z/pZ$. I am pretty confused about the theory of polynomials in $Z/pZ$. Does a polynomial of degree $n$ always have $n$ solutions in $Z/pZ$ if $n<p$? And how can we prove Viete's in $Z/pZ$.

ksun48 wrote: Wait darn, your solutions are quite troll. What I had in mind (and many others): We want to construct x,y with $p \nmid x,y$ and $p \mid x^3+x-y^3-y$, so $p \mid x^2+xy+y^2+1$. Then we complete the square to get $p \mid (2x+y)^2+3y^2+ 4$. Since there are $\frac{p+1}{2}$ quadratic residues mod $p$, and $\frac{p+1}{2}+\frac{p+1}{2}> p$, we must have some $x$,$y$ with $p \mid (2x+y)^2+3y^2+ 4$. (If $x = y$, we can fudge them around a little to make them different) Can someone please explain the $\frac{p+1}{2}+\frac{p+1}{2}> p$ part? How does that show that there exists a pair $x,y$ for which the sum of squares expression is divisible by $p$?

viperstrike wrote: ksun48 wrote: Wait darn, your solutions are quite troll. What I had in mind (and many others): We want to construct x,y with $p \nmid x,y$ and $p \mid x^3+x-y^3-y$, so $p \mid x^2+xy+y^2+1$. Then we complete the square to get $p \mid (2x+y)^2+3y^2+ 4$. Since there are $\frac{p+1}{2}$ quadratic residues mod $p$, and $\frac{p+1}{2}+\frac{p+1}{2}> p$, we must have some $x$,$y$ with $p \mid (2x+y)^2+3y^2+ 4$. (If $x = y$, we can fudge them around a little to make them different) Can someone please explain the $\frac{p+1}{2}+\frac{p+1}{2}> p$ part? How does that show that there exists a pair $x,y$ for which the sum of squares expression is divisible by $p$? The set of numbers in $\{(2x+y)^2\}$in modular $p$ has $\frac{p+1}{2}$ elements. The set of numbers in $\{-3y^2-4\}$ in modular $p$ has $\frac{p+1}{2}$ elements. Since there are $p$ numbers in modular $p$, there must be an element that appears in both sets. Take such element.

Ok I understand now. However what happens if the pair $(x,y)$ which satisfies $p|(2x+y)^2+3y^2+4$ turns out to have $x=y$? What do we do?

@viperstrike If $p \mid (2x+y)^2+3y^2+4$ and $x \equiv y \equiv a \pmod p$, then $12a^2+4 \equiv 0 \pmod p$. Take $x' \equiv -a$ and $y' \equiv 2a$. Then $(2x'+y')^2+3(y')^2+4 \equiv 12a^2+4 \equiv (2x+y)^2+3y^2+4 \equiv 0 \pmod p$. If $x'$ and $y'$ are distinct, then this is a valid modification. If $x' \equiv y' \pmod p$, then $3a \equiv 0 \pmod p$. If $p \neq 3$, then $a \equiv 0$ which leads to $p \mid 4 \Rightarrow p = 2$, which was already ruled out. This leaves $p = 3$ which leads to an answer of yes for powers of $3$, as proven above.

Meh, might as well post the following, it is not as nice as the above tho rafayaashary1 wrote: By CRT it suffices to consider powers of primes. Essentially we want $x^3+x\equiv y^3+y\text{ (mod }p^{\alpha})$ to have no solutions save $x-y\equiv 0\text{ (mod }p^{\alpha})$. Via Algebraic manipulation this is equivalent to showing that $x^2+xy+y^2+1\equiv 0\text{ (mod }p^{\alpha})$ has no solutions. Treating this as a quadratic in $x$ and completing the square we want $\left(\tfrac{-3\cdot2^{-2}y^2-1}{p^{\alpha}}\right)=-1$ for all $y\not\equiv x\text{ (mod }p)$. But since $\left(\tfrac{1}{p^{\alpha}}\right)=\left(\tfrac{4}{p^{\alpha}}\right)=\left(\tfrac{9}{p^{\alpha}}\right)=1$ there two consecutive quadratic nonresidues $\text{ (mod }p^{\alpha})$. Since $\sqrt{p}-\sqrt{0.5p}>1$ there exist two consecutive integers such that the larger is a quadratic residue, but the smaller is a nonresidue. Hence the only possibilities are when $p\in\{2,3\}\text{ or }p^{\alpha}\in\{5,7,11\}$. The last four cases are all easy to check manually, and none work. $p=2$ is also easy to check since the output is always even, and hence a complete residue set cannot be achieved. Finally, a complete set of residues is formed modulo $3$, and if a complete set is formed $\text{ (mod }3^{\alpha})$, then $(x+\{0,1,2\}3^{\alpha})^3+x+\{0,1,2\}3^{\alpha}\equiv x^3+x+\{0,1,2\}3^{\alpha}\text{ (mod }3^{\alpha+1})$, also a complete residue set. We conclude that the answer is all $\boxed{n=3^{\alpha}}$

Note the problem statement is equivalent to finding all positive integers $n$ in which $a^3+a$ is surjective $\pmod{n}$. Let $p$ be a prime such that $p \mid n$. Notice that $a^3+a$ must also be surjective $\pmod{p}$. Now we require$$\prod_{a = 1}^{p-1} a(a^2+1) = (p-1)! \pmod{p}$$This implies that$$\prod_{a=1}^{p-1} a^2+1 = 1 \pmod{p}$$If $p \equiv 1 \pmod{4}$, we have $\prod_{a=1}^{p-1} (a+x)(a-x) = 1 \pmod{p}$, where $x = \sqrt{-1}$. However, this obviously cannot be true because the product is $0 \pmod{p}$. We have $p \equiv 3 \pmod{4}$. We can now work in $\mathbb{F}_p[i]$. The product turns into $\prod_{a=1}^{p-1} (i+a)(i-a) = \prod_{a=1}^{p-1} (i+a) \cdot \prod_{a=1}^{p-1} (i-a) = (i^{p-1} - 1)^2 \pmod{p}$. The last step is due to how everything cancels mod $p$ due to Vieta's. Because $p \equiv 3 \pmod{4}$, this simplifies to $4$, which implies that $p$ must be $3$. We will now prove all numbers of the form $3^b$ where $b$ is a nonnegative integer work by induction. Our base cases of $b = 0, 1$ work. Assume $f(a) = a^3+a$ is surjective $\pmod{3^b}$. Let $n$ be an integer $1 \le n \le 3^b$. Notice that $f(n+3^k) = (n+3^k)^3+n = n^3+n+3^k \pmod{3^{k+1}}$. Therefore $f(n)$ is surjective $\pmod{3^{k+1}}$ and we are done.

This is a somewhat boring problem. It suffices to find all primes $p$ that work. On the other hand, the condition is equivalent for there not to exist any $(a, b)$ such that $$a^2+ab+b^2\equiv -1 \pmod p$$as the map $a \to a^3+a$ must be surjective in $\mathbb F_p$. Working in $\mathbb F_p$, $\Delta = -4-3b^2$ cannot be a quadratic residue. On the other hand, for $p \neq 3$, $\Delta$ can take one of $\frac{p-1}2$ distinct values, but on the other hand each of $\frac{p+1}2$ quadratic residues for $b^2$ yields a different $\Delta$. This is an evident contradiction. As a result, only $p=3$ can divide $n$, and it is easy to see that all powers of $3$ indeed work, say by induction.

This is essentially saying "for which positive integers $n$ is $a^3+a$ surjective mod $n$". In mod $n$, surjective is the same as injective. Claim: primes $p\neq 3$ do not work. Clearly, 2 does not work since it is always even. Now, we will show that for any prime $p\geq 5$, there exists a solution $(a,b)$ to the equation $$a^3+a\equiv b^3+b\pmod{p}$$but $a\neq b\pmod{p}$ (which will show that it hits the same thing twice and is therefore not injective). Assuming that $a\neq b\pmod{p}$, factor out a factor of $a-b$ to get $$a^2+ab+b^2\equiv -1\pmod{p}.$$We then complete the square: $$(a+\frac{b}{2})^2\equiv -\frac{3}{4}b^2-1\pmod{p}.$$(Since $p$ is odd, these fractions are allowed). For any given $b$, this has a solution in $a$ when $-3b^2-4$ is a quadratic residue. When $p\neq 3$, $-3b^2-4$ spans $(p+1)/2$ different residues as $b$ varies. However, there are only $(p-1)/2$ nonresidues, so it has to hit a quadratic residue at some point, thus resulting in a solution. Therefore, primes $p\neq 3$ do not work. If the expression is not even surjective mod $p$, then it is also not surjective mod $mp$ for any positive integer $m$ (as it will still have holes every mod $p$), so this means that $n$ must be a power of 3. We finish with induction to show that all powers of 3 work. Clearly, $n=3$ works. Now, suppose that $3^k$ works. Note that $$(a+3^k)^3+(a+3^k)\equiv a^3+a+3^k\pmod {3^{k+1}}.$$We already know that when $a$ varies over residues mod $3^k$, it is surjective mod $3^k$. Since shifting $a$ up by $3^k$ also shifts the expression up by $3^k$ mod $3^{k+1}$, it is still surjective mod $3^{k+1}$, done.

I claim that the answer is that $n$ must be a power of $3$. The problem is equivalent to finding all $n$ such that $\{a^3+a\}$ are all distinct in $\mathbb{Z}_n$, call such an $n$ good. Lemma. A number $n$ is good only if all primes $p\mid n$ are good. Proof. Note that if $p\nmid n$ is not good, then there are $a,b$ such that $a\ne b\pmod{p}$ and $a^3+a\equiv b^3+b\pmod{p}$. But this pair $(a,b)$ can be lifted via CRT to a pair $(a',b')$ such that $a'\ne b'\pmod{n}$ and $a'^3+a'\equiv b'^3+b'\pmod{n}$. Hence it suffices to show that $3$ is the only good prime. It can be checked that $3$ is good very easily. Suppose $p$ is not $3$ and $p$ is good. Additionally, assume $p$ is odd because $p=2$ fails. Then for all $a,b\in \mathbb{Z}_p$, $a^3+a\equiv b^3+b\pmod{p}$ implies $a\equiv b\pmod{p}$. Note $$a^3-b^3+a-b\equiv 0\pmod{p}\implies (a-b)(a^2+ab+b^2+1)\equiv 0\pmod{p}$$Thus the equation $$a^2+ab+b^2+1\equiv 0\pmod{p}$$Has no solutions. By the quadratic formula, this means that $\sqrt{-3b^2-4}\notin \mathbb{Z}_p$ for all $b$. First note that if $-1$ is a QR modulo $p$, i.e. $x^2\equiv -1\pmod{p}$ for some $x$, there is a contradiction by plugging $b=x$.Thus $-1$ is not a QR modulo $p$. Hence the map $\sigma:\mathbb{Z}_p\to\mathbb{Z}_p$ with $\sigma(x)=3x+4$ sends QRs to QRs. Since it's bijection as $p\ne 3$, it sends QNRs to QNRs. However $\sigma(-1)=1$, a contradiction. Therefore $n$ must be a power of $3$. To see that this works, we may use Hensel's lemma on $f(x)=x^3+x-t$ for some $t\pmod{3^k}$. Note $f'(x)=3x^2+1\ne 0\pmod{3^r}$ for all $r$. Therefore there's a unique solution to $x^3+x-t\equiv 0\pmod{3^k}$ for all $t$ by Hensel's because there's a unique solution to $x^3+x-t\equiv 0\pmod{3}$.

Kinda overkill but I believe that does it for the $p=3$ part By Dirichlet and CRT take a prime $q$ with $q\equiv -1\pmod p$ and $q\equiv 1\pmod 3,$ then $q$ can be written of the form $a^2+ab+b^2$(a well known result of thue's lemma mentioned in modern olympiad number theory) thus $q+1=a^2+ab+b^2+1\equiv 0\pmod p,$ if $a\not\equiv b\pmod p$ we are done but $a\equiv b$ then we have $3a^2+1\equiv 0\pmod p$ thus $a^2+(-2a)a+(2a)^2\equiv 3a^2\equiv 1\pmod p,$ since $a\not\equiv -2a\pmod p$ since neither $a$ nor $3$ is divisible by $p$ thus this value of $p\ne3$ does not work

The answer is exactly all $n = 3^k$. Note $n = 1$ is trivially true. Now, note that the truth of $n$ is equivalent to the composite truth of its prime powers, so consider $n = p^k$ for $k \geq 1$. In particular, if $p^k$ is true, then $p$ should also be true. Now the statement is equivalent to the claim that $f: x \to x^3 + x$ is bijective on $\mathbb{Z}/p\mathbb{Z}$. First, notice that injectivity is equivalent to this fact. It suffices to determine the existence of distinct $x, y$ such that: $$(x-y)(x^2+xy+y^2 + 1) \equiv 0 \pmod p \Longleftrightarrow y^2 + xy + x^2 + 1 = 0$$ By the quadratic formula, the value of such a solution $y$ given $x$ is $\frac{-x \pm \sqrt{x^2 - 4(x^2 + 1)}}{2}$. First, it follows that we must choose $x$ such that $-3x^2 - 4$ is a quadratic residue modulo $p$. If $p \not \equiv 3 \pmod 4$ then choosing $x = 0$ suffices, and it is clear the the value of $y$ is nonzero, so we reach contradiction. Otherwise, $x \to -3x^2 - 4$ maps into a set of $\frac{p+1}{2}$ residues modulo $p$ by quadratic residues, and there are $\frac{p+1}{2}$ quadratic residues modulo $p$, so by pigeonhole it follows that there exists a choice of $x$ that gives a valid choice of $y$. The only way this choice doesn't disprove $p$ is if both choices of $y$ equal $x$ exactly, violating the distinct clause. This means that $y = \frac{-x}{2} = x$, so it follows that $p = 3$. Now to prove that $p = 3^k$ works for all positive $k$, we claim that $f: x \to x^3 + x$ is injective. Note that if $x \equiv y \pmod 3$ then $x^2 + xy + y^2 \equiv 0 \pmod 3$ so $v_3(x^3+x - y^3 - y) = v_3(x-y) < k$, finishing as desired. Furthermore if $x \not \equiv y \pmod 3$ then $x^3 + x \equiv 2x \not \equiv 2y \equiv y^3 + y \pmod 3$, finishing as desired. Thus we are done.

The answer is powers of $3.$ First we show that the only prime that holds is $p=3.$ If $a^3+a\equiv b^3+b\pmod p,a\not\equiv b\pmod p$ we have $a^2+ab+b^2+1\equiv 0\pmod p.$ Clearly $a,b$ are both not $p$ so WLOG that $b\not\equiv 0\pmod p$ and write this as $\left(\frac ab\right)^2+\left(\frac ab\right)+1+\left(\frac1b\right)^2\equiv 0\pmod p.$ Let $\frac ab\equiv m,\frac1b\equiv n\not\equiv 0\pmod p.$ This becomes $m^2+m+1\equiv -n^2\pmod p.$ We want to find $p$ such that this has no solutions. Clearly $p\not\equiv 1\pmod 4$ by taking $m=0.$ Also $p\ne 2,$ so $p\equiv 3\pmod 4.$ Now we want to find $p$ such that $\{k\mid m^2+m+1\equiv k\pmod p\}$ and $\{k\mid -n^2\equiv k\pmod p,k\ne 0\}$ are disjoint. However we see that the first set has $\frac{p+1}2$ elements and the second has $\frac{p-1}2,$ so they must be complements, and the complement of the second set is the set of quadratic residues. Now we want to show that for all $m$ there exists an $n$ such that $m^2+m+1\equiv n^2\pmod p.$ Set $n=m+k$ and we want to show for all $m$ there exists $k$ such that $m+1\equiv 2mk+k^2\pmod p,$ or $(2k-1)m\equiv 1-k^2\pmod p.$ If $k=\frac{p+1}2$ we can check that there are no solutions unless $p=3,$ and for other values of $k$ there is exactly one solution for $m.$ However, this means that as $k=0,1,\dots,p-1$ there are at most $p-1$ solutions for $m,$ which is a contradiction. Thus $p=3$ and we may check this works. Now it is clear that for any possible $n$ we must have its only prime factor is $3.$ Now we show powers of $3$ work. Suppose $a^3+a\equiv b^3+b\pmod{3^k}.$ This becomes $(a-b)(a^2+ab+b^2+1)\equiv 0\pmod{3^k},$ but a simple $\pmod 3$ check shows that $a^2+ab+b^2+1\not\equiv 0\pmod 3,$ so by $\nu_3$ we must have $a\equiv b\pmod 3^k.$ Thus all powers of $3$ work.

Our answer is $\boxed{n = 3^k, \quad k \in \mathbb{Z}_{\ge 0}}$. Notice we require $f(x) \equiv x^3+x \pmod n$ to be injective modulo $n$. Assume FTSOC $f(a) \equiv f(b)$ has no solution other than $a \equiv b \pmod p$. Since we can also find $p \neq 2$, this gives the congruence (which we assume has no solutions) \[a^2+ab+b^2+1 \equiv 0 \implies (2a+b)^2+4 \equiv -3b^2 \pmod p.\] If $p \neq 3$, then both sides can attain $\frac{p+1}{2}$ values, and thus Pigeonhole guarantees a solution. However, we still need to check to make sure $a=b$ will not be the only solution; indeed, we can see that $a=b$ holding gives another solution where $b = p-2a$. This concludes the desired contradiction. To show all powers of three work, we use induction on $n = 3^e$, where $e = 0,1$ are trivial. Using the injectivity of $f(x)$ modulo $3^e$, it suffices to show $f(x+d \cdot 3^e) \not\equiv f(x) \pmod{3^{e+1}}$, where $d=1,2$. This holds from expansion: \[f(x+d \cdot 3^e) \equiv x^3+x+d \cdot 3^e \not\equiv x^3+x \equiv f(x) \pmod{3^{e+1}}. \quad \blacksquare\]

Bruh why is solution so much longer than the others The answer is only powers of $3.$ We only need to consider $a < n,$ since we only care about the remainder when $a$ is divided by $n.$ So, we can consider $$f(a):\{0, 1, \dots, n-1\} \to \{0, 1, \dots, n-1\},$$the function taking $a$ to $a^{3}+a \pmod n.$ If this function is surjective, which is what we want, then it is equivalent to being injective; i.e. $$a^{3}+a \equiv b^{3}+b \pmod n$$implies $a \equiv b \pmod n.$ We can factor this equation to $$(a-b)(a^{2}+b^{2}+ab+1) \equiv 0 \pmod n.$$We will use this equation to do both directions of the problem. Firstly, we show that $n = 3^{k}$ works. If $3|a-b,$ then $$a^{2}+ab+b^{2}+1 \equiv 1 \pmod 3, $$so for the equation to be satisfied we would need $a \equiv b \pmod n.$ If $3 \not | a-b,$ then we need to have $$a^{2}+ab+b^{2}+1 \equiv 0 \pmod n.$$But, since $3$ cannot divide $a^{2}+ab+b^{2}+1,$ this case is impossible. Thus, our function $f$ is injective, and we are done. Next, we show that any other $n$ does not work. Claim: If $$a^{2}+ab+b^{2}+1 \equiv 0 \pmod p, $$for some prime $p$ positive integers $a,b,$ then we have $$a^{2}+ab+b^{2}+1 \equiv 0 \pmod {p^{k}} $$for all positive integers $k.$ We proceed by induction on $k.$ The base case is by assumption. For the inductive step, let $k$ satisfy this. If we have $$a^{2}+ab+b^{2}+1 \equiv 0 \pmod {p^{k}},$$then if we set $a^{\prime} = p^{k}r + a,$ and $b^{\prime} = q^{k}r + b,$ solving $$(a^{\prime})^{2}+a^{\prime}b^{\prime} + (b^{\prime})^{2}+1 \equiv 0 \pmod {p^{k+1}} $$yields a linear equation in $r$ and $q.$ Now, this linear equation must have solutions, since otherwise we would have $p|a,b,$ a clear contradiction to the fact that $$a^{2}+b^{2}+ab+1 \equiv 0 \pmod p.$$ Claim: If $S$ is the set of primes $p$ so that $$a^{2}+b^{2}+ab+1 \equiv 0\pmod p $$has integer solutions, then $n$ cannot be divisible by any number in $S.$ Notice that, if $p^{k}|n,$ and $p \in S,$ then we can find such $a,b$ which satisfy $$a^{2}+ab+b^{2}+1 \equiv 0 \pmod {p^{k}}$$by the first claim. Taking some $x,y,$ with $x \equiv a \pmod {p^{k}},$ and $y \equiv b \pmod p^{k},$ and $$x \equiv y \pmod {\frac{n}{p^{k}}} ,$$which exist by the Chinese Remainder Theorem, we see that these numbers satisfy $x^{3}+x \equiv y^{3}+y \pmod n,$ and these are different $\pmod n,$ so $n$ does not work. Claim (To finish off): $S$ consists of the primes $p$ which are not $3.$ We will first check $2 \in S.$ Notice that $1^{2}+1^{2}+1 \cdot 1 + 1 \equiv 0 \pmod 2,$ so $2 \in S.$ Now, for $p > 3, $ we can simplify the equation $$a^{2}+ab+b^{2}+1 \equiv 0 \pmod p $$to $$\frac{3}{4}(a+b)^{2} + \frac{1}{4} (a-b)^{2} \equiv -1 \pmod p, $$or $$3(a+b)^{2}+(a-b)^{2} \equiv -4 \pmod p. $$Now, we consider the set $A$ which is the set of $x < p$ for which $-4-3x^{2} $ is a quadratic residue modulo $p.$ We want all $p$ for which $A$ is nonempty. Notice that $$|A| = \frac{1}{4} \sum_{a=1}^{p-1} \left(\left(\frac{a}{p}\right)+1\right)\left(\left(\frac{-3-4a}{p}\right)+1\right) + \frac{1}{2} \left(\left(\frac{-1}{p}\right)+1\right) $$since the expression inside the parenthesis is $4$ if both of the Legendre symbols are $1,$ and $-1$ otherwise (Unless we have $a=0,$ which is the extra case outside the parenthesis). Expanding gives $$\frac{p}{4} + \sum_{a=1}^{p} \left(\frac{a}{p}\right) + \sum_{a=1}^{p} \left(\frac{-3-4a}{p} \right) + \sum_{a=1}^{p} \left(\frac{a}{p}\right) \left(\frac{-3-4a}{p}\right) + \frac{1}{2} \left(\frac{-1}{p} \right) +\frac{1}{2}. $$For $p \neq 2, 3$ the first sum is $0$ and the second sum is the negative of the legendre symbol of $-1$ modulo $p. $ Then, the last sum is $$\sum_{a=1}^{p} \left(\frac{a}{p}\right) \left(\frac{-3-4a}{p}\right) = \sum_{a=1}^{p} \left(\frac{a^{-1}}{p}\right)\left(\frac{-3-4a}{p}\right) = \sum_{a=1}^{p} \left(\frac{-3a^{-1}-4}{p}\right) = -\left(\frac{-1}{p} \right). $$So, we get $$|A| = \frac{p}{4} + \frac{1}{4}\left(\frac{-1}{p} \right) + \frac{1}{2} \ge \frac{p+1}{4} \ge \frac{3}{2},$$so there must be at least $1$ possible solution. Hence, we have proven the claim. Notice that this concludes the problem, since then we know that the prime factor $n$ can have is $3.$

First, we can see that if we have a prime p that divides n, $x^3 + x$ is a complete system remains $\pmod {p}$. If $x^3 + x \pmod p$ is not a complete system remains there exist a, b, with $a \not \equiv b \pmod p$, such that $a^3 + a \equiv b^3 + b \pmod p$, and we get that $(a-b)(a^2 + ab+b^2) + (a-b) \equiv 0 \pmod p \iff$ $a^2 + ab + b^2 + 1 \equiv 0 \pmod p \iff$ $(a + \frac{b}{2})^2 + \frac{3}{4}b^2 + 1 \equiv 0 \pmod p$. Now p is odd since $1^3 + 1 \equiv 0^3 + 0 \pmod p$, and using that p is odd we can change $b \rightarrow 2c$ such that $2c \equiv b \pmod p$, we have $(a+c)^2 + 3c^2 + 1 \equiv 0 \pmod p$ and now if we denote $a+c = d$, we have $d^2 + 3c^2 + 1 \equiv 0 \pmod p \iff$ $d^2 + 1 \equiv -3c^2 \pmod p$ $\Rightarrow$ $x^3 + x \pmod{p}$ is a complete system remains if and only if there aren't $c, d \pmod p$, for which $d^2 + 1 \equiv -3c^2 \pmod p$. The set of numbers in $\{d^2-1\}$ mod p has $\frac{p+1}{2}$ elements and the set of numbers in $\{-3c^2\}$ mod p has $\frac{p+1}{2}$ elements. Since there are p residues mod p, there must be an element that is in both sets $\Rightarrow$ there are c, d for which $d^2 +1 \equiv -3c^2 \pmod p$, which is impossible. So now it follows that p = 3 is the only prime that divides n $\Rightarrow$ $n = 3^k$. The only thing left to do is prove that every $n = 3^k$ works. We will use induction for this. Obviously n=3 works. Assume that $n=3^k$ works. We must now show that $n=3^{k+1}$ works. Let $a \in \{0,1,2 \}$. It is only left to show that $x^3+x+3^ka \pmod 3^{k+1}$ is a complete residue system, which is true $\Rightarrow$ the only solutions are $n = 3^k$.

Spent 3 days on this, didn't get anywhere, gave up, and looked at the sol

Solved with RM1729 Note that it suffices to find when $f(x)=x^3+x$ is bijective modulo $n$. Firstly I find all primes $p$ such that $x^3+x$ is bijective modulo $p$, since any $n$ where $f$ is bijective modulo $n$ must be divisible by such primes. The key realisation is that for such primes $p$, we can get $$\prod_{k=1}^{p-1} (k^2+1)\equiv 1 \pmod{p}$$by finding the product of all residues modulo $p$ in two different ways. But expanding $\prod_{k=1}^{p-1} (k^2+1)$ using primitive roots, we get that for $p\neq 3$, the product is $2$. This gives that no prime not equal to 3 works, and checking that $x^3+x$ is bijective modulo 3 is trivial. This means that the only $n$ that can work are those that are powers of 3, and its not so hard to see that all powers of 3 work with Hensel's lemma.

I am sorry if I missed some important details as I did this problem months ago

Solution: Only $n=3^k$ work: Denote by good and bad integers the ones which satisfy and don't satisfy the problem's condition, respectively and note that this condition is equivalent to finding out for which $n$ there exists a bijection between $f(a)\equiv a^3+a \pmod{n}$ and $\{0,1,2\dots \}$, where $a\in\{0,1,2\dots\}$, for both $a$ and $\{0,1,2\dots \}$ have $p$ possible values. Furthermore, if there existed such bijection, then we'd have $i^3+i\not \equiv j^3+j$ for $i\not \equiv j$. Take $\pmod{n=3^k}$, then $3^k\mid(i-j)(i^2+ij+j^2+1)$ for $n$ to be bad, but $v_3(i-j)\leq (k-1)$ due to $i\not \equiv j$ and $v_3(i^2+ij+j^2+1)=0$ clearly, so all $n=3^k$ work Check that $n=2$ doesn't work, for $f(0)=0, f(1)=2\equiv0\pmod{2}$, so by choosing $k=1$, there doesn't exist $k$ to satisfy the problem's divisibility. For the remaining primes, we may split them into three different categories: Claim 1: All primes $p\equiv 1 \pmod{4}$ are bad Proof: Trivially $(\frac{-1}{p})\equiv1$, so there exists $i: i^2\equiv1 \pmod{p}$, hence both $a=0,i$ yield $f(a)\equiv a(a^2+1)=0$ Claim 2: All primes $p=4k+3$ with $k\equiv1\pmod{3}$ are bad Proof: We will prove that there exist $i\not \equiv j$ such that $i^3+i \equiv j^3+j$, that is $i^2+ij+j^2\equiv -1$ (owing to $i\not \equiv j$). Clearly $(\frac{-1}{p})\equiv-1\equiv(\frac{3}{p})$, hence by choosing $j=-2i$, we have: $3i^2\equiv -1$, that is $i^2\equiv \frac{-1}{3}$, but both $-1$ and $3$ are $NQR$, so $\frac{-1}{3}$ is $QR$, proving the existence of an $i\not \equiv 0$ such that $i^2\equiv \frac{-1}{3}$ (and as $i\not \equiv 0$, then $i\not \equiv -2i=j$) Claim 3: All primes $p=4k+3$ with $k\equiv 2\pmod{3}$ are bad Proof: Again, if $i^3+i\equiv j^3+j$ ($i\not \equiv j$), then $i^2+ij+j^2\equiv -1 \pmod{p}$. By setting $j\equiv ti$, we get $i^2(t^2+t+1)\equiv-1$. Again, if there exists $t$ such that $t^2+t+1$ was a $NQR$, then $\frac{-1}{t^2+t+1}$ would be a $QR$, hence there would exist an $i\not \equiv0$ which would satisfy $i^2\equiv \frac{-1}{t^2+t+1}$. To prove that there exists such $t$, suppose $t_1^2+t_1+1\equiv t_2^2+t_2+1$, then $t_1+t_2 \equiv -1$, so consider the following $\frac{p+1}{2}$ residues: $S=\{0,1,2\dots \frac{p-1}{2}\}$, which all clearly satisfy that if $t_1\not \equiv t_2\in S$, then $t_1+t_2\not \equiv -1$, since $t_1+t_2<\frac{p-1}{2}+\frac{p-3}{2}=p-2<p-1$. We will show no $t\in S$ satisfies $t^2+t+1\equiv0$, simultaneously showing by pigeonhole that there exists the $NQR$ that we want: $0\equiv t^2+t+1 = \frac{t^3-1}{t-1}$, so $t\not \equiv1$ must have order $3$, hence $3\mid p-1$, but $p\equiv 8+3\equiv2 \pmod{3}$, proving our claim. Claim 4: If $n$ is bad, then so is $kn$ ($n,k \in \mathbb{Z}$) Proof: $n$ is bad implies there exists $r$ such that $f(a)=a^3+a$ is never $r$, that is $n\nmid a^3+a-r$, hence also $kn \nmid a^3+a -r$ for that residue $r$. It then follows that all number $n$ such that $q\mid n$ (with $q$ prime $\neq 3$) are \textit{bad} and the only possible solutions are $n=3^k$, which we've checked all work.

pi271828 wrote: We can now work in $\mathbb{F}_p[i]$. The product turns into $\prod_{a=1}^{p-1} (i+a)(i-a) = \prod_{a=1}^{p-1} (i+a) \cdot \prod_{a=1}^{p-1} (i-a) = (i^{p-1} - 1)^2 \pmod{p}$. The last step is due to how everything cancels mod $p$ due to Vieta's. What's $F_p[i]$? Is it an embedding like $Q(\sqrt n)$ with $F_p$ and the imaginary unit or something like that? Also, could you please explain which polynomial do you consider on $\prod_{a=1}^{p-1} (i+a)$ and $\prod_{a=1}^{p-1} (i-a)$ to apply Vieta? Sorry, but I only know high school math and my only way to learn this new stuff is asking you guys (in NT olympiad books, they don't really go in depth in these more advanced topics) Thanks!!!!