# Obtain the eight incongruent solutions of the linear congruence

• Math100
In summary: Also, the line that goes through the points (3,5) and (-1,7) is not interesting, as it is just a multiple of the line that goes through (3,5) and (7,3).In summary, the linear congruence ##3x+4y\equiv 5\pmod{8}## has eight incongruent solutions given by ##x\equiv7, y\equiv0; x\equiv3, y\equiv1; x\equiv7, y\equiv2; x\equiv3, y\equiv3; x\equiv7, y\equiv4; x\equiv3, y\equiv5; x\equiv7, y\equiv
Math100
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. ##

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.

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

Math100

## What is a linear congruence?

A linear congruence is a type of mathematical equation that involves a variable, a modulus, and a remainder. It is written in the form of ax ≡ b (mod m), where a is the coefficient of the variable, b is the remainder, and m is the modulus.

## Why is it important to obtain the eight incongruent solutions of a linear congruence?

Obtaining the eight incongruent solutions of a linear congruence allows us to fully understand the behavior of the equation and determine all possible values for the variable. It also helps in solving problems related to number theory and modular arithmetic.

## What are the eight incongruent solutions of a linear congruence?

The eight incongruent solutions of a linear congruence are obtained by adding or subtracting the modulus from the original solution. For example, if x ≡ 3 (mod 5) is a solution, then the other seven solutions are x ≡ 8 (mod 5), x ≡ 13 (mod 5), x ≡ 18 (mod 5), x ≡ 23 (mod 5), x ≡ 28 (mod 5), x ≡ 33 (mod 5), and x ≡ 38 (mod 5).

## How can we solve a linear congruence to obtain the eight incongruent solutions?

To solve a linear congruence, we can use the extended Euclidean algorithm or the Chinese remainder theorem. These methods involve finding the greatest common divisor between the coefficient and the modulus, and then using modular arithmetic to obtain the solutions.

## What are some real-life applications of obtaining the eight incongruent solutions of a linear congruence?

The concept of linear congruences and their solutions are used in various fields such as cryptography, coding theory, and computer science. For example, in cryptography, linear congruences are used to generate pseudorandom numbers, which are essential for secure communication and data encryption.

• Precalculus Mathematics Homework Help
Replies
1
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
959
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
2K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
1
Views
1K
• Precalculus Mathematics Homework Help
Replies
6
Views
848
• Precalculus Mathematics Homework Help
Replies
1
Views
984
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
904