Find the solutions of the system of congruences

  • Thread starter Math100
  • Start date
  • Tags
    System
In summary: But that's okay, because we can just use the inverse of the equation to solve for the x-coordinate.In summary, the system of congruences has two solutions, x=7 and y=9.
  • #1
Math100
779
220
Homework Statement
Find the solutions of the system of congruences:
## 3x+4y\equiv 5\pmod {13} ##
## 2x+5y\equiv 7\pmod {13} ##.
Relevant Equations
None.
Consider the system of congruences:
## 3x+4y\equiv 5\pmod {13} ##
## 2x+5y\equiv 7\pmod {13} ##.
Then
\begin{align*}
&3x+4y\equiv 5\pmod {13}\implies 6x+8y\equiv 10\pmod {13}\\
&2x+5y\equiv 7\pmod {13}\implies 6x+15y\equiv 21\pmod {13}.\\
\end{align*}
Observe that ## [6x+15y\equiv 21\pmod {13}]-[6x+8y\equiv 10\pmod {13}] ## produces ## 7y\equiv 11\pmod {13} ##.
This means ## 7y\equiv 11\pmod {13}\implies 14y\equiv 22\pmod {13}\implies y\equiv 9\pmod {13} ##.
Thus
\begin{align*}
&3x+4y\equiv 5\pmod {13}\implies 3x+4(9)\equiv 5\pmod {13}\\
&\implies 3x+36\equiv 5\pmod {13}\implies 3x\equiv 8\pmod {13}\\
&\implies 12x\equiv 32\pmod {13}\implies -x\equiv 6\pmod {13}\\
&\implies x\equiv -6\pmod {13}\implies x\equiv 7\pmod {13}.\\
\end{align*}
Therefore, the solutions are ## x\equiv 7\pmod {13} ## and ## y\equiv 9\pmod {13} ##.
 
Physics news on Phys.org
  • #2
Math100 said:
Homework Statement:: Find the solutions of the system of congruences:
## 3x+4y\equiv 5\pmod {13} ##
## 2x+5y\equiv 7\pmod {13} ##.
Relevant Equations:: None.

Consider the system of congruences:
## 3x+4y\equiv 5\pmod {13} ##
## 2x+5y\equiv 7\pmod {13} ##.
Then
\begin{align*}
&3x+4y\equiv 5\pmod {13}\implies 6x+8y\equiv 10\pmod {13}\\
&2x+5y\equiv 7\pmod {13}\implies 6x+15y\equiv 21\pmod {13}.\\
\end{align*}
Observe that ## [6x+15y\equiv 21\pmod {13}]-[6x+8y\equiv 10\pmod {13}] ## produces ## 7y\equiv 11\pmod {13} ##.
This means ## 7y\equiv 11\pmod {13}\implies 14y\equiv 22\pmod {13}\implies y\equiv 9\pmod {13} ##.
Thus
\begin{align*}
&3x+4y\equiv 5\pmod {13}\implies 3x+4(9)\equiv 5\pmod {13}\\
&\implies 3x+36\equiv 5\pmod {13}\implies 3x\equiv 8\pmod {13}\\
&\implies 12x\equiv 32\pmod {13}\implies -x\equiv 6\pmod {13}\\
&\implies x\equiv -6\pmod {13}\implies x\equiv 7\pmod {13}.\\
\end{align*}
Therefore, the solutions are ## x\equiv 7\pmod {13} ## and ## y\equiv 9\pmod {13} ##.
Correct. And see, just as if it was over the rationals. All numbers different from ##0## have an inverse. We can therefore solve the linear equation system as usual. This time you calculated the intersection point of two straights in the plane.

If you draw the straights, they will look a bit weird because they wrap around ##13##.
 
  • Like
Likes topsquark and Math100

FAQ: Find the solutions of the system of congruences

1. What is a system of congruences?

A system of congruences is a set of equations that involve modular arithmetic. In this system, each equation has the form "x is congruent to a (mod m)", where x is the unknown variable, a is a constant, and m is the modulus.

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 in the system are pairwise coprime (meaning they have no common factors), then there exists a unique solution for x that satisfies all the congruences.

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

Sure, let's say we have the system:
x is congruent to 2 (mod 3)
x is congruent to 4 (mod 5)
x is congruent to 3 (mod 7)
To solve this, we first check if the moduli (3, 5, and 7) are pairwise coprime. Since they are, we can use the Chinese Remainder Theorem. We can rewrite the first congruence as x = 2 + 3k, the second as x = 4 + 5j, and the third as x = 3 + 7l, where k, j, and l are integers. Now we can set these equations equal to each other and solve for x. This gives us the solution x = 23, and we can check that it satisfies all three congruences.

4. Are there any other methods for solving systems of congruences?

Yes, there are other methods such as the Extended Euclidean Algorithm and Gaussian Elimination. However, the Chinese Remainder Theorem is the most efficient and commonly used method.

5. What are some real-world applications of solving systems of congruences?

Solving systems of congruences is used in many fields such as cryptography, computer science, and engineering. For example, it is used in the RSA encryption algorithm for secure communication, in error-correcting codes for data transmission, and in scheduling algorithms for optimizing processes.

Similar threads

Replies
3
Views
1K
Replies
4
Views
1K
Replies
6
Views
905
Replies
2
Views
798
Replies
3
Views
933
Replies
7
Views
1K
Back
Top