How many incongruent solutions are there for $x^{2}\equiv49\:\left(10^{6}\right)$?

Question

How many solutions are there for $x^{2}\equiv49\:\left(10^{6}\right)$ ?

I can see that $x=\pm7$ are two solutions, and I guess that $x$ is a solution to the given congruence iff $\left(\frac{x}{7}\right)^{2}\equiv1\:\left(10^{6}\right)$. So as $\frac{x}{7}$ has to be an integer, we can write $x=7y$ and then look for number of solutions to $y^{2}\equiv1\:\left(10^{6}\right)$ (right?). How can we continue from here?

EDIT:

The answer is 8.

I think it is somehow related to the fact that $$\left(\mathbb{Z}/_{10^{6}}\mathbb{Z}\right)^{\times}\cong\left(\mathbb{Z}/_{2^{6}}\mathbb{Z}\right)^{\times}\times\left(\mathbb{Z}/_{5^{6}}\mathbb{Z}\right)^{\times} $$ and that

• $y^{2}\equiv1\:\left(2^{6}\right)$ has 4 solutions
• $y^{2}\equiv1\:\left(5^{6}\right)$ has 2 solutions

But I don't see exactly why. Is that right?

Answer 1

Your edit contains two essential observations; making explicit the isomorphism $$\left(\mathbb{Z}/{10^{6}}\mathbb{Z}\right)^{\times}\ \longrightarrow\ \left(\mathbb{Z}/{2^{6}}\mathbb{Z}\right)^{\times}\times\left(\mathbb{Z}/{5^{6}}\mathbb{Z}\right)^{\times}: x+10^6\Bbb{Z}\ \longmapsto\ (x+2^6\Bbb{Z},x+5^6\Bbb{Z}) ,\tag{1}$$ tells you that $x^2\equiv49\pmod{10^6}$ if and only if $$x^2\equiv49\pmod{2^6}\qquad\text{ and }\qquad x^2\equiv49\pmod{5^6}.$$ You already note that these congruences have $4$ and $2$ solutions, respectively. This gives you $4\times2=8$ pairs $(x_1,x_2)\in\left(\mathbb{Z}/{2^{6}}\mathbb{Z}\right)^{\times}\times\left(\mathbb{Z}/{5^{6}}\mathbb{Z}\right)^{\times}$ such that $$x_1^2\equiv49\pmod{2^6}\qquad\text{ and }\qquad x_2^2\equiv49\pmod{5^6}.$$ Because ($1$) is an isomorphism, every such pair corresponds to a unique $x\in\left(\mathbb{Z}/_{10^{6}}\mathbb{Z}\right)^{\times}$ satisfying $x^2\equiv49\pmod{10^6}$. Hence there are precisely $8$ solutions to the original congruence.

Answer 2

Let $d=\gcd(x-7,x+7)$ then $d\mid (x+7)-(x-7)=14$ so $d=2$ or $d=1$ since $$2^6\cdot 5^6\mid (x-7)(x+7)$$ So we have this possibilities:

• $x-7=5^6a$ and $x+7 = 2^6b$ where $a,b$ are relatively prime

• $x-7=2\cdot 5^6a$ and $x+7 = 2^5b$ where $a,b$ are relatively prime

• $x+7=2\cdot 5^6a$ and $x-7 = 2^5b$ where $a,b$ are relatively prime
• $x+7=5^6a$ and $x-7 = 2^6b$ where $a,b$ are relatively prime.

Now solve this systems if $x<10^6$.

---

For the first case we have a following linear diophant equation $$ 2^6b -5^6a = 14$$ where $a\leq {999993\over 5^6}$ so $a\in \{0,1,...639\}$ and $b\leq {1000007\over 2^6}$ so $b\in \{0,1,...15625\}$. Clearly $a=2c$ so we have $$32\mid 125^2c+7\implies 32\mid c-17$$ so $c= 32k+17$ and $$b= 5^6k+8301\implies 0\leq k\leq 0 $$

So $k=0$ and $a=34$ and $b=8301$ and $x=531257$.

Answer 3

If you factorise as $(x+7)(x-7)$ the two factors must contain factors $2^65^6$

Now they differ by $14$ so must both be even. $14$ contains just one factor $2$ so one of the two factors must have a factor $2^5$. They can't have a factor $5$ in common, so $5^6$ belongs to one of the factors.

That is sufficient to identify the solutions.