Theorem (Chinese Remainder Theorem). Let $m_1, m_2, …, m_n\in \mathbb{Z}^+$ be pairwise relatively prime. The system $$x \equiv a_k \pmod {m_k}$$ has a unique solution modulo $M = m_1m_2…m_n.$
Group of Inversable Residue Number
Definition. $\mathbb{Z}_n^* = \{m\in\mathbb{Z}_n| m\perp n\}$
Proposition. $\mathbb{Z}_n^*$ is a group under multiplication.
Proof.
Closure. If $m’m \equiv 1 \pmod n$, then $m’m - kn = 1$, so $m’, m \in \mathbb{Z} _n ^*$. And if $m_1, m_2 \perp n$, then $m_1 m_2 \perp n$, so $m_1 m_2 \in \mathbb{Z} _n ^ *$
Inversability.
By Fermat’ little theorem, we know that for any $m$ such that $m\perp n$, $m\cdot m ^{\phi(n)-1} \equiv 1 \pmod n$. On the other hand, there exists $m’,n’$ such that $m’m + n’n = 1$, so $m’m \equiv 1 \pmod n$. Those two ways both give the existence of inversion.
Uniqueness
If $m_1m \equiv 1 \pmod n$, $m_2 m\equiv 1 \pmod n$, then $m_1 - m_2 \equiv 0 \mod n$.
Corollary. If $a \perp n$ then $ax \equiv b \pmod n$ has a unique solution $x \equiv a^{-1}b$.
Proof of Chinese Remainder Theorem.
Chinese Remainder Theorem is equivalent to $\mathbb{Z}_M \cong \mathbb{Z} _{m_1} \bigoplus \mathbb{Z} _{m_2} … \bigoplus \mathbb{Z} _{m_k}$.
We define a map $x\ mod\ M \rightarrow Res(x) = (x \ mod\ m_1, x\ mod\ m_2, …, x\ mod \ m_k),$ which is a homomorphism between two groups. We need to prove this map is bijective. And it’s sufficient to prove this has an inversion
$\mathbb{Z} _{m_1} \bigoplus \mathbb{Z} _{m_2} … \bigoplus \mathbb{Z} _{m_k}$ is actually a linear space, whose basis is $\{(1,0,…,0), (0, 1, 0,…,0), … (0,…,0,1)\}$. We want to find the preimage of every element of the basis.
Assume we want to find the preimage of $(0, …,0,1,0,…,0)$, where $1$ is at $i^{th}$ position. This equivalent to solve:
$$
\begin{equation}
\begin{cases}
x \equiv 0 \pmod{m_1}\cr
…\cr
x\equiv 1 \pmod{m_i}\cr
…\cr
x\equiv 0 \pmod {m_k}\cr
\end{cases}
\end{equation}
$$
This is equivalent to solve $$\frac{M}{m_i}y \equiv 1 \pmod{m_i} $$ where $x \equiv \frac{M}{m_i}y \pmod M$ is the solution to original system. We already know $y$ exists and is unique because $\frac{M}{m_i} \perp m_i$.
Assume the the preimage of the basis is $\{x_1 \ mod\ M, …, x_k\ mod\ M\}$. Then given $(a_1, …, a_k)$, the preimage is $x \equiv \sum _{i=1} ^k a_i x_i \pmod M$, which is well-defined.
Square Roots Under Modulo.
Assume $a \perp n$, we want to solve $x^2 \equiv a \pmod n$.
Assume $n = p_1 ^{n_1} p_2^{n_2}…p_k ^{n_k}$. By Chinese remainder theorem. This equation is equivalent to the following system: $$ \begin{equation} \begin{cases} x^2 \equiv a \pmod {p_1^{n_1}}\cr …\cr x^2 \equiv a \pmod {p_k ^{n_k}} \end{cases} \end{equation} $$
So we need only to worry about $x^2 \equiv a \pmod {p^n}$, where $a\perp p$.
Case 1: p is odd.
Assume $x^2 \equiv y^2 \equiv a \pmod {p^n} $. Then $p^n \mid (x-y)(x+y)$. We want to show $p^n$ only divides one of $(x-y)$ and $(x+y)$.
If $p^n$ doesn’t divide any of them or divides them both, then $p$ must divides them both. Then $p$ divides their sum and difference $2x$ and $2y$, which means $p$ divides $x$ and $y$. So $p \mid x^2 \equiv a$, which is contradictory with the assumption $p\perp a$.
So $p^n | x-y$ or $p^n | x+y$, which means once we have a solution $x$, $-x$ must be another solution.
Case 2: p = 2.
By checking one by one, we know that
$x^2 \equiv a \pmod 2$ have 1 solution when $a\equiv 1 \pmod 2$: $x \equiv 1 \pmod 2$;
$x^2 \equiv b \pmod 4$ have 2 solutions when $a \equiv 1 \pmod 4$: $x\equiv \pm 1 \pmod 4$.
$x^2 \equiv a \pmod 8$ have 4 solutions when $a \equiv 1 \pmod 8$: $x\equiv 1,3,5, 7\pmod 8$.
When $n>3$, if $x^2 \equiv y^2 \pmod{2^n}$, then $2^n \mid (x-y)(x+y)$. Not like the case $p$ is odd, we want to show $2^{n-1}$ divides only one of $(x+y)(x-y)$, because they are both even. If 4 divides both, then 4 divides $2x$, but $x$ must be odd since $a$ is odd, which is contradictory. So one of them has only one 2 in its factors, and the other must has at least $(n-1)$ 2s in its factors. This proves that $x\equiv y \pmod {2^{n-1}}$ or $x\equiv -y\pmod {2^{n-1}}$.
Then if $x = x_0$ is a solution, then there three other solutions: $x \equiv - x_0, x \equiv x_0 + 2^{n-1}, x\equiv - x_0 + 2^{n-1} \pmod {2^n}$.
If $\gcd(a, n) \not = 1$. Assume $a = p^r A$, where $A\perp p$.
If $r = n$, we need to solve $x^2 \equiv 0 \pmod {p^n}$. So if $n = 2m - 1$ or $2m$, the solution is $x\equiv 0 \pmod {p^m}$.
If $r\not = n$, assume $x = p^m X$ and $X\perp p$, so $r$ must equal to $2m$. And we only need to solve $X^2\equiv A \pmod{p^{n-m}}$, where $A\perp p$.
(https://www.numbertheory.org/php/squareroot.html)