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: