Obtain the eight incongruent solutions of the linear congruence

  • Thread starter Thread starter Math100
  • Start date Start date
  • Tags Tags
    Linear
AI Thread Summary
The discussion focuses on solving the linear congruence 3x + 4y ≡ 5 (mod 8). It establishes that since gcd(3, 8) = 1, the equation can be manipulated to find x in terms of y, resulting in x ≡ 7 + 4y (mod 8). The solutions for y ranging from 0 to 7 yield eight incongruent pairs: (7,0), (3,1), (7,2), (3,3), (7,4), (3,5), (7,6), and (3,7). The discussion also highlights that the even remainders do not have multiplicative inverses in this context, affecting the solution set. Ultimately, the congruence provides a structured approach to finding all solutions within the specified modulus.
Math100
Messages
813
Reaction score
229
Homework Statement
Obtain the eight incongruent solutions of the linear congruence ## 3x+4y\equiv 5\pmod {8} ##.
Relevant Equations
None.
Consider the linear congruence ## 3x+4y\equiv 5\pmod {8} ##.
Then ## 3x\equiv 5-4y\pmod {8} ##.
Note that ## gcd(3, 8)=1 ## and ## 1\mid (5-4y) ##.
Since ## 3^{-1}\equiv 3\pmod {8} ##, it follows that ## x\equiv 15-12y\pmod {8}\equiv 7+4y\pmod {8} ##.
Thus ## {(x, y)=(7+4y, y)\pmod {8}\mid 0\leq y\leq 7} ##.
Therefore, ## x\equiv 7, y\equiv 0; x\equiv 3, y\equiv 1; x\equiv 7, y\equiv 2; x\equiv 3, y\equiv 3; ##
## x\equiv 7, y\equiv 4; x\equiv 3, y\equiv 5; x\equiv 7, y\equiv 6; x\equiv 3, y\equiv 7. ##
 
Physics news on Phys.org
Math100 said:
Homework Statement:: Obtain the eight incongruent solutions of the linear congruence ## 3x+4y\equiv 5\pmod {8} ##.
Relevant Equations:: None.

Consider the linear congruence ## 3x+4y\equiv 5\pmod {8} ##.
Then ## 3x\equiv 5-4y\pmod {8} ##.
Note that ## gcd(3, 8)=1 ## and ## 1\mid (5-4y) ##.
Since ## 3^{-1}\equiv 3\pmod {8} ##, it follows that ## x\equiv 15-12y\pmod {8}\equiv 7+4y\pmod {8} ##.
Thus ## {(x, y)=(7+4y, y)\pmod {8}\mid 0\leq y\leq 7} ##.
Therefore, ## x\equiv 7, y\equiv 0; x\equiv 3, y\equiv 1; x\equiv 7, y\equiv 2; x\equiv 3, y\equiv 3; ##
## x\equiv 7, y\equiv 4; x\equiv 3, y\equiv 5; x\equiv 7, y\equiv 6; x\equiv 3, y\equiv 7. ##
That's right. The remainders modulo ##8## do not form a field because none of the even numbers has a multiplicative inverse. The odd remainders have such so that you could solve the equation.
 
And here is how the straight looks like. Of course, only the circled points do really count, so the green lines is a bit cheating.
1661294620661.png
 
Back
Top