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.
No comments:
Post a Comment