SOLUTION: Solve: 73x is congruent to(the three line equal symbol) 115 (mod 971). I know you can change this to (73x-115)/971, but I'm not sure how to solve the rest of this.

Algebra ->  Probability-and-statistics -> SOLUTION: Solve: 73x is congruent to(the three line equal symbol) 115 (mod 971). I know you can change this to (73x-115)/971, but I'm not sure how to solve the rest of this.      Log On


   

Question 620707: Solve: 73x is congruent to(the three line equal symbol) 115 (mod 971).
I know you can change this to (73x-115)/971, but I'm not sure how to solve the rest of this.
Answer by jim_thompson5910(35256) About Me  (Show Source):
You can put this solution on YOUR website!
73x = 1 (mod 971)

971 | (73x - 1)

971y = 73x - 1

-73x + 971y = -1

73x - 971y = 1

971 = 13*73 + 22 ----> 22 = 971 -13*73

73 = 3*22 + 7 ----> 7 = 73 - 3*22

22 = 3*7 + 1 ----> 1 = 22 - 3*7



1 = 22 - 3*7

1 = 22 - 3*(73 - 3*22)

1 = 22 - 3*73 + 9*22

1 = 971 -13*73 - 3*73 + 9*(971 - 13*73)

1 = 971 - 13*73 - 3*73 + 9*971 - 117*73

1 = 10*971 - 13*73 - 3*73 - 117*73

1 = 10*971 - 133*73


Since 1 = 10*971 - 133*73, this means that for 73x = 1 (mod 971), the solution is x = -133 = 838 (mod 971)

So

73x = 1 (mod 971)

73*838 = 1 (mod 971)

Now multiply both sides by 115

73*838 = 1 (mod 971)

115*73*838 = 115*1 (mod 971)

73*(115*838) = 115*1 (mod 971)

73*(115*838) = 115 (mod 971)

73*96370 = 115 (mod 971)

73*241 = 115 (mod 971)

So the solution for x in 73x = 115 (mod 971) is x = 241