Number Theory Basics for Algorithms
Number-theory tools reduce large arithmetic problems to invariants: Euclid preserves common divisors, modular arithmetic preserves congruence, and exponentiation by squaring follows the exponent's binary digits.
Euclid's invariant
A number divides both a and b exactly when it divides b and a mod b, so gcd(a,b)=gcd(b,a mod b). Each remainder is smaller than the previous divisor, guaranteeing termination at gcd(x,0)=|x|.
Normalize signs and define gcd(0,0) according to the API; many libraries return zero. Extended Euclid also tracks coefficients x and y with ax+by=gcd(a,b), enabling modular inverses when the gcd is one.
- Remainders preserve common divisors
- Second operand strictly decreases
- Extended Euclid finds Bézout coefficients
LCM and overflow
For nonzero integers, |ab|=gcd(a,b)·lcm(a,b). Compute lcm as |a/gcd(a,b)·b| so division happens before multiplication and reduces overflow risk. If either input is zero, the conventional LCM is zero.
A wider integer type or checked multiplication may still be necessary. Mathematical correctness does not prevent machine overflow, and silently wrapped values corrupt later modular computations.
- Divide before multiplying
- Zero makes LCM zero
- Use checked or wide arithmetic
Euclid, LCM, and binary modular power
import math
a, b = 84, 30
gcd = math.gcd(a, b)
lcm = a // gcd * b
print(f"gcd={gcd}, lcm={lcm}, 3^13 mod 7={pow(3, 13, 7)}")#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
long long pw(long long a,int n,int m)
{
long long r=1;
for(;n;n/=2,a=a*a%m)if(n%2)r=r*a%m;
return r;
}
int main()
{
long long a=84,b=30,g=gcd(a,b);
cout<<"gcd="<<g<<", lcm="<<a/g*b<<", 3^13 mod 7="<<pw(3,13,7);
}class Main
{
static long gcd(long a,long b)
{
while(b!=0)
{
long r=a%b;
a=b;
b=r;
}
return Math.abs(a);
}
static long pw(long a,int n,long m)
{
long r=1;
for(;n>0;n/=2,a=a*a%m)if(n%2==1)r=r*a%m;
return r;
}
public static void main(String[]z)
{
long a=84,b=30,g=gcd(a,b);
System.out.print("gcd="+g+", lcm="+(a/g*b)+", 3^13 mod 7="+pw(3,13,7));
}
}84, 30; 3^13 mod 7gcd=6, lcm=420, 3^13 mod 7=3Run the example step by step
Modular arithmetic
Congruent integers have the same remainder class, allowing addition and multiplication before reduction. Subtraction should be normalized because language remainder operators may return negative values. Ordinary division is invalid modulo m unless the divisor has a multiplicative inverse.
An inverse of a modulo m exists exactly when gcd(a,m)=1. For prime moduli, Fermat's theorem offers a^(m−2) mod m; Extended Euclid works for any coprime modulus.
- Reduce after addition and multiplication
- Normalize subtraction
- Division requires an inverse
Exponentiation by squaring
Write the exponent in binary. Repeatedly square the base; when the current bit is one, multiply it into the result. Each iteration halves the exponent, so only O(log n) multiplications are required instead of O(n).
Reducing after every multiplication gives modular exponentiation without constructing the enormous exact power. The same method works for any associative operation, including matrix multiplication and function composition.
- Odd bit contributes the current power
- Square while halving exponent
- Associativity enables generalization
Choosing the right tool
Use Euclid for divisibility structure, modular arithmetic when answers are requested modulo m, and fast power when an exponent is large. These tools often combine: modular inverse, combinatorics, primality testing, and matrix recurrences build on them.
Test negative inputs, zeros, modulus one, exponent zero, and overflow boundaries. The common convention a^0=1 means the modular result is 1 mod m, which is zero when m=1.
- Handle zero explicitly
- Modulus must be positive
- Test machine-integer boundaries
Safe contracts for integer algorithms
Specify domains before implementation: whether GCD returns a nonnegative value, whether modulus must be positive, and whether negative exponents are supported through inverses. In modular multiplication, a wider intermediate type may still overflow for very large machine integers; use a big-integer type or an overflow-safe multiplication method when constraints exceed the safe product range. Reduce the base before repeated squaring and normalize every remainder into [0,m).
Tests should include gcd(0,b), gcd of negative inputs, coprime values, equal values, exponent zero, modulus one, and products near the numeric limit. For modular inverse, explicitly reject gcd(a,m)≠1 rather than returning a meaningless coefficient. These boundary contracts turn short mathematical identities into reliable program components and prevent a correct proof over unbounded integers from being misapplied to overflowing machine arithmetic.
When several operations are composed, preserve the invariant at each boundary: take absolute values where promised, reduce modular operands, and use the computed GCD before attempting an LCM or inverse. Documenting these preconditions makes the routines safely reusable inside combinatorics, hashing, and graph algorithms. For exponentiation with exponent zero, return the multiplicative identity before entering the loop, then reduce it by the modulus. Test that convention directly.
- State sign and modulus conventions
- Mathematical products can overflow machines
- Reject nonexistent modular inverses