A very basic doubt in Modular Arithmetic

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

A very basic doubt in Modular Arithmetic

Post by MuthuVeerappanR » Sat Dec 05, 2015 8:59 pm

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
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm
Location: Montréal, Canada

Re: A very basic doubt in Modular Arithmetic

Post by mpiotte » Sat Dec 05, 2015 10:14 pm

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

Post Reply