Extended Chinese Remainder Theorem

The Extended Chinese Remainder Theorem is an algorithm that checks if

$$\exists x\in \mathbb{Z},x\equiv a_0(\mathrm{mod}{m}_0)\wedge x\equiv a_1(\mathrm{mod}{m}_1)$$

and finds such an integer $x$ if there exists for integers $a_0,a_1$ and postive integers $m_0,m_1$ in $\mathcal{O}(\log m_0+\log m_1)$ time and $\mathcal{O}(\log m_0+\log m_1)$ space.

Algorithm

Lemma

$$\exists x\in \mathbb{Z},x\equiv a_0(\mathrm{mod}{m}_0)\wedge x\equiv a_1(\mathrm{mod}{m}_1)⟺\gcd \{m_0,m_1\}\mid a_1-a_0$$

Proof

$$\begin{array}{rl}\exists x\in \mathbb{Z},x\equiv a_0(\mathrm{mod}{m}_0)\wedge x\equiv a_1(\mathrm{mod}{m}_1)& ⟺\exists p,q\in \mathbb{Z},m_{0}p+a_0=m_{1}q+a_1\\ & ⟺\exists p,q\in \mathbb{Z},m_{0}p-m_{1}q=a_1-a_0\end{array}$$

Applying Bézout’s Identity yields

$$\exists p,q\in \mathbb{Z},m_{0}p-m_{1}q=a_1-a_0⟺\gcd \{m_0,m_1\}\mid a_1-a_0$$

0. Apply the Euclidean Algorithm to find $\gcd \{m_0,m_1\}$.
1. • If $\gcd \{m_0,m_1\}\nmid a_1-a_0$, applying the lemma yields that no solution exists.
   • Otherwise, apply the Extended Euclidean Algorithm to find a pair of integers $p$ and $q$ such that $m_{0}p+a_0=m_{1}q+a_1$, then $x=m_{0}p+a_0=m_{1}q+a_1$ is an integer such that $x\equiv a_0(\mathrm{mod}{m}_0)\wedge x\equiv a_1(\mathrm{mod}{m}_1)$.

This algorithm solves the problem in $\mathcal{O}(\log m_0+\log m_1)$ time and $\mathcal{O}(\log m_0+\log m_1)$ space.

std::optional<int> excrt(const std::array<int, 2> &a, const std::array<int, 2> &m) {
	int gcd = std::gcd(m[0], m[1]);
	if ((a[1] - a[0]) % gcd != 0) {
		return std::nullopt;
	}
 
	return m[0] * (a[1] - a[0]) / gcd * exgcd(m[0], m[1]).first + a[0];
}