# About a variant of the Chinese Remainder Theorem

• MHB
• steenis
In summary: The multiplicative inverse of q with respect to q'.That is, it is such that:$$[q]_{q'}^{-1} \cdot q \equiv 1 \pmod {q'}$$And since $q$ and $q'$ are co-prime that inverse is guaranteed to exist and to be unique.
steenis
Let $m$ and $m'$ be positive integers, and $d=gcm(m,m')$.
(i) The system:

$x \equiv b (mod \ m)$
$x \equiv b' (mod \ m')$

has a solution if and only if $b \equiv b' (mod \ d)$

(ii) two solutions of the system are congruent $mod \ l$, where $l = lcm(m,m')$.

I can prove part (i), but can anyone help me with part (ii) ?

Remember $gcd(a,b) \cdot lcm(a,b) = a \cdot b$

See, for instance: "Cuoco - Learning Modern Algebra (2013)", p.145 and p.148

Example:
$x \equiv 1 (mod \ 6)$ and $x \equiv 4 (mod \ 15)$
Then $m=6$, $m'=15$, $d=3$, $b=1$, $b'=4$, and $1 \equiv 4 (mod \ 3)$, so (i) applies:
$19 \equiv 1 (mod \ 6)$ and $19 \equiv 4 (mod \ 15)$.
$lcm(6,15)=30$ and all the solutions are: $\cdots \ -41,-11,19,49,79 \ \cdots$.

Hi, steenis.

Start with two solutions, say $x$ and $y$, to the system. We want to show that $l$ divides $x-y$. Since $x$ and $y$ solve the system of congruences, we have that $m$ and $m'$ divide $x-y$, which can be seen by writing $x-y = (x-b)-(y-b)$. Since $m$ and $m'$ both divide $x-y$, so too must their least common multiple, $l$, which can be proved by considering the prime factorizations of $m$ and $m'$.

steenis said:
Let $m$ and $m'$ be positive integers, and $d=gcm(m,m')$.
(i) The system:

$x \equiv b (mod \ m)$
$x \equiv b' (mod \ m')$

has a solution if and only if $b \equiv b' (mod \ d)$

(ii) two solutions of the system are congruent $mod \ l$, where $l = lcm(m,m')$.

I can prove part (i), but can anyone help me with part (ii) ?

Hi steenis,

Suppose $\gcd(m,m')=d$, then we can write $m=qd$ and $m'=q'd$ with $\gcd(q,q')=1$.
And suppose $b\equiv b' \pmod d$, so that $\frac{b'-b}d$ is an integer.

Then we have:
$$x = b + km = b' + k'm' \quad\Rightarrow\quad b + kqd = b' + k'q'd \quad\Rightarrow\quad kq = \frac{b'-b}d + k'q' \\ \quad\Rightarrow\quad kq \equiv \frac{b'-b}d \pmod {q'} \quad\Rightarrow\quad k \equiv [q]_{q'}^{-1} \frac{b'-b}d \pmod {q'} \quad\Rightarrow\quad k = [q]_{q'}^{-1} \frac{b'-b}d + k''q' \\ \quad\Rightarrow\quad x= b + km= b + \left([q]_{q'}^{-1} \frac{b'-b}d + k''q'\right)qd = b + [q]_{q'}^{-1}q (b'-b) + k''qq'd$$

Thus:
$$x \equiv b + [q]_{q'}^{-1}q (b'-b) \pmod{\text{lcm}(m,m')}$$

Btw, note that in the second step we have $b + kqd = b' + k'q'd \quad\Rightarrow\quad (b-b') = (k'q' - kq)d$.
Since the right hand side is divisible by $d$, so must the left hand side be divisible by $d$, proving (i).

However, what does $[q]_{q'}^{-1}$ mean?

steenis said:
However, what does $[q]_{q'}^{-1}$ mean?

The multiplicative inverse of q with respect to q'.
That is, it is such that:
$$[q]_{q'}^{-1} \cdot q \equiv 1 \pmod {q'}$$
And since $q$ and $q'$ are co-prime that inverse is guaranteed to exist and to be unique.

As an example $[2]_5^{-1} = [3]_5$ because $3\cdot 2 \equiv 1 \pmod 5$.

It's a common notation to express solutions that make use of the Chinese Remainder Theorem.
Note that the general solution of $x\equiv a_i \pmod{m_i}$ with $m_i$ pairwise coprime, is $x\equiv\sum a_i \left[\frac M{m_i}\right]_{m_i}^{-1} \frac M{m_i} \pmod M$, where $M=\prod m_i$.

Clear, thank you.
I think my texts are too introductory to come across this notation.

## 1. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that provides a solution to a system of congruences, where each equation has a different modulus. It states that if the moduli are pairwise relatively prime, there exists a unique solution to the system of congruences.

## 2. What is a variant of the Chinese Remainder Theorem?

A variant of the Chinese Remainder Theorem is a modified or alternative version of the original theorem. These variants may have different conditions or requirements, but they still provide a solution to a system of congruences with different moduli.

## 3. How is a variant of the Chinese Remainder Theorem different from the original theorem?

A variant of the Chinese Remainder Theorem may have different conditions or requirements, but the fundamental principle of finding a solution to a system of congruences with different moduli remains the same. The differences may lie in the simplicity or complexity of the solution method.

## 4. What are some applications of the Chinese Remainder Theorem and its variants?

The Chinese Remainder Theorem and its variants are widely used in cryptography, computer science, and number theory. They can be used to encrypt and decrypt messages, solve systems of linear equations, and find solutions to modular arithmetic problems.

## 5. Are there any limitations to the Chinese Remainder Theorem and its variants?

The Chinese Remainder Theorem and its variants have some limitations, such as the requirement of relatively prime moduli and the complexity of finding the solution for large numbers. Additionally, there may be cases where the solution is not unique, or there is no solution at all.

• General Math
Replies
3
Views
1K
• General Math
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• General Math
Replies
5
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• General Math
Replies
8
Views
6K
• General Math
Replies
1
Views
2K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• General Math
Replies
1
Views
1K
• General Math
Replies
4
Views
2K