Question

Teach me, please
Find all solutions to the congruence 55x = 35 (mod 75)

Answer 1

@ganeshie8

Answer 2

gcd(75,55) = 5

divide 5 through out

Answer 3

11x = 7 (mod 15)

Answer 4

yes, my bad

Answer 5

and why are we allowed to divide like that ?

Answer 6

you might be knowing that already, so lets move on and find the x in mod 15

Answer 7

Because 75,35 and 55 all are multiple of 5, so reduce to the lowest modulo, right?

Answer 8

yes

11x = 7 (mod 15)

Notice that x = 2 gives :

11*2 = 7 (mod 15)

22 = 7 (mod 15)

15 = 0 (mod 15)

which is true, so `x = 2(mod 15)` is a solution

Answer 9

but you want to express the solution in mod 75 right ?

Answer 10

yes,

Answer 11

but how to get 2 there? just try all remainder in Z_15?

Answer 12

thats one way when the numbers are small

Answer 13

the general method is to use euclidean algorithm

Answer 14

heard of it before ?

Answer 15

2years ago, once I saw it. Not sure I can remember or not, remind me, please

Answer 16

11x = 7 (mod 15)

is equivalent to

11x = 15y + 7

for some y, right ?

Answer 17

yes

Answer 18

which is same as

11x - 15y = 7

Answer 19

Notice that our goal here is to find the solutions in `integer values of x and y`

Answer 20

so this is a linear diophantine equation

Answer 21

the method is as follows :

express gcd(11, 15) =1 as linear combination of 11 and 15 and multiply both sides by 7

Answer 22

we can express gcd(a,b) as linear combination of a,b :

ax + by = gcd(a,b)

u knew this right ?

Answer 23

yes

Answer 24

good, then its easy for you :

we digress from our goal a bit and solve 11x+15y=1 first :

15 = 11*1 + 4
11 = 4*2 + 3
4 = 3*1 + 1
3 = 1*3 + 0

so the gcd(11, 15) is 1

Answer 25

3(15)-4(11)

Answer 26

Now go in reverse :

1 = 4 - 3(1)
= 4 - (11 - 4*2)
= 15-11*1 - (11 - (15-11*1)*2)
= 15 - 11 - 11 + 2(15-11)
= 15(3) + 11(-4)

Answer 27

1 = 15(3) + 11(-4)

multiply both sides by 7, you get :

7 = 15(21) + 11(-28)

y = 21, x = -28

Answer 28

11x = 7 (mod 15)

solution is

x = -28 (mod 15)

Answer 29

let me know if something is not clear

Answer 30

I got it so far.

Answer 31

we're done,
the solution is x = -28(mod 15)
which is same as x= 2(mod 15)

Answer 32

you can express it in mod 75
you would get 75/15 = 5 incongruent solutions in mod 75

Answer 33

x = 2 (mod 15)

is same as

x = 2 + 15t

for some t, right ?

Answer 34

plugin t = 0,1,2,3,4

Answer 35

yes

Answer 36

bascially you want all the x values that are less than 75 when you're in mod75

Answer 37

and check which values give us 55x =35 (mod 75) right?

Answer 38

No, we're done.

all of those 5 values satisfy above ^^

Answer 39

x = 2 + 15t


t = 0 : x = 2
t = 1 : x = 17
t = 2 : x = 32
t = 3 : x = 47
t = 4 : x = 62

so the incongruent solutions to 55x =35 (mod 75) are : {2, 17, 32, 47, 62}

Answer 40

Ok, If I plug t =1, then x =17 so that 55(17) = 935 and 935 = 12*(75) +35
so that 935 = 35 (mod 75)

Answer 41

Got it:))))))))).Thanks a lot

Answer 42

np :)