# Chinese Remainder theorem for 2 congruences

• fishturtle1
In summary, the conversation discusses the proof that the solution to a system of congruences of the form ##x \equiv a (\operatorname{mod} m)## and ##x \equiv b (\operatorname{mod} n)## has the form ##x = a + cn + ymn## for some ##y \in \mathbb{Z}##. The conversation also mentions a possible typo in the given equations, where ##m## and ##n## may have been swapped.
fishturtle1

## Homework Statement

Let ##a, b, m, n## be integers with ##\gcd(m,n) = 1##. Let $$c \equiv (b-a)\cdot m^{-1} (\operatorname{mod} n)$$
Prove that ##x = a + cn## is a solution to ##x \equiv a (\operatorname{mod} m)## and ##x \equiv b (\operatorname{mod} n)##, (2.24).

and that every solution to (2.24) has the form ##x = a + cn + ymn## for some ##y \epsilon \mathbb{Z}##.

## The Attempt at a Solution

Since ##\gcd(m,n) = 1## I tried following CRT..

##x \equiv a (\operatorname{mod} m)##
##x = a + mk##, for some integer ##k##.

Substituting into second congruence,
##a + mk \equiv b (\operatorname{mod} n)##
##mk \equiv b - a (\operatorname{mod} n)##
##k \equiv (b-a)\cdot m^{-1} (\operatorname{mod} n)##
##k = (b-a) \cdot m^{-1} + nl##, for some integer ##l##.
Substituting ##k## into ##x##,
##x = a + mk##
##x = a + m((b-a)\cdot m^{-1} + nl)##

But we're given ##c = (b-a)\cdot m^{-1}##
So ##x = a + mc + mnl## but they have ##nc## instead of ##mc## as the second term of ##x##Also, I tried to check that this ##x## satisfied both congruences but i have a problem:

We have ##x \equiv a + mc \equiv a + m(b-a)\cdot m^{-1} \equiv a + b - a \equiv b (\operatorname{mod} mn)##.

So this satisifes ##x = b \equiv b (\operatorname{mod} n)##
But i don't see how ##x = b \equiv a (\operatorname{mod} m)## is true unless ##a \equiv b (\operatorname{mod} m)##...

It's a typo. The solution should be x=a+cm.
Then the first equation is satisfied trivially, and c cancels neatly in the 2nd equation.

Alternatively the typo could be in the given equations, meaning m and n should be swapped.

Ok, thank you.

I like Serena

## 1. What is the Chinese Remainder theorem for 2 congruences?

The Chinese Remainder theorem for 2 congruences is a mathematical theorem that provides a solution to a system of congruences with two equations. It states that if the two equations have relatively prime moduli, then there exists a unique solution that satisfies both equations simultaneously.

## 2. How does the Chinese Remainder theorem for 2 congruences work?

The theorem works by using the Chinese remainder theorem, which states that if two integers are relatively prime, then there exists a solution to the system of congruences. The solution is found by using the extended Euclidean algorithm to calculate the coefficients of the linear combination of the two congruences.

## 3. What are the applications of the Chinese Remainder theorem for 2 congruences?

The Chinese Remainder theorem for 2 congruences has various applications in number theory, cryptography, and computer science. It is used to find solutions to systems of linear congruences, which has applications in solving simultaneous equations and finding modular inverses. It is also used in the Chinese remainder theorem algorithm for fast computation of large modular exponentiation.

## 4. Can the Chinese Remainder theorem for 2 congruences be extended to more than 2 congruences?

Yes, the Chinese Remainder theorem can be extended to any number of congruences. The theorem states that if the moduli of the congruences are pairwise relatively prime, then there exists a unique solution that satisfies all the congruences simultaneously. However, as the number of congruences increases, the complexity of the calculations also increases.

## 5. What is the relationship between the Chinese Remainder theorem and the Chinese remainder theorem for 2 congruences?

The Chinese Remainder theorem for 2 congruences is a special case of the Chinese remainder theorem. It is used specifically for finding solutions to systems of two congruences, while the general Chinese remainder theorem can be used for any number of congruences. The Chinese remainder theorem for 2 congruences is often used as a stepping stone to understanding the more general theorem.

• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
9
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
16
Views
1K
• Precalculus Mathematics Homework Help
Replies
5
Views
1K