Question 6689: Solve the equation:
233x + 177 = 496 (mod 792)
Answer by khwang(438)   (Show Source):
You can put this solution on YOUR website! Solve
233 x = 219 (mod 792)
Since 792 and 233 are relative prime(in fact 233 is prime)
USe Euclidan algorithm to find the inverse of 233 in mod 792
792 = 233 * 3 + 93,
233 = 93*2 + 47,
93 = 47*2 - 1
Hence, -1 = 93 - 47*2
= 93 - (233 -93*2)*2
= 233*(-2) + 93*5
= 233*(-2) + (792 -233*3)*5
= 233*(-17) + 792*5
Or 233*17 + 792*(-5) = 1
Apply mod 792 on both sides, we have 233*17 = 1 mod 792.
This means 17 is the inverse of 233 mod 792.
Multiply 17 on both sides of 233 x = 219 (mod 792) , we get
x = 17* 219 mod 792 = 555 mod 792.
Use Excel, check MOD(233*555,792) = 219 OK
The answer x = 555 mod 792.
Kenny
|
|
|
