# Prove that the congruences admit a simultaneous solution

• Math100
In summary: I like your thinking though.Yes, this proof is essentially a restatement of the Chinese Remainder Theorem. However, some people may not be familiar with the theorem and may find this proof easier to understand. It also highlights the connection between the existence of a solution and the divisibility property.
Math100
Homework Statement
Prove that the congruences ## x\equiv a\pmod {n} ## and ## x\equiv b\pmod {m} ## admit a simultaneous solution if and only if ## gcd(n, m)\mid (a-b); ## if a solution exists, confirm that it is unique modulo ## lcm(n, m) ##.
Relevant Equations
None.
Proof:

Consider the congruences ## x\equiv a\pmod {n} ## and ## x\equiv b\pmod {m} ##.
Suppose ## \exists ## a solution for ## x ##.
Let ## d=gcd(n, m) ##.
This means ## \exists r, s\in\mathbb{Z} ## such that ## n=dr ## and ## m=ds ##.
Then ## x\equiv a\pmod {n}\implies x=a+nt, t\in\mathbb{Z}, x\equiv b\pmod {m}\implies x=b+mk, k\in\mathbb{Z} ##.
Now we have ## a+nt=b+mk\implies nt-mk=b-a ##.
Observe that substituting for ## m, n ## produces:
## d(sk-rt)=a-b ##.
Thus, ## d=gcd(n, m)\mid (a-b) ##.
Conversely, suppose ## gcd(n, m)\mid (a-b) ##.
Then ## d=gcd(m, n) ## and ## d\mid (a-b) ##.
This means ## dt=a-b ## for some ## t\in\mathbb{Z} ## such that ## d=nx_{0}+my_{0} ##.
Observe that ## dt=nx_{0}t+my_{0}t=a-b\implies my_{0}t+b=a-nx_{0}t ##.
Let ## x\equiv a\pmod {n}, x\equiv b\pmod {m} ## and ## y ## be any other solution.
Since ## y\equiv a\pmod {n} ## and ## y\equiv b\pmod {m} ##,
it follows that ## x\equiv y\pmod {n} ## and ## x\equiv y\pmod {m} ##.
Thus, ## \exists ## a simultaneous solution.
Therefore, the congruences ## x\equiv a\pmod {n} ## and ## x\equiv b\pmod {m} ## admit a simultaneous solution
if and only if ## gcd(n, m)\mid (a-b); ## and a solution exists, hence, ## x\equiv y\pmod {lcm(m, n)} ##.

Math100 said:
Homework Statement:: Prove that the congruences ## x\equiv a\pmod {n} ## and ## x\equiv b\pmod {m} ## admit a simultaneous solution if and only if ## gcd(n, m)\mid (a-b); ## if a solution exists, confirm that it is unique modulo ## lcm(n, m) ##.
Relevant Equations:: None.

Proof:

Consider the congruences ## x\equiv a\pmod {n} ## and ## x\equiv b\pmod {m} ##.
Suppose ## \exists ## a solution for ## x ##.
Let ## d=gcd(n, m) ##.
This means ## \exists r, s\in\mathbb{Z} ## such that ## n=dr ## and ## m=ds ##.
Then ## x\equiv a\pmod {n}\implies x=a+nt, t\in\mathbb{Z}, x\equiv b\pmod {m}\implies x=b+mk, k\in\mathbb{Z} ##.
Now we have ## a+nt=b+mk\implies nt-mk=b-a ##.
Observe that substituting for ## m, n ## produces:
## d(sk-rt)=a-b ##.
Thus, ## d=gcd(n, m)\mid (a-b) ##.
Conversely, suppose ## gcd(n, m)\mid (a-b) ##.
Then ## d=gcd(m, n) ## and ## d\mid (a-b) ##.
This means ## dt=a-b ## for some ## t\in\mathbb{Z} ## such that ## d=nx_{0}+my_{0} ##.
Observe that ## dt=nx_{0}t+my_{0}t=a-b\implies my_{0}t+b=a-nx_{0}t ##.
Let ## x\equiv a\pmod {n}, x\equiv b\pmod {m} ## and ## y ## be any other solution.
Since ## y\equiv a\pmod {n} ## and ## y\equiv b\pmod {m} ##,
it follows that ## x\equiv y\pmod {n} ## and ## x\equiv y\pmod {m} ##.
Thus, ## \exists ## a simultaneous solution.
Therefore, the congruences ## x\equiv a\pmod {n} ## and ## x\equiv b\pmod {m} ## admit a simultaneous solution
if and only if ## gcd(n, m)\mid (a-b); ## and a solution exists, hence, ## x\equiv y\pmod {lcm(m, n)} ##.
The equivalence proof is correct, a bit confusing, but correct. I am a little bit lost in the uniqueness part.

Let me suggest a hopefully slimmer version:

Consider the congruences ## x\equiv a\pmod {n} ## and ## x\equiv b\pmod {m} ##.

(a) Let ##x## be such a solution.
Then ##n\,|\,(x-a)## and ##m\,|\,(x-b).##
Moreover, ##\operatorname{gcd}(n,m)\,|\,n \wedge \operatorname{gcd}(n,m\,|\,m.##
Thus ##\operatorname{gcd}(n,m)\,|\,(x-a)\wedge \operatorname{gcd}(n,m)\,|\,(x-b).##
Finally, ##\operatorname{gcd}(n,m)\,|\,[(x-b)-(x-a)]=a-b.##

It follows your proof, only without the many parameters that are necessary to establish equations. The divisibility properties are sufficient.

(b) Conversely, suppose ## \operatorname{gcd}(n, m)\,|\, (a-b), ## i.e. ##\operatorname{gcd}(n, m)\cdot t=a-b## for some ##t\in \mathbb{Z}.##
Bézout's identity guarantees the existence of ##x_0,y_0\in \mathbb{Z}## such that ## \operatorname{gcd}(n, m)=x_0n+y_0m.## Hence
\begin{align*}
x&:=a-nx_0t=\operatorname{gcd}(n,m)\cdot t+b - nx_0t\\&\phantom{:}
=\operatorname{gcd}(n,m)\cdot t +b - \operatorname{gcd}(n,m)\cdot t +y_0m\cdot t=b +my_0t
\end{align*}
is a solution to ##x\equiv a \pmod n## and ##x\equiv b \pmod m## what had to be shown.

This uses again your ideas, only that I name Bézout's identity and save a few parameters. It is easier to read with fewer variables.

(c) Let ##x,y## be two solutions.
Then ##x-y \equiv 0=a-a \pmod n## and ##x-y \equiv 0=b-b \pmod m.## Thus ##n\,|\,(x-y)## and ##m\,|\,(x-y)##. Therefore ##\operatorname{lcm}(n,m)\,|\,(x-y)## or ##x=y+ s\cdot \operatorname{lcm}(n,m).##

Maybe this was what you meant. I just wasn't sure.

berkeman and Math100
Isn't this given by the Chinese Remainder Theorem? You only need to prove the remainder is Chinese ;).

WWGD said:
Isn't this given by the Chinese Remainder Theorem? You only need to prove the remainder is Chinese ;).
Yes, it is. But the question asked for a proof.

fresh_42 said:
Yes, it is. But the question asked for a proof.
Doesn't CRT provide conditions on the uniqueness of solutions?

WWGD said:
Doesn't CRT provide conditions on the uniqueness of solutions?
According to Wikipedia, the above exercise is basically the CRT, not the algorithmic version, but the theoretical.

## 1. What does it mean for congruences to admit a simultaneous solution?

When a set of congruences is said to admit a simultaneous solution, it means that there exists a single number that satisfies all of the congruences at the same time.

## 2. How can you prove that congruences admit a simultaneous solution?

The most common method for proving that congruences admit a simultaneous solution is by using the Chinese Remainder Theorem. This theorem states that if the moduli of the congruences are pairwise coprime, then there exists a unique solution that satisfies all of the congruences simultaneously.

## 3. What is the importance of proving that congruences admit a simultaneous solution?

Proving that congruences admit a simultaneous solution is important in number theory and cryptography. It allows us to find solutions to systems of congruences, which can be used to solve various mathematical problems and create secure encryption algorithms.

## 4. Can all congruences be solved simultaneously?

No, not all congruences can be solved simultaneously. For a set of congruences to admit a simultaneous solution, the moduli must be pairwise coprime. If the moduli are not coprime, then there may not be a solution that satisfies all of the congruences simultaneously.

## 5. Are there any other methods for proving that congruences admit a simultaneous solution?

Yes, there are other methods for proving that congruences admit a simultaneous solution, such as the Extended Euclidean Algorithm and the Chinese Remainder Theorem for Non-Coprime Moduli. However, the Chinese Remainder Theorem is the most commonly used and efficient method for proving simultaneous solutions to congruences.

• Precalculus Mathematics Homework Help
Replies
1
Views
988
• Precalculus Mathematics Homework Help
Replies
3
Views
970
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
1
Views
853
• Precalculus Mathematics Homework Help
Replies
6
Views
848