Modulo (congruence)
It calculates x such that `N \equiv x \mod P`
What is "modulo" ?
The modulo is the remainder of the Euclidean division. 17 modulo 3 is equal to 2 because the remainder of the euclidean division of 17 by 3 is equal to 2. We use this notation,
`17 \equiv 2 \mod 3`
To generalize to two given integers N and P, N modulo P is the remainder of the Euclidean division of N by P.
Modulo is used in modular arithmetic, a branch of number theory in which we focus on the remainder of the Euclidean division of a number by other numbers.
What is congruence ?
Two numbers are congruent "modulo n" if they have the same remainder of the Euclidean division by n.
Another way to state that is that their difference is a multiple of n.
a, b and n are three integers, a is congruent to b "modulo n" will be written,
a \equiv b \mod n`
In the above example, 17 is congruent to 2 modulo 3.
How to calculate "a modulo n"?
Using the above definition, to calculate a modulo n, we compute the remainder of the Euclidean division of a by n.
Example: how to calculate 126 modulo 7 ?
We know that 126 ÷ 7 = 18 remainder 0 therefore,
`126 \equiv 0 \mod 7`
Programming
Python
This python program calculates a modulo b, a and b are two integers.
The operator % is the remainder of the Euclidean division.
def modulo(a, b):
return a%b