※ 引述《B90165 (abc)》之銘言：
: Find an inverse of 5 modulo 47.
: Solve the congruence 5 x ≡ 7 (mod 47)
: 因為本人離散真的很弱,所以很多都搞不懂
: 希望有大大可以講解這2題,非常感謝
1.
47 = 5 x 9 + 2
5 = 2 x 2 + 1
所以
1 = 5 - 2 x 2 = 5 - 2 x (47- 5 x 9)
= 5 x 19 - 2 x 47
故 1 = 5 x 19 - 2 x 47
inverse of 5 modulo 47 為 19
------------------------------#
2.
由上一題解知
1 = 5 x 19 - 2 x 47
兩邊同乘7
7 = 7 x (5 x 19 - 2 x 47)
7 = 5 x 133 - 14 x 47
所以 x= 133
--------------#
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.249.2.182