Question 620707
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