Say I want to find the following:
(145  1)/(7  1) % 100 = 24
But since 145 is a big number in my problem, I can only get its value mod 100 i.e. 45 (= 145 % 100)
In this case,
(45  1)/(7  1) = 22 / 3
3 ^ 1 = 67 mod 100
22 * 67 = 1474 = 74 mod 100.
What am I doing wrong and how to correctly get 24? Kindly request any of the fellow solvers to clarify my doubt. Any help is greatly appreciated
A very basic doubt in Modular Arithmetic

 Posts: 348
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
A very basic doubt in Modular Arithmetic
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: A very basic doubt in Modular Arithmetic
Division modulo n must be done by multiplying with the multiplicative inverse. However, your divisor is 6 = 7  1 is not coprime with n=100, and thus the inverse does not exist. In this example, you can divide by 3 by multiplying by 3^{1} mod 100, but to divide by 2 you must keep track of the value modulo 2*n=200 because 2n. Modulo 2*n, you can make an ordinary division by 2 to get the value modulo n.