Find all integers $x, y \geq 1$ such that $x^{3}-y^{3}=x y+61$.

## Second Part

To solve Diophantine equations, we often use congruences by considering the equation modulo $N$. But which modulo $N$ should we choose?

- If there are $p$-th powers with $p$ prime, try $N=p^{2} p^{3}$, etc.

Indeed, if $a$ is not divisible by $p$, by Euler's theorem, $a^{p^{k-1}(p-1)} \equiv 1 \bmod p^{k}$, so $\left(a^{p}\right)^{p^{k-2}(p-1)} \equiv 1 \bmod p^{k}$, which limits the number of values taken by $a^{p}$ modulo $p^{k}$.

- When a $n$-th power (with $n$ a known integer) is involved, it can be useful to choose $N$ as a prime number congruent to 1 modulo $n$.

Indeed, in this case, $a^{N-1} \equiv 1 \bmod N$ by Fermat's little theorem, so $\left(a^{n}\right)^{\frac{N-1}{n}} \equiv 1 \bmod N$, which limits the number of values taken by $a^{n}$ modulo $N$.

- When a $n$-th power (where $n$ is the unknown), say $a^{n}$, is involved, it can be useful to choose $N=a^{k}$ (with $k$ greater than the largest supposed solution).
- When a $n$-th power (where $n$ is the unknown), say $a^{n}$, is involved, it can be useful to choose $N$ as a not too large divisor of $a^{k}-1$ for some integer $k$.

Indeed, if we know that $n$ is congruent to a fixed number modulo a certain $m$ (or takes a limited number of values modulo $m$), it may be judicious to find $N$ such that the order of $a$ modulo $N$ is $m$, or divides $m$, or is a multiple of $m$. In the first two cases, $N$ divides $a^{m}-1$, and in the last case, $N$ divides $a^{k}-1$ with $k$ a multiple of $N$.

Indeed, in the first two cases, $a^{n}$ is then constant modulo $N$, and in the third case, $a^{n}$ takes a limited number of values modulo $N$.

It can also be useful to use the fact that if $a^{k} \equiv 1 \bmod N$ and $\omega$ is the order of $a$ modulo $N$, then $a^{\omega}-1$ divides $a^{k}-1$.

- For equations of the form $a^{x}=b^{y}+c$ (with $a, b, c$ known and $x$ and $y$ unknown) having a finite number of solutions, consider $\left(x_{0}, y_{0}\right)$ the "largest", assuming $x>x_{0}, y>y_{0}$, we subtract it from the original equation to get $a^{x_{0}}\left(a^{x-x_{0}}-1\right)=b^{y_{0}}\left(b^{y-y_{0}}-1\right)$. When $a$ and $b$ are coprime, we then have $a^{x_{0}}$ dividing $b^{y-y_{0}}-1$. If $\omega$ is the order of $b$ modulo $a^{x_{0}}$, we deduce that $b^{\omega}-1$ divides $b^{y-y_{0}}-1$ and thus divides $a^{x-x_{0}}-1$. We then find a nice prime divisor of $b^{\omega}-1$ and continue step by step (we can also start from the fact that $b^{y_{0}}$ divides $a^{x-x_{0}}$) until we reach a contradiction. This is the method of Dan Schwarz (which roughly comes down to what is stated above, but may more easily provide the right modulos to consider).
(Order of magnitude)

Let $(x, y)$ be a solution. Clearly, $x>y$, and $(x-y)\left(x^{2}+x y+y^{2}\right)=x y+61$. We deduce that $x^{2}+x y+y^{2} \leq x y+61$, and thus $2 y^{2}<x^{2}+y^{2}<61$, so that $y \leq 5$. We easily verify that, conversely, only $y=5$ gives the solution $(6,5)$.