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
 
I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
Back
Top