# Tricky positive diophantine equation

Find all positive integer solutions to the equation $x^3=y^5+100$.

Notice that $7^3=3^5+100$ is a solution, but I can't find any more.

P.S. I don't know any advanced number theory, just basic olympiad stuff.

• Trivially, $x \equiv y \space (mod 2)$, i.e. $x$ and $y$ are both even or both odd. – LeeNeverGup Feb 7 '14 at 13:26
• Moreover, x and y are both odd, since if they even putting $x=2a$ and $y=2b$ gives $2a^3=8b^5+25$, which is impossible. – LeeNeverGup Feb 7 '14 at 13:30
• Assume $g=gcd(x, y)$, we can put $x=gt$ and $y=gs$ and get $g^3|100$. The only solution is $g=1$, so $(x, y)=1$ or $x$ and $y$ are co-prime. – LeeNeverGup Feb 8 '14 at 18:18
• Brute force to 10,000 failed. Can someone with better computer and computer skills proceed? – LeeNeverGup Feb 9 '14 at 13:18
• Where have you found this problem? – miracle173 Feb 16 '14 at 14:42

Thanks to Edward we are morally certain that $(x,y) = (7,3)$ is the only solution. [I extended the search to all odd $y<10^9$ using the gp command

forstep(y=1,10^9,2, if(ispower(y^5+100,3),print(y)))


which took about 4 minutes and output only $3$ as expected.] Also, as a special case of Siegel's theorem on integral points we know that there are only finitely many integer solutions. The original proof is "ineffective", i.e. doesn't yield an algorithm that can be guaranteed to find all solutions; more recent work sometimes provides such algorithms, and even ones that can be carried out in practice, but they're not easy, being clearly "advanced number theory" as opposed to "basic olympiad stuff". The existence of one nontrivial solution $(7,3)$ makes it quite unlikely that an elementary proof is possible; for starters it will never be enough to just use congruences modulo a few small numbers, because once $(7,3)$ works there will always be infinitely many more surviving candidates.

One thing that makes this just a bit more tractable, and effectively solvable at least in principle, is that $100$ happens to be a square, and also cube-free, so any solution yields a pair of solutions $(\pm 10,-x,y)$ to the Diophantine equation $X^2+Y^3+Z^5=0$ in relatively prime integers. This lets us build on previous work in the paper

J. Edwards: A Complete Solution to $X^2 + Y^3 + Z^5 = 0$, Journal f. d. reine und angew. Math. (Crelle's Journal) 571 (2004), 213-236.

which completely solves this equation under the relatively-prime condition. Edwards finds $27$ identities $X_i(r,s)^2 + Y_i(r,s)^3 + Z_i(r,s)^5 = 0$, each with $X_i,Y_i,Z_i$ homogeneous polynomials of degree $30$, $20$, $12$ respectively, and shows that every solution of $X^2+Y^3+Z^5=0$ in relatively prime integers is obtained from one of these solutions by substituting some integers for $r$ and $s$. Thus any solution with $X = \pm 10$ is a solution of one of $27$ pairs of Thue equations $X_i(r,s) = \pm 10$. This count is probably exaggerated because some $i$ might be ruled out by congruence conditions, but at least one must be possible, again because we know the solution $(X,Y,Z)=(10,-7,3)$. Unless we're quite lucky, we won't be able to solve all these equations by elementary means, and since each of the polynomials $X_i(r,s)$ has degree $30$ the more advanced techniques (try $p$-adic methods first, and the Baker bounds where the $p$-adic analysis does not reach a complete solutions) could take quite some work to complete.

[added later] The sixth of J.Edwards' identities has $Z = \sum_{j=0}^{12} a_j r^j s^{12-j}$, where the coefficients $a_0,\ldots,a_{12}$ are $$3,12,-132,0,-1980,-3168,3168,12672,-39600,-10560,-61248,-26112,27072,$$ and then (as with all these identities) $Y$ is the scaled Hessian $(Z_{rr} Z_{ss} - Z_{rs}^2)/132^2$ and $X$ is the scaled Jacobian $(Y_r Z_s - Y_s Z_r) / 240$. Taking $(r,s)=(0,1)$ recovers the solution $10^2 - 7^3 + 3^5 = 0$. So we must at least prove that there are no other solutions of the degree-$30$ Thue equation $Z_6(r,s) = 10$. Since $Z_6$ is irreducible and is not positive-definite (the polynomial $Z_6(1,s)$ has four real roots), even this part of the problem seems unlikely to have an elementary solution.

• $X^2 + Y^3 + Z^5 = 0$ faintly resembles the relation satisfied by the icosahedral invariant. Can there be any serious connections? Like, for example, I suspect that thing to be isomorphic to some quotient of $X(5)$, so integral points on this curve might be equivalent to finding integral point on some modular equation? – Balarka Sen Jun 13 '14 at 12:09
• Yes, there's actually quite a close connection; in each of Edwards' parametrizations you can make a linear change of variables in $(r:s)$ so that each of $X,Y,Z$ has roots with the same icosahedral symmetry ($12$ vertices, $20$ face centers, and $30$ edge midpoints of the same regular icosahedron inscribed in the Riemann sphere). The list of parametrizations could indeed have been obtained via twists of the modular curve $X(5)$, though that's not how Edwards did it. – Noam D. Elkies Jun 14 '14 at 18:31
• Ah, nice, thanks professor. Do you know of any references that use the connection with that modular curve to derive the list of parametrizations? – Balarka Sen Jun 14 '14 at 21:26
• You're welcome. No, I don't have a reference for an $X(5)$ approach to this question, at least not yet :-) (I've carried out one part of this analysis already but haven't written it up yet.) – Noam D. Elkies Jun 14 '14 at 23:01
• OK. Will be looking forward for the write-up. – Balarka Sen Jun 14 '14 at 23:12

gcd approach: $x$ and $y$ are coprime, and both not divisible by 2, nor by 5.

Proof. Assume $g$ is the greatest common divisor of $x$ and $y$. we can put $x=gt$ and $y=gs$ to get: $$\color{red} {g^3t^3}=\color{green}{g^5s^5}+100$$ The expressions $\color{red}{g^3t^3}$ and $\color{green}{g^5s^5}$ are both divisible by $g^3$, so also $g^3|100$. The only cubic number dividing 100 is 1. So $\gcd(x,y)=1$.

Now, let $g'$ be the greatest common divisor of $x$ and 100. From $g'|x$ and $g'|100$ we can infer $g'|x^3-100=y^5$ so $g'|y^5$ and $g'|y$. But if $g'$ divides both $x$ and $y$, he must divide its gcd, hence $g'=1$ ($\gcd(100,x)=1$, or 100 and $x$ are coprime). In similar way we can show that 100 and $y$ are coprime, so $x$ and $y$ are both not divisible by neither 2 nor 5.

In this, $\gcd(a, b)$ means Greatest Common Divisor, the largest integer that divides both $a$ and $b$. If $\gcd(a,b)=1$, we say $a$ and $b$ are coprime.

Euler's and Fermat's theorems approach:

From Euler's theorem we can get some modular equation (thank to Edward for the results mod primes):

1. mod 2: As I proved above, both $x$ and $y$ are $\equiv 1$
2. $x^3\equiv x\equiv y+1 \pmod 3$
3. $x^3\equiv x\equiv y \pmod 4$
4. $x^3\equiv y \pmod 5$
5. $x^3\equiv x\equiv y+4 \pmod 6$
6. $x^3\equiv y+4 \pmod 8$
7. $x^3\equiv y \pmod{10}$
8. $x^3\equiv y+4 \pmod{12}$

By the Chinese remainder theorem, we can infer some more modular equations from that list. From 2., 4. and 6. we know that:

• $x^3=y+4+8k_1$
• $x^3=y+5k_2$
• $x^3=y+1+3k_3$

This match into one formula: $x^3 = y+n$ where n is equal to 4 mod 8, 0 mod 5 and 1 mod 3. This has a unique solution mod 120: $$x^3\equiv y+100 \pmod{120}$$ Similar way brings the formula for $x$: $$x\equiv y+4 \pmod{12}$$

Brute force approach: I run this command in python (since I don't have Matmatica nor Matlab):

[(x,y) for (x,y) in itertools.product(xrange(10), xrange(10)) if gcd(x,100)==1 and gcd(y,100)==1 and (x**3)%10==(y**5)%10]


And got that the only solutions modulo 10 are: $(1, 1), (3, 7), (7, 3), (9, 9)$

Similar command brought me the only 40 solutions modulo 100:

[(x,y) for (x,y) in itertools.product(xrange(100), xrange(100)) if gcd(x,100)==1 and gcd(y,100)==1 and (x**3)%100==(y**5)%100]


$[(1, 1), (1, 21), (1, 41), (1, 61), (1, 81), (7, 3), (7, 23), (7, 43), (7, 63), (7, 83), (43, 7), (43, 27), (43, 47), (43, 67), (43, 87), (49, 9), (49, 29), (49, 49), (49, 69), (49, 89), (51, 11), (51, 31), (51, 51), (51, 71), (51, 91), (57, 13), (57, 33), (57, 53), (57, 73), (57, 93), (93, 17), (93, 37), (93, 57), (93, 77), (93, 97), (99, 19), (99, 39), (99, 59), (99, 79), (99, 99)]$

EDIT: Divisors of x and y with brute-force:if $q|y$, then $q|y^5=x^3-100$ and $x^3\equiv100\pmod q$. Similar way shows that if $p|x$ then $y^5\equiv -100 \pmod p$. So I run some Python command to detect what $q$ and $p$ cannot be:

>>> qs=[q for q in xrange(1, 1000) if not [x for x in xrange(q) if x**3%q==100%q]]
>>> qs=[q for q in qs if not [x for x in qs if x!=q and q%x==0]]


Gave me that $y$ is not divisible by any number of:

[7, 8, 13, 19, 31, 43, 61, 67, 97, 109, 125, 151, 157, 163, 181, 193, 199, 211, 223, 229, 241, 277, 283, 307, 313, 337, 367, 373, 379, 397, 409, 433, 439, 487, 499, 523, 541, 571, 577, 601, 619, 631, 709, 727, 757, 769, 787, 811, 823, 853, 877, 883, 919, 937, 991]


By similar commands I got:

>>> ps=[p for p in xrange(1, 1000) if not [y for y in xrange(q) if y**5%p==(-100)%p]]
>>> ps=[p for p in ps if not [x for x in ps if x!=p and p%x==0]]


So $x$ is not divisible by any of:

[8, 31, 41, 61, 71, 125, 131, 151, 181, 191, 211, 241, 271, 311, 331, 401, 421, 431, 461, 491, 541, 571, 601, 631, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991]


I asked for a proper way to determine possible values of $p$ and $q$. I'll update if found better way.

As in this answer, $x^k\equiv n \pmod p$ iff $n^{\frac{p-1}{k_p}}\equiv 1 \pmod p$, where $k_p = \gcd(k,p-1)$.

In our case, we have $x^3\equiv 100 \pmod q$ iff $100^{\frac{q-1}{k_q}}\equiv 1 \pmod q$. If $k_q=(q-1, 3)=1$, the equation becomes $100^{q-1}\equiv 1 \pmod q$, which is true for every prime $q$ by Fermat's little theorem.

So suppose we have $k_q=(q-1, 3)=3$, or $3|q-1$. Now the equation becomes $100^{\frac{q-1}3}\equiv 1 \pmod q$ or $ord_q(100)|\frac{q-1}3$. Closer form seem impossible.

Interesting question. Here's a complete (EDIT: and wrong!) answer that shows that $(x=7, y=3)$ is the only solution.

First, I cheated and wrote a small computer program that evaluated all integers up to one million. Your solution $(x=7, y=3)$ was the only one found.

Second, we can observe that $x^3 - y^5 = 100$ so it's clear that $x^3 > 100$ and therefore $x \ge 5$.

Third, since $x^3 - y^5 > 0$, it's clear that $x^3 > y^5$ so $x > y$.

Now we get into a bit of number theory. Fermat's Little Theorum says that $a^p \equiv a\:\pmod p$ so we can consider the equation $\mod 3$ as follows: $$\begin{eqnarray} x^3 &\equiv& y^5 + 100 \pmod{3} \\ x &\equiv&y^5+100 \pmod{3}\\ x &\equiv&y^5+1 \pmod{3}\\ x &\equiv&y^{5 \bmod \phi(3)} + 1 \pmod{3}\\ x &\equiv&y^{5 \bmod 2} +1 \pmod{3}\\ x &\equiv&y + 1 \pmod{3} \end{eqnarray}$$

In this, the $\phi(n)$ function is Euler's totient function which is equal to $n-1$ when $n$ is a prime number. We can do a similar operation considering a rearranged version of the original equation $\mod 5$: $$\begin{eqnarray} x^3-100 &\equiv& y^5\pmod{5}\\ x^3-100 &\equiv& y\pmod{5}\\ x^3 &\equiv& y\pmod{5} \end{eqnarray}$$

Summarizing, we can assert that $x\ge 5$, $x>y$, $x\equiv y+1\pmod{3}$ and $x^3 \equiv y\pmod{5}$ for solutions to this equation.

This should probably allow us to conclude that $(x=7, y=3)$ is the only solution, but at the moment, I lack the insight to bring us to that conclusion. Perhaps this will inspire someone else to fill in that blank.

Edit:

Inspiration has come at last! As LeeNeverGup has pointed out, we know that $x$ and $y$ are both the same parity (both odd or both even) because the equation $\mod 2$ is $x \equiv y$. We can rule out both even by substituting $x=2a$ and $y=2b$ yielding $2^3a^3=2^5b^5+100 \implies 2a^3=8b^5+25 \implies 0\equiv 0+1 \pmod{2}$. Since that's not true, both $x$ and $y$ must be odd numbers.

We also know from the $\mod 3$ equation above the $x\equiv y+1 \pmod{3}$. Put another way, $x-y =3n+1$ where $n \in \mathbb{N}$ (the set of natural numbers). Since $x$ and $y$ are both odd numbers, we can substitute $x=2a+1$ and $y=2b+1$ (with $a,b \in \mathbb{N}$). This gives us $2a+1-2b-1=3n+1$. Examining this in $\mod 2$ yields $0+1-0-1\equiv n+1 \pmod{2}$ so clearly $n\equiv 1\pmod{2}$. Again we do a substitution to show this fact and we get $x-y=3(2c+1)+1; c\in\mathbb{N}$ or $x-y=6c+4$ and $y = x-6c-4$.

Substituting this into the cubic equation, we get $x^3-x+6c+4=5m$, so again looking at this equation $\mod 2$, we can see that $m \equiv 0\pmod{2}$. Once more we substitute to reflect this and get $x^3-x+6c+4=10f; f \in\mathbb{N}$.

We know that $(x=7,y=3)$ is a solution and we know that $x\ge 5$ and that $x \equiv 1 \pmod{2}$ (that is, $x$ is odd). If there is another solution, it must be of the form $x=2d+9$ where $d\in\mathbb{N}$. Given this, we can rewrite the cubic equation above: $$\begin{eqnarray} (2d+9)^3 -2d-9+6c+4&=&10f\\ (2d+9)^3 -2d+6c-5&=&10f\\ 8d^3+108d^2+484d+6c+724&=&10f \end{eqnarray}$$ If we solve for $d$ (omitting a lot of messy algebra) we get three solutions, two of which involve imaginary numbers, and therefore can be ruled out because $d \in \mathbb{N}$. That leaves us with $$d=\left(\frac{\sqrt{675f^2+\left(-810c-540\right)f+243c^2+324c+107}}{8\times 3^{\frac{3}{2}}} - \frac{-5f+3c+2}{8}\right) ^{\frac{1}{3}}+\\ {\frac{1}{12\left(\frac{\sqrt{675f^2+\left(-810c- 540\right)f+243c^2+324c+107}}{8\times 3^\frac{3}{2}}-\frac{-5 f+3c+2}{8}\right)^\frac{1}{3}}} -\frac{9}{2}$$ Substituting $$g=\left(\frac{\sqrt{675f^2+\left(-810c- 540\right)f+243c^2+324c+107}}{8\times 3^\frac{3}{2}}-\frac{-5 f+3c+2}{8}\right)^\frac{1}{3}$$ If we multiply both sides by 2, we get $$2d = 2g+\frac{1}{6g}-9$$. Since $2d$ and $9$ are integers, $2g+\frac{1}{6g}$ also must be an integer. So $\frac{12g+1}{6g} = \frac{2g + \frac{1}{6}}{g}$ must be an integer (specifically an odd integer) and so $g$ must be an odd multiple of $\frac{1}{6}$. That assertion is not correct! Therefore the rest of the proof is also erroneous and should be ignored. Thanks to @barto for pointing this out in a comment, and apologies to all for the error.

In other words $6g \in \mathbb{Z}$ and $6g \equiv 1\pmod{2}$. We can return to our definition of $g$ and substitute: $$6g=2h+1=6\left(\frac{\sqrt{675f^2+\left(-810c- 540\right)f+243c^2+324c+107}}{8\times 3^\frac{3}{2}}-\frac{-5 f+3c+2}{8}\right)^\frac{1}{3}$$ where $h \in \mathbb{N}$. $$2h+1=3\left(\frac{\sqrt{675f^2+\left(-810c- 540\right)f+243c^2+324c+107}}{3^\frac{3}{2}}+5 f-3c-2\right)^\frac{1}{3}$$
Since $2h+1$ is an odd integer, $\left(\frac{\sqrt{675f^2+\left(-810c- 540\right)f+243c^2+324c+107}}{3^\frac{3}{2}}+5 f-3c-2\right)^\frac{1}{3}$ must also be an odd integer. So $\frac{\sqrt{675f^2+\left(-810c- 540\right)f+243c^2+324c+107}}{3^\frac{3}{2}}+5 f-3c-2$ must be an odd cubic integer This implies that $\sqrt{\frac{675f^2-810cf-540f+243c^2+324c+107}{27}}$ is an integer, and so is $\frac{675f^2-810cf-540f+243c^2+324c+107}{27}$. So $675f^2-810cf-540f+243c^2+324c+107 \equiv 0 \pmod{27}$. However, each of the factors except 107 is divisible by 27 so we get $26 \equiv 0 \pmod{27}$ which is a contradiction.

Therefore $(x=7, y=3)$ is the only solution.

• Start by modulo 2: $x$ and $y$ are both odd. – LeeNeverGup Feb 7 '14 at 13:32
• Also, using Euler's theorem, $x\equiv y \space (mod\space 4)$ and $x\equiv y + 4 \space (mod\space 6)$ – LeeNeverGup Feb 7 '14 at 13:42
• Ah, I see you already mentioned this in a comment. $2^3 m^3 = 2^5 n^5 + 100 \implies 2m^3 + 8n^5 + 25 \implies 0 \equiv 0 + 1 \pmod{2}$ which is a contradiction. – Edward Feb 12 '14 at 15:35
• In you last solution there must be a mistake somewhere. (You didn't take in the fifth power, so it is very unlikely to be true.) You concluded that the equation $x^3-x+6c+4=10f$ has no solutions, but sure it does. Take for example $x=11$, $c=1$ and $f=133$. Unless I'm missing some important detail... – punctured dusk Feb 14 '14 at 18:11
• @barto: You're right and there's an error. I asserted that because $2d = 2g+\frac{1}{6g}-9$, $g$ must be an odd integral multiple of $\frac{1}{6}$ but that's not correct. Solving for $g$ in terms of $d$ in that equation gives: $g = \pm \frac{\sqrt{3}\sqrt{12d^2+108d+239}-6d-27}{12}$, so the rest of the "proof" after that is faulty. – Edward Feb 14 '14 at 19:17

Again not a complete solution, just some new insights...

The fact that you already know a solution makes it interesting. It allows us to rewrite the equation as $$x^3-7^3=y^5-3^5,$$ or $$(x-7)(x^2+7x+49)=(y-3)(y^4+3y^3+9y^2+27y+81).$$ Note that every prime divisor of $\frac{x^3-7^3}{x-7}$ is either $3$ or congruent to $1$ modulo $3$. Similarly, every prime divisor of $\frac{y^5-3^5}{y-3}$ is either $5$ or congruent to $1$ modulo $5$. (This is all due to a more general result involving cyclotomic polynomials of primes.)

The factor that 'makes' the RHS large is $y^4+3y^3+9y^2+27y+81$. The fact that this can only have primes $\equiv0,1\pmod5$ suggests that there will not be many solutions as $x^3-7^3$ might have a lot of prime divisors that have to divide $y-3$. Finding a close upper bound on the primes dividing $x^3-7^3$ that are $\equiv0,1\pmod5$ possibly will exclude further solutions.

I'll start off considering an easy case. If $x-7\mid\frac{y^5-3^5}{y-3}$ then either $x\equiv2$ or $x\equiv3\pmod5$. In any case $x^2+7x+49$ is not congruent to $0$ or $1$ modulo $5$, so it should have some divisor $>1$ in common with $y-3$. We want this divisor to be big in order to obtain a contradiction.

Perhaps finding an upper bound on $\gcd(x-7,y-3)$ might help. Certainly the $\gcd$ should divide $3x-7y$ but I can't really make anything interesting of this.