3
$\begingroup$

I'm studying quadratic congruences with composite moduli, something of the form:

$$x^2\equiv a\pmod n$$

where $\gcd(a;n)=1$, but something I can't manage to find is how many solutions does one of them actually have without, well, solving it directly. I know that if $n=p$ a prime the congruence has either $0$ or $2$ incongruent solutions but what can we say about the general case ? Is there a general formula or at least some applicable in specific cases (different from the one that I mentioned).

edite note: actually I know how to solve this kind of equation decomposing the modulus and using the Chinese reminder theorem so I'm only interested in determining the number of solutions without actually compute them.

$\endgroup$
1
  • 1
    $\begingroup$ Maybe you can start by decomposing $n=p_1^{b_1}...p_n^{b_n}$. Interesting question. $\endgroup$
    – Maman
    Sep 27, 2016 at 22:42

2 Answers 2

Reset to default
5
$\begingroup$

If $n$ is small enough, you could probably list all the residues of $n$ squared, modulo $n$, and see which of these is equal to $a$. In the general case, you will likely need to use the prime factorization $n = p_1^{a_1} \dots p_r^{a_r}$, and then use the Chinese Remainder Theorem along with a way of solving $x^2 \equiv a \pmod{p_i^{a_i}}$ for all $1 \leq i \leq r$.

To solve $x^2 \equiv a \pmod{p^k}$, this article goes through the procedure in detail, so I won't repeat it here.

As for how many solutions the congruence has, by the Chinese Remainder Theorem, it would be the product over the number of solutions each of $x^2 \equiv a \pmod{p_i^{a_i}}$ has.

Also relevant is the answer to this question. Hope this helps.

$\endgroup$
0
$\begingroup$

The key thing you are missing is Hensel's lemma

It will allow you to reduce the prime-power case to the prime case.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .