For what $n$ does $x^4+y^4\equiv 0\pmod n\implies x\equiv y\equiv 0\pmod n$

Question

For what $n\in\mathbb N^*$ does it hold, for $x$ and $y$ integers, $$x^4+y^4\equiv 0\pmod n\implies x\equiv y\equiv 0\pmod n$$

I'm after a characterization of $n$ that can be efficiently tested for $n$ in the millions. A sufficient condition with few exceptions would still help.

It certainly holds if $n$ is a prime congruent to 3 modulo 4. — Gerry Myerson, Oct 29 '16 at 10:20
@Gerry Myerson: yes, that's a sufficient condition (I welcome a proof); but it is far from the "few exceptions" criteria, even among primes; e.g., 13 and 29 — fgrieu, Oct 29 '16 at 10:27

lhf · Accepted Answer · 2016-10-30T20:42:26.370

For $n$ prime, this holds iff $−1$ is not fourth power mod $n$, aka a biquadratic residue.

If $a^4\equiv−1 \bmod p$, then $a$ has order $8$ mod $p$ and so $8$ divides $p-1$, by Lagrange's theorem of group theory.

Conversely, since the units mod $p$ form a cyclic group, there is an element $a$ of order $8$ when $8$ divides $p-1$. For this $a$, we have $a^4\equiv−1 \bmod p$.

Therefore,

$−1$ is fourth power mod $p$ iff $p \equiv 1 \bmod 8$

and so

$−1$ is not fourth power mod $p$ iff $p \equiv 2, 3, 5, 7 \bmod 8$

For $n$ not prime, quartic reciprocity will help.

For what $n$ does $x^4+y^4\equiv 0\pmod n\implies x\equiv y\equiv 0\pmod n$

1 Answers1