Properties of Integers: Practice Problems and Methods

Prime factorization, divisors and multiples

Example: $72 = 2^3 \cdot 3^2$ has $4 \times 3 = 12$ divisors with sum $15 \times 13 = 195$. The GCD uses the common primes with the smaller exponents; the LCM uses all primes with the larger exponents. For two numbers, $ab = \gcd(a, b) \times \operatorname{lcm}(a, b)$.

The Euclidean algorithm and linear Diophantine equations

If $a = bq + r$, then $\gcd(a, b) = \gcd(b, r)$. Repeating this until the remainder is 0 is the Euclidean algorithm.

For $ax + by = c$ with $a$, $b$ coprime, find one solution $(x_0,\ y_0)$ and subtract to get $a(x - x_0) = -b(y - y_0)$. Since $a$ and $b$ are coprime, $x - x_0$ is a multiple of $b$:

Remainders and base-n numbers

Every integer has the form $3k$, $3k + 1$ or $3k + 2$. This classification proves facts such as "$n^2$ leaves remainder 0 or 1 when divided by 3". Congruences $a \equiv b \pmod{m}$ make calculations like the remainder of $2^{100}$ divided by 7 easy.