elementary number theory - 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?

Answer

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.