Number Theory Formula Cheat Sheet for Divisibility

Number theory formula cheat sheet explains primes, divisibility, modular arithmetic, and number properties, helping learners understand number patterns and solve problems in mathematics and cryptography.

Number Theory Formula Cheat Sheet

Topic	Formula	Description
Divisibility	a	b ⇔ b = ak
Prime Number	p > 1, only factors 1 and p	Basic definition
Composite Number	More than two factors	Non-prime
GCD (HCF)	gcd(a,b)	Greatest common divisor
LCM	lcm(a,b) = (a×b)/gcd(a,b)	Least common multiple
Euclidean Algorithm	gcd(a,b) = gcd(b, a mod b)	Efficient GCD
Extended Euclidean	ax + by = gcd(a,b)	Linear combination
Coprime Numbers	gcd(a,b) = 1	Relatively prime
Fundamental Theorem	n = p₁^a × p₂^b × …	Prime factorization
Modular Congruence	a ≡ b (mod n)	Same remainder
Modular Addition	(a + b) mod n	Add under mod
Modular Multiplication	(ab) mod n	Multiply under mod
Modular Inverse	a⁻¹ mod n	ax ≡ 1 (mod n)
Fermat’s Little Theorem	a^(p−1) ≡ 1 (mod p)	p prime
Euler’s Totient	φ(n)	Count of coprimes
Euler’s Theorem	a^φ(n) ≡ 1 (mod n)	Generalization
φ(p)	p − 1	For prime p
φ(pᵏ)	pᵏ − pᵏ⁻¹	Prime power
Multiplicative φ	φ(ab)=φ(a)φ(b) if coprime	Property
Chinese Remainder	Solve x ≡ a₁ mod n₁	System solution
Wilson’s Theorem	(p−1)! ≡ −1 (mod p)	Prime test
Linear Diophantine	ax + by = c	Integer solutions
Condition	c divisible by gcd(a,b)	Solution exists
Perfect Number	σ(n) = 2n	Sum of divisors
Mersenne Prime	2ᵖ − 1	Special prime
Quadratic Residue	x² ≡ a (mod p)	Square mod
Legendre Symbol	(a/p)	Residue test
Euler’s Criterion	a^((p−1)/2) ≡ ±1 (mod p)	Residue check
Modular Exponentiation	a^b mod n	Fast power
Sum of Divisors	σ(n) = Π[(p^(k+1)−1)/(p−1)]	Divisor sum
Number of Divisors	d(n) = Π(k+1)	Count factors

Download PDF

Conclusion Number theory is the subfield of mathematics that examines a whole number. It also covers such subjects as prime numbers, divisibility and modular arithmetic. There are both theoretical and practical applications of number theory. It finds wide application in computer security and cryptography. The notion of greatest common divisor and least common multiple are basic. Patterns and relationships of numbers are also studied in number theory. It assists to enhance logical thinking and problem solving. Numerous mathematical proofs rely on the concepts of number theory. It constitutes one of the most ancient areas of mathematics that have a rich historical significance. The use of encryption and coding systems is modern. Studying number theory builds up good analytical skills. It assists in learning higher mathematics as well. In sum, number theory is an intriguing topic which intertwines theory and practice. In summary, number theory is essential for understanding integers and their properties. It plays a key role in cryptography and builds strong logical skills.