- #1

Math100

- 767

- 207

- 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. ##

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. ##