# Find the solutions of the following system of congruences

• Math100
In summary, the given system of congruences can be simplified to get the solutions ##x\equiv 4\pmod {7}; y\equiv 3\pmod {7}##.
Math100
Homework Statement
Find the solutions of the following system of congruences:
## 5x+3y\equiv 1\pmod {7} ##
## 3x+2y\equiv 4\pmod {7} ##.
Relevant Equations
None.
Consider the following system of congruences:
## 5x+3y\equiv 1\pmod {7} ##
## 3x+2y\equiv 4\pmod {7} ##.
Then
\begin{align*}
&5x+3y\equiv 1\pmod {7}\implies 15x+9y\equiv 3\pmod {7}\\
&3x+2y\equiv 4\pmod {7}\implies 15x+10y\equiv 20\pmod {7}.\\
\end{align*}
Observe that ## [15x+10y\equiv 20\pmod {7}]-[15x+9y\equiv 3\pmod {7}] ## produces ## y\equiv 17\pmod {7} ##.
This means ## y\equiv 17\pmod {7}\implies y\equiv 3\pmod {7} ##.
Since ## 3y\equiv 9\pmod {7}\implies 3y\equiv 1-5x\pmod {7} ##,
it follows that ## 1-5x\equiv 9\equiv 2\pmod {7}\implies -5x\equiv 1\pmod {7} ##.
Thus
\begin{align*}
&-5x\equiv 1\pmod {7}\implies -15x\equiv 3\pmod {7}\implies -x\equiv 3\pmod {7}\\
&\implies x\equiv -3\pmod {7}\implies x\equiv 4\pmod {7}.\\
\end{align*}
Therefore, the solutions are ## x\equiv 4\pmod {7}; y\equiv 3\pmod {7} ##.

Correct.

I only think that you could save a few steps. From ##y \equiv 3\pmod{7}## we get ##3x\equiv 4-6\equiv 5\pmod{7}## and so ##x\equiv 5^2\equiv 4\pmod{7}.##

Math100
fresh_42 said:
Correct.

I only think that you could save a few steps. From ##y \equiv 3\pmod{7}## we get ##3x\equiv 4-6\equiv 5\pmod{7}## and so ##x\equiv 5^2\equiv 4\pmod{7}.##
This is way better.

## 1. What is a system of congruences?

A system of congruences is a set of equations that involve modular arithmetic. Each equation in the system is called a congruence, and the set of all solutions to the system is called the solution set.

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

To solve a system of congruences, you need to use the Chinese Remainder Theorem. This theorem states that if the moduli (numbers on the right side of the congruences) are pairwise coprime (meaning they have no common factors), then there exists a unique solution for the system.

## 3. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that states that if you have a system of congruences with pairwise coprime moduli, then there exists a unique solution for the system. This solution is found by using the Chinese Remainder Theorem algorithm.

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

Yes, a system of congruences can have more than one solution. This happens when the moduli are not pairwise coprime, meaning they have common factors. In this case, the system may have multiple solutions or no solutions at all.

## 5. How is a system of congruences used in real life?

Systems of congruences have many applications in real life, particularly in cryptography and computer science. They are used to encrypt and decrypt messages, generate random numbers, and solve problems involving modular arithmetic. They also have applications in fields such as engineering, physics, and economics.

Replies
6
Views
850
Replies
4
Views
1K
Replies
2
Views
1K
Replies
1
Views
1K
Replies
7
Views
2K
Replies
3
Views
846
Replies
6
Views
1K
Replies
1
Views
989
Replies
3
Views
908
Replies
3
Views
1K