Browse · MATH
Printjmc
number theory senior
Problem
Notice that Find some integer with such that is the multiplicative inverse to 160 modulo 1399.
Solution
Taking the given equation modulo 1399 gives so we know that 35 is the multiplicative inverse to 40. We want to use this to find the multiplicative inverse to , so we want to try to "divide" 35 by 4.
The difficulty in dividing by 4 is that 35 is odd. We do know, though, that and this number is even! Let's go even further, though, to find a multiple of 4: Factoring 4 we get Finally we multiply by 40: This argument is inelegant. Let's write it in a more clear order: The multiplicative inverse to 160 modulo 1399 is .
The difficulty in dividing by 4 is that 35 is odd. We do know, though, that and this number is even! Let's go even further, though, to find a multiple of 4: Factoring 4 we get Finally we multiply by 40: This argument is inelegant. Let's write it in a more clear order: The multiplicative inverse to 160 modulo 1399 is .
Final answer
1058