## A very basic doubt in Modular Arithmetic

Primes, divisors, arithmetic, number properties, ...
MuthuVeerappanR
Posts: 495
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

### A very basic doubt in Modular Arithmetic

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

It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
mpiotte
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm

### 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.