# Quadratic congruences in which modulus is divisible by constant term

There are two similar congruences: $$x^2-6x\equiv16\pmod{512}\\ y^2-y\equiv16\pmod{512}$$ It is easy to see that the $\gcd$ of all three parts in both of them is $16$, $x$ and $x-6$ are even and one of $y$ and $y-1$ is odd. After also noticing $x\not\equiv x-6\pmod{4}$ we have $$x \equiv 0 \pmod{8}\\ or\\ x-6 \equiv 0 \pmod{8}$$ $$y \equiv 0 \pmod{16}\\ or\\ y-1 \equiv 0 \pmod{16}$$ Making substitutions $x=8n,x=8n+6,y=16m,y=16m+1$ I obtained congruences with modulus $32$, but couldn't make it any further. I also discovered that the first congruence can be rewritten as $(x+2)(x-8) \equiv 0\pmod{512}$ while $-2$ and $8$ appear to be its solutions. However, it's still not clear to me whether there are more of them.
What am I missing? How can such congruences be solved?

• The first is true exactly when $x\equiv -2,8\pmod {256}$, since you just want $512\mid(x+2)(x-8)$ and both of those terms must be even, but only one of them can have higher powers of $2$ as factors. – Thomas Andrews Dec 27 '14 at 3:12
• @Thomas Ah, one of the terms is necessarily divisible by 256, and it's only achievable when it is equivalent to zero. Easy indeed. Thanks! – Edacious Dec 27 '14 at 3:23

The first one is easy. You need $(x-8)(x+2)$ divisible by $512$. Both $x+8$ and $x-2$ are even, but only one of them can have higher powers of $2$ as factors. Thus, $x\equiv 8\pmod {256}$ or $x\equiv -2\pmod{256}$.

The second requires more care.

First assuming $y\equiv 0\pmod{16}$ you have $y=16y_0$ and $$16y_0^2=y_0+1\pmod{32}$$

Since $16y_0^2$ is even, $y_0+1$ is even, so $y_0$ is odd. When $y_0$ odd, $16y_0^2\equiv 16\pmod{32}$, so $y_0\equiv 15\pmod {32}=$ and $y\equiv 16\cdot 15=240\pmod{512}$.

Second, assume $y=16y_0+1$. Then $$16y_0^2 \equiv 1-y_0\pmod{32}$$ So $y_0$ is odd, $1-y_0\equiv 16\pmod {32}$, or $y_0\equiv 17\pmod{32}$. So $y\equiv 16\cdot 17+1=273\pmod{512}$

So the two solutions are $y\equiv 240,273\pmod{512}$.

Note that the sum of these two values is $1\pmod{512}$, as befits the two roots of any quadratic equation of the form $x^2-x+C=0$.

Indeed, we have $(y-240)(y-273)\equiv y^2-y-16\pmod{512}$, so these are the only solutions, since only one of $y-240$ and $y-273$ can be even.