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?

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$.
