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?

  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Dec 27 '14 at 3:12
  • $\begingroup$ @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! $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.