Given an integer greater than 1, if it’s only positive factors are 1 and itself, then it is called a prime number. If it has a positive factor different from 1 or itself, then it is called a composite number. 1 is neither prime nor composite.
Prime factors If a positive integer a has a factor b and b is a prime number, we call b a prime factor of a. For example, 2 and 3 are the prime factors of 12. 4 and 6 are also factors of 12 but they are not prime.
Prime factorization Writing a number as the product of all its prime factors is called forming the prime factorization of the number. For instance, the prime factorization of 12 is 12 = 2 × 2 × 3.
Euclid’s Lemma For any two positive integers a, b and a prime number p, if p | ab, then either p | a or p | b.
Euclid’s Lemma can be used to prove:
Fundamental Theorem of Arithmetic Every integer > 1 can be factorized into primes in exactly one way.
This means that for every integer n > 1, it can be uniquely expressed as a product of primes
Knowing the prime factorization of a number tells us a lot about the number. For instance, for any divisor d of n, Euclid’s Lemma tells us that every prime factor of d must also be a prime factor of n, and so d must be of the form
Since each bᵢ lies between 0 and aᵢ (inclusive), there are aᵢ + 1 possible choices for b. By the Fundamental Theorem of Arithmetic, different choices of bᵢ s correspond to different divisors, and each divisor arises from some choice of bᵢ s. Hence n has (a₁ + 1)(a₂ + 1)…(aₙ + 1) different divisors.
Example: 180 = 2² ∙ 3² ∙ 5¹ should have (2 + 1)(2 + 1)(1 + 1) = 18 different divisors. Indeed, listing them out:
n is a perfect square precisely when all the aᵢ s are even. For example, 180 isn’t a perfect square since the power of 5 in its prime factorization is 1. However, 900 = 2² 3² 5² = (2¹ 3¹ 5¹)² = 30² is a perfect square.
Common divisors and greatest common divisor Let n₁, n₂, …, nₖ (k ≥ 2) be n positive integers. If an integer d divides each one of them, i.e. d | n₁, d | n₂, … , d | nₖ, then we call d a common divisor (or equivalently a common factor) of n₁, n₂, …, nₖ. If d is the largest one among all the common divisors, we call it the greatest common divisor and write gcd(n₁, n₂, …, nₖ) = d, or just (n₁, n₂, …, nₖ) = d to denote this. For instance, (18, 30, 66) = 6, since the common factors of 18, 30 and 66 are 1, 2, 3, 6.
Suppose n, m can be expressed as
(Note that these are not necessarily prime factorizations, the aᵢ s and bᵢ s may be 0.) Then
where min(aᵢ, bᵢ) is the smaller of aᵢ and bᵢ. That’s because min(aᵢ, bᵢ) is the largest power of pᵢ that divides both the 
term in m and the 
term in n.
Coprimality Let m, n be integers. If (m, n) = 1, i.e. m and n have no positive divisors in common besides 1, then we say that m and n are coprime.
Common multiples and least common multiple Let n₁, n₂, …, nₖ (k ≥ 2) be n positive integers. If an integer m is a multiple for all of them, i.e. n₁ | m, n₂ | m, …, nₖ | m, then we call m a common multiple of n₁, n₂, …, nₖ. If m is the smallest among all the common multiples, we call m the least common multiple and write lcm(n₁, n₂, …, nₖ) = m, or sometimes [n₁, n₂, …, nₖ] = m to denote this.
Again, if m and n can be expressed as
Then
where max(aᵢ, bᵢ) is the larger of aᵢ and bᵢ. This is because max(aᵢ, bᵢ) is the smallest power of pᵢ that is a multiple of both the term in m and the term in n.
Relationship between greatest common divisor and least common multiple For any two positive integers n, m, we have (n, m) [n, m] = nm. This is because for each prime pᵢ, the pᵢ term on the LHS is 
and the pᵢ term on the RHS is 
. The powers on both sides match up: 
