- #1

Math100

- 767

- 207

- 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)} ##.

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)} ##.