Modular Arithmetic Fundamentals
Modular arithmetic groups integers by their remainder after division by a positive modulus m. Congruent numbers differ by a multiple of m, so calculations can retain only one representative from each residue class. This controls enormous intermediate growth in counting and periodicity problems. Addition, subtraction and multiplication respect congruence; division is a separate operation requiring a modular inverse.
Prerequisites: Divisibility; C++ remainder and integer overflow.
Build the idea
1. Define congruence and normalization
a≡b (mod m) means m divides a−b. The canonical representative is in 0..m−1. For signed C++ input use r=a%m and, if r<0, add m. For −7 modulo 5 this gives 3, while the raw C++ remainder is −2. Modulus zero is invalid; m=1 has just one residue, zero.
2. Reduce before arithmetic
Normalize a and b to A,B. Then (a+b) mod m=(A+B) mod m, similarly for subtraction and products. For m≤10^9, A+B fits long long and A·B<10^18, also representable. This bound is intentional; using a larger modulus near the type limit would require overflow-safe multiplication, not merely putting %m after a product.
3. Repair negative subtraction
A−B may be negative, so normalize the remainder again. For −7 and 8 modulo 5, representatives are 3 and 3: sum is 1, difference 0, product 4. Reducing after each operation keeps values bounded, but only if the operation itself can be evaluated without overflow.
4. Do not divide residues as ordinary integers
Modulo 5, 3/2 is not integer truncation 1: the inverse of 2 is 3, so modular division gives 3·3≡4. Modulo 6, 2 has no inverse because gcd(2,6)≠1. Cancelling a common factor can change the modulus or lose solutions; it requires a separate argument. The program deliberately prints no modular quotient until the inverse lesson establishes its conditions.
5. Extend safely when bounds grow
For full-width modular products, repeated doubling with overflow-safe addition or a proven wider arithmetic implementation is needed. A safe normalized addition can branch on a≥m−b instead of forming a+b when m is large. The teaching program uses an explicit small-modulus contract, making ordinary long-long multiplication correct and easy to inspect. Do not copy its product to unrestricted 64-bit moduli.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
// Key idea: 5. Extend safely when bounds grow For full-width modular products, repeated doubling with
// overflow-safe addition or a proven wider arithmetic implementation is needed.
#include<iostream>
using ll=long long;
ll normalize(ll value,ll mod){
value%=mod;
if(value<0){
value+=mod;
}
return value;
}
int main(){
ll a,b,m;
std::cin>>a>>b>>m;
ll A=normalize(a,m),B=normalize(b,m);
std::cout<<A<<' '<<B<<'\n';
std::cout<<(A+B)%m<<' '<<normalize(A-B,m)<<' '<<(A*B)%m<<'\n';
}
Complexity analysis
O(1) time and O(1) space for bounded machine-integer arithmetic. m≤10^9 guarantees normalized products below 10^18. If multiplication is instead implemented by repeated doubling, its operation count becomes logarithmic in a multiplier; do not hide that change.
Example input and output
Read a b m, |a|,|b|≤10^18 and 1≤m≤10^9. Print normalized operands, then modular sum, difference and product.
Input
-7 8 5
Output
3 3 1 0 4
Both operands are congruent to 3. Their sum is 6≡1 and product 9≡4 modulo 5.
Practical applications
Use for cyclic positions, hash-like fingerprints, combinatorial counts and keeping recurrences bounded modulo a specified integer. Remainder normalization is a prerequisite for inverse and CRT code. Exact integer answers cannot be recovered from one small residue without additional information.
Check your understanding
Can you safely compute (a*b)%m if a*b overflows first?
Put it into practice
Normalize values −m−1, −m, −1, 0 and m+1.
Show a hint
The result must always lie in 0..m−1.