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: 538
- 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 2|n. Modulo 2*n, you can make an ordinary division by 2 to get the value modulo n.