How to decide which moduli to check when solving a "polynomial" congruence?

Question

Consider the following problem:

Find all integer solutions to $y^2 = x^5 - 4$.

The solution goes something like – check modulo 11, where $x^5 \equiv 0, \pm 1$, and then check cases to arrive at the conclusion that no solution exists. I thought about checking mod 11 as from Fermat's little theorem we get $x^{10} \equiv 1 \pmod{11}$, but it was really a lucky guess.

My question is: how can one decide which moduli to check when one has to face a "polynomial" congruence?

Answer 1

Notice that by the Legendre symbol properties we have $$ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \equiv x \pmod p $$ where $x$ can be only $-1$,$0$ or $1$. That's why if you have a $n$-th power in a diophantine equation and $2n+1$ is prime, then you're really lucky, although it is not a strange guess xd

Answer 2

You should check modulo $p=\text{lcm}(a_1,a_2,\ldots,a_n)+1$, if it is prime (here $a_1,a_2,\ldots,a_n$ are the degrees of the variables). The reason this may easily work is: by FLT (if $p\nmid x$) $$x^{\text{lcm}(a_1,a_2,\ldots,a_n)}\equiv 1\pmod {\!p}$$

and $a_ik_i=\text{lcm}(a_1,a_2,\ldots,a_n)$ for some small $k_i$ ($\forall i\in\{1,\ldots,n\}$)(I say 'small' because we're taking $\text{lcm}$ as opposed to, e.g., outright multiplying them all).

$(x^{a_i})^{k_i}\equiv 1\pmod{\!p}$ has at most $k_i$ solutions in terms of $x^{a_i}$ (see Theorem below). $k_i$ is small, so $x^{a_i}$ can only gain a small amount ($\le k_i+1$ when $p\nmid x$ constraint is removed) of remainders $\bmod p$.

Theorem: a polynomial of degree $n$ has at most $n$ zeroes $\bmod p$.

Proof: $ax\equiv b\pmod {\!p}$ has one solution. Assume that any polynomial of degree $n-1$ has at most $n-1$ roots. Consider an arbitrary polynomial $f$ of degree $n$. If it has no zeroes, we're done. Otherwise (let the root be $a$) we can write $f$ as $f(x)=(x-a)g(x)$, where $g$ is a polynomial of degree $n-1$. $f$ then must have at most $1+(n-1)=n$ zeroes. $\ \ \ \square$

Example: (Baltic Way 2012) Solve in integers: $2x^6+y^7=11$.

Solution: $2x^6\equiv\{2,8,22,27,32,39,42\}$ (WA), $y^7\equiv\{1,6,7,36,37,42\} \pmod{\!43}$ (WA).

So $2x^6+y^7\not\equiv 11\pmod {\!43}$, and equality can't be satisfied.$\ \ \ \square$