1.6 Number Theory
Divisibility
Definition
For integers a,b with b≠0, b divides a denoted b|a if ∃k∈ℤ:a=k*b.
Properties
If b|a and c|d, then b*c|a*d
If b|a, then b|a+b*n for any n∈ℤ.
If b|a and b|c, then b|(a*x+c*y) for all x*y∈ℤ.
Greatest Common Divisor (GCD) and LCM
Definition
For a,b, the greatest common divisor gcd(a,b) is the largest d such that d|a and d|b. The least common multiple lcm(a,b) is the smallest positive m with a|m and b|m.
Euclidean Algorithm
Compute gcd(a,b) by repeated division: a=b*q+r, then replace (a,b)←(b,r) until remainder 0.
Relation
gcd(a,b)⋅lcm(a,b)=|a,b|
Primes and Fundamental Theorem
Prime
An integer p>1 whose only positive divisors are 1 and p.
Fundamental Theorem of Arithmetic
Every integer n>1 has a unique factorization into primes up to order:
n=(p_1)(e_1)⋯(p_k)(e_k)
Modular Arithmetic
For modulus m>0, define equivalence a≡b*mod(m) if m|(a-b). Operations respect congruence: if a≡(a^′) and b≡(b^′) then a±b≡(a^′)±(b^′), a*b≡(a^′)*(b^′)*mod(m).
Residue Classes
The set {0,1,⋯,m-1} are representatives of ℤ/m*ℤ.
Euler's Totient Function
𝜙(m) number of integers in {1,2,⋯,m} relatively prime to m. If m=∏(p)(e_i) then
𝜙(m)=m*(∏_i)(1-1/(p_i))
Congruences and Linear Equations
Solve a*x≡b*mod(m). A solution exists iff gcd(a,m)|b
; then there are gcd(a,m) solutions mod m.
Chinese Remainder Theorem
If (m_1),⋯,(m_k) are pairwise coprime, the system
x≡(a_i)*mod((m_i));i=1,⋯k
has a unique solution mod M=∏((m_i)).
Diophantine Equations
Linear: a*x+b*y=c has integer solutions iff gcd(a,b)|c, general solution from one particular.