# Solve ##x\equiv 1\pmod {3},x\equiv 2\pmod {5},x\equiv 3\pmod 7 ##

• Math100
In summary, the Chinese Remainder Theorem can be used to solve simultaneous congruences, such as the set given by x ≡ 1 (mod 3), x ≡ 2 (mod 5), and x ≡ 3 (mod 7). By defining N_k and solving for x_1, x_2, and x_3, we can ultimately determine that x ≡ 52 (mod 105).
Math100
Homework Statement
Solve the following set of simultaneous congruences:
## x\equiv 1\pmod {3}, x\equiv 2\pmod {5}, x\equiv 3\pmod {7} ##.
Relevant Equations
None.
Consider the following set of simultaneous congruences:
## x\equiv 1\pmod {3}, x\equiv 2\pmod {5}, x\equiv 3\pmod {7} ##.
Applying the Chinese Remainder Theorem produces:
## n=3\cdot 5\cdot 7=105 ##.
Now we define ## N_{k}=\frac{n}{n_{k}} ## for ## k=1, 2,..., r ##.
Observe that ## N_{1}=\frac{105}{3}=35, N_{2}=\frac{105}{5}=21 ## and ## N_{3}=\frac{105}{7}=15 ##.
Then
\begin{align*}
&35x_{1}\equiv 1\pmod {3}\\
&21x_{2}\equiv 1\pmod {5}\\
&15x_{3}\equiv 1\pmod {7}.\\
\end{align*}
This means ## x_{1}=2, x_{2}=1 ## and ## x_{3}=1 ##.
Thus ## x\equiv (1\cdot 35\cdot 2+2\cdot 21\cdot 1+3\cdot 15\cdot 1)\pmod {105}\equiv 157\pmod {105}\equiv 52\pmod {105} ##.
Therefore, ## x\equiv 52\pmod {105} ##.

fresh_42
Math100 said:
Homework Statement:: Solve the following set of simultaneous congruences:
## x\equiv 1\pmod {3}, x\equiv 2\pmod {5}, x\equiv 3\pmod {7} ##.
Relevant Equations:: None.

Consider the following set of simultaneous congruences:
## x\equiv 1\pmod {3}, x\equiv 2\pmod {5}, x\equiv 3\pmod {7} ##.
Applying the Chinese Remainder Theorem produces:
## n=3\cdot 5\cdot 7=105 ##.
Now we define ## N_{k}=\frac{n}{n_{k}} ## for ## k=1, 2,..., r ##.
Observe that ## N_{1}=\frac{105}{3}=35, N_{2}=\frac{105}{5}=21 ## and ## N_{3}=\frac{105}{7}=15 ##.
Then
\begin{align*}
&35x_{1}\equiv 1\pmod {3}\\
&21x_{2}\equiv 1\pmod {5}\\
&15x_{3}\equiv 1\pmod {7}.\\
\end{align*}
This means ## x_{1}=2, x_{2}=1 ## and ## x_{3}=1 ##.
Thus ## x\equiv (1\cdot 35\cdot 2+2\cdot 21\cdot 1+3\cdot 15\cdot 1)\pmod {105}\equiv 157\pmod {105}\equiv 52\pmod {105} ##.
Therefore, ## x\equiv 52\pmod {105} ##.
Perfect!

Math100

## 1. How do you solve a system of congruences?

To solve a system of congruences, you must first determine if the system is solvable. This means that the moduli (numbers on the right side of the congruences) must be relatively prime. In this case, 3, 5, and 7 are all relatively prime. Once you have determined that the system is solvable, you can use the Chinese Remainder Theorem to find a unique solution for x.

## 2. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that states that if the moduli in a system of congruences are relatively prime, then there exists a unique solution for x that satisfies all of the congruences. This solution can be found by using a specific algorithm, known as the Chinese Remainder Theorem algorithm.

## 3. Can you provide an example of solving a system of congruences?

Sure, using the system given in the question, we can solve for x using the Chinese Remainder Theorem algorithm. First, we find the inverse of 5 modulo 3, which is 2. Then, we find the inverse of 3 modulo 5, which is 2. Finally, we find the inverse of 5 modulo 7, which is 3. Plugging these values into the algorithm, we get x = 1*5*2 + 2*3*2 + 3*2*3 = 103. Therefore, the solution for x is 103.

## 4. Is there a faster way to solve a system of congruences?

Yes, there are other methods for solving systems of congruences, such as the Gauss-Jordan method or the Chinese Remainder Theorem extended algorithm. These methods can be faster and more efficient for larger systems of congruences.

## 5. Can a system of congruences have more than one solution?

No, if the moduli in a system of congruences are relatively prime, there will always be a unique solution for x. However, if the moduli are not relatively prime, there may be multiple solutions or no solutions at all.

Replies
3
Views
2K
Replies
4
Views
1K
Replies
6
Views
1K
Replies
1
Views
1K
Replies
7
Views
2K
Replies
7
Views
1K
Replies
2
Views
1K
Replies
1
Views
1K
Replies
19
Views
1K
Replies
3
Views
1K