Monster among the algebra

This problem is USAMO 2005 Problem 2 . This solution is my own creation; it is probably most similar to Solution 2 on the AoPS page.

First and foremost, note that the equations can be rewritten as

$(x^3+1)(x^3+y) = 147^{157} \\ (y+1)(x^3+y) + z^9 = 157^{147}$

Since $x^3+1 | 147^{157}$ , $x$ must be even (This will become useful much later). In fact, since $147 = 3*7^2$ , we know that the only primes that can divide $x^3+1$ are 3 and 7. $x^3+1$ factors further into $(x+1)(x^2-x+1)$ , and $\gcd(x+1,x^2-x+1) = \gcd(x+1,-2x+1) = \gcd(x+1,3)$ . In particular, only one of $x+1$ and $x^2-x+1$ can be divisible by 7; more specifically, one of $x+1$ and $x^2-x+1$ must be a power of 3. (or possibly a negative power of 3).

From here, we split into cases:

• Case 1: $x=0$ or $x=2$ .

Taking both equations $\pmod{19}$ gives us, after some consideration,

$(x^3+1)(x^3+y) \equiv 2 \pmod{19} \\ (y+1)(x^3+y)+z^9 \equiv 11 \pmod{19}$

If $x = 0$ , then the first equation tells us that $y \equiv 2 \pmod{19}$ , and $6+z^9 \equiv 11 \pmod{19} \implies z^9 \equiv 5 \pmod{19}$ . Since only 1 and -1 are 9th powers $\pmod{19}$ , this is impossible. Similarly, if $x=2$ , the first equation tells us that $72+9y \equiv 2 \pmod{19}$ , which can be solved to produce $y \equiv 7 \pmod{19}$ . Plugging this into the second equation tells us that $120+z^9 \equiv 6+z^9 \equiv 11 \pmod{19}$ , which is again impossible.

• Case 2: $x^2-x+1$ is a power of 3. [Note that $x^2-x$ is always nonnegative for integer values of $x$ , so we do not need to deal with the possibility that it is negative]

If $x^2-x+1 = 1$ , then $x^2-x=0$ ; since $x$ is even, we know that $x=0$ , which was covered in case 1. Similarly, if $x^2-x+1=3$ , then $x^2-x=2$ , which gives $x=2$ , which was covered in case 1.

If $x^2-x+1 = 3^k$ , with $k \ge 2$ , then $(x+1)(x-2)+3=3^k \implies (x+1)(x-2)=3^k-3$ . But $x+1$ and $x-2$ are equivalent $\pmod{3}$ , so either both are divisible by 3, or neither is. In the first case, $3^2 | 3^k-3$ , which is clearly impossible; in the other case, $3 \nmid 3^k-3$ , which is also impossible. Thus this case is impossible.

• Case 3: $x+1$ is a positive power of 3.

Once again, if $x+1=1$ , $x=0$ , and if $x+1=3$ , $x=2$ . Both of these cases are dealt with in case 1. In addition, if $x+1=9$ , $x=8$ , and $8^3+1=513$ , which is divisible by 19.

If $x+1=3^k$ with $k \ge 3$ , then we know from the gcd argument at the start that $x^2-x+1=3*7^j$ , for some positive integer $j$ . In addition, taking this $\pmod{3^k}$ gives us $3 \equiv 3*7^j \pmod{3^k} \implies 1 \equiv 7^j \pmod{3^{k-1}}$ . By some number theory argument (LTE on $7^j-1$ is what I used, but I believe there are other arguments), this implies further that $3^{k-2} | j$ . In particular, since $x^2-x+1 > x^2 > 3$ , we know that $j \ge 3^{k-2}$ . But since $x^2-x+1 < x^2+2x+1 = 3^2k$ , we also have $7^j < 3^{2k-1}$ . When $k = 3$ , this gives $7^{3^1} = 343 < 3^5 = 243$ , which is clearly false. When $k > 3$ , a simple induction argument shows that $3^{k-2} > 2k-1$ , so since $7>3$ , clearly the inequality cannot hold. Thus there are no solutions in this case.

• Case 4: $x+1$ is a negative power of 3. (that is, the negative of some power of 3)

Here, we have slightly different base cases from case 3: $x+1=-1 \implies x=-2$ , and $x+1=-3 \implies x=-4$ . In these base cases, we can do a similar analysis to that in case 1: $x=-2 \implies y=5 \implies z^9=10$ , which is impossible, and $x=-4 \implies y=13 \implies z^9=3$ , which is impossible. Just like in case 3, $x+1=-9 \implies x=-10 \implies x^3+1=-999$ , which is divisible by a number distinct from 3 or 7 (37 in particular). When $k \ge 3$ , we once again have that $x^2-x+1=3*7^j \implies 7^j \equiv 1 \pmod{3^{k-1}}$ , which implies that $3^{k-2} | j$ , and once again $j > 0$ by bounding $x^2-x+1$ from below. Here's where things get different from case 3: since $x$ is negative, $x^2-x+1 > x^2+2x+1$ , so instead we have to use $x^2-x+1 < x^2-2x+1 = (x-1)^2 = (-3^k-2)^2 = (3^k+2)^2$ . However, after this, the flow is very similar: when $k = 3$ , we need $3*7^3=1029 < (3^3+2)^2=29^2 < 1000$ , which is clearly impossible. When $k > 3$ , just note that $3^k+2 < 3^{k+1}$ , so the inequality becomes $7^j < 3^{2k+1}$ . By another simple induction argument, $3^{k-2} \ge 2k+1$ for all $k \ge 4$ , and since $7 > 3$ , once again the inequality cannot hold. Thus there are no solutions in this case.

Overall, there are no solutions in any case, so there are $\boxed{0}$ solutions.

Note: in my original solution, I made a mistake and thought $\pmod{19}$ arguments did not work, so I used much messier $\pmod{73}$ arguments. For simplicity, I have used the simpler $\pmod{19}$ arguments in this solution.