How many incongruent solutions are there for $x^{2}\equiv49\:\left(10^{6}\right)$? 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?
 A: 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.
A: 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.
A: 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$.
