Solutions to Congruence Modulo 50

[knowLittle]

Homework Statement

Find all solutions to the equation $35x\equiv 10mod50$

The Attempt at a Solution

gcd( 35,50)= 5
So, there is a solution to this, since 5| 10. Also, there is a theorem that guarantees the existence of exactly 5 solutions.

Now, dividing $35x\equiv 10mod50$ over 5 gives:
$7x\equiv 2mod10$
Now, what multiple of 7 gives us $\equiv 2mod10$
{ 2, 12, 22, 32, 42,...} Here, we found 42 that is a multiple of 7 and satisfies $\equiv 2mod10$
We can write $7x\equiv 42mod10$ . Now, I divided the expression by 7 and got $x\equiv 6mod10$

Now, there is another theorem that tells me this
6+(50/5)t, t=0, 1, ..., 4
I get: 6, 16, 26, 36, 46
So, the solutions are
$x\equiv 6mod50$ , $x\equiv 16 mod50$, $x\equiv 26 mod50$, $x\equiv 36mod 50$, $x\equiv 46mod 50$
These are the 5 solutions of $35x\equiv 10mod50$

I found other solutions online:
So x = 6, 16, 22, 28, 34, 40, 46 modulo 50 are the
solutions to the congruence 35x ≡ 10 mod 50.

Am I incorrect?


Thank you.

 

[kru_]

Your method is correct. You can check your own solutions to verify that they are correct.

35*6 = 210 which is congruent to 10 mod 50.
35*16 = 560 which is also congruent to 10 mod 50.
Similarly for the other solutions that you found.

You can verify that 22, 28, and 40 are not solutions.
35*22 = 770 which is 20 mod 50.
35*28 = 980, is 30 mod 50.
etc.

 

[knowLittle]

I have read somewhere that division is not defined in modular arithmetic. Can someone tell me how this affect my solution?

@kru: This is puzzling, since I found those other solutions at a .edu site.

 

[HallsofIvy]

Division is not necessarily defined in modular arithmetic because there may be "0 divisors". For example, in modulo 6, 2(3)= 6= 0 (mod 6). If we had an equation of the form 3x= 1 (mod 6) we can immediately check that 3(1)= 3, 3(2)= 6, 3(3)= 9= 3, 3(4)= 12= 0, and 3(5)= 15= 3 mod 6. There is NO x such that 3x= 1 and so we could not, for example, "divide by 3" to get "1/3" as an answer. If we are working "modulo" a prime number, that doesn't happen and we can define "division".

The way I would do "35x= 10 mod 50" is this. This is the same as saying 35x= 50n+ 10 for some integer n- a linear "diophantine equation". The first thing we can do divide through by 5 to 7x= 10n+ 2 or 7x- 10n= 2. Now 7 divides into 10 once with remainder 3: 3= 10- 7. 3 divides into 7 twice with remainder 1: 1= 7- 2(3). We can replace that "3" with 10- 7 from the first equation: 1= 7- 2(10- 7)= 3(7)- 2(10)= 1 (The "Euclidean Divison Algorithm"). Multiply through by 2 to get 6(7)- 4(10)= 2.

So one solution to 7x- 10n= 2 is x= 6, n= 4. It is possible to write out the "general solution" but since 6 itself is between 0 and 10, x= 6 satisfies 7(6)= 2 (mod 10) and so 35(6)= 210= 10 (mod 50).

 

[knowLittle]

The way I would do "35x= 10 mod 50" is this. This is the same as saying 35x= 50n+ 10 for some integer n- a linear "diophantine equation".

According to Wikipedia, Diophantine equations are written as follows:
ax + by = c
The Diphantine equation that you are really writing is this
35x-50n=10?

The first thing we can do divide through by 5 to 7x= 10n+ 2 or 7x- 10n= 2. Now 7 divides into 10 once with remainder 3: 3= 10- 7. 3 divides into 7 twice with remainder 1: 1= 7- 2(3). We can replace that "3" with 10- 7 from the first equation: 1= 7- 2(10- 7)= 3(7)- 2(10)= 1 (The "Euclidean Divison Algorithm").

I understand everything, until you change the equation 1=7 -2(10-7)= 3(7)-2(10)=1. I understand that 21-20=1, but why changing from 7- 2(10-7) to 3(7)-2(10)?
Also, I am acquainted with Euclid's GCD algorithm:
Euclid(a,b)
if b==0
return a
else return Euclid (b, a mod b)

Is there a way to use it without having to trace it?

Multiply through by 2 to get 6(7)- 4(10)= 2.
So one solution to 7x- 10n= 2 is x= 6, n= 4. It is possible to write out the "general solution" but since 6 itself is between 0 and 10, x= 6 satisfies 7(6)= 2 (mod 10) and so 35(6)= 210= 10 (mod 50).

Is this all solutions for 35x \equiv 10 mod 50? Also, is it correct that there has to be exactly 5 solutions, since the gcd of 35, 50 is 5?
Is my solution correct?