Thread: Congruence Equation

I am having a little trouble with this homework question


Find all incongruent solutions modulo 35 of the congruence
25x = 380 (mod 35)


I know there will be five solotions because that is the gcd

I divided the Equation by 5 which now gives you
5x = 76 (mod7)

35 = 1 (25) + 10
25 = 2 (10) + 5
10 = 2 (5) + 0

5= 1 (25) + -2 (10)
= -2 (35) + 3 (35)


After this I am not sure how to get the solutions

Please help

Originally Posted by math_cali

I am having a little trouble with this homework question


Find all incongruent solutions modulo 35 of the congruence
25x = 380 (mod 35)

which divides 380.
Hence there are 5 incongruent solutions (algebraists say a solution in each equivalence class).

You can solve this with a techinque but because the numbers are small we can try to "guess" what the solution is. First simplify the 380, the remainder it leaves it 30.
Thus,
.
We can see that is surly a solution.
By a theorem all other solutions are,

Thus,

Which are,

Why do we guess x = 4?

Originally Posted by math_cali

Why do we guess x = 4?

Because it works.
Are you asking me is there a techinque to get the number, yes there is.
One way is the Euclidean algorithm.
But why do that if the numbers are small.

Think of it this way. When you reduce a fraction by finding the common divisiors do you do it using a techinque (there is one) of do you just trial and error. You use trial and error and for the most of the time it is way faster.