Number Theory Foundations

A quotient counts full groups; a remainder counts what is left.

For a positive divisor d, every whole number n has exactly one expression $\displaystyle n = dq + r$ with $\displaystyle 0 \le r < d$. If $\displaystyle r = 0$, d divides n. A remainder can never equal or exceed the divisor: that would make another full group.

Why the digit-sum tests work

In division by 9, 10 leaves remainder 1. So do 100, 1,000, and every power of 10. Replacing each place-value unit by 1 preserves the remainder. That means a number and its digit sum have the same remainder when divided by 9. The same reasoning works for 3. It does not give a digit-sum rule for every divisor.

Choose the test that matches the divisor

For 2, inspect the last digit. For 5, the last digit must be 0 or 5. For 10, it must be 0. For 4, inspect the last two digits, because every multiple of 100 is divisible by 4. A number divisible by 6 must be divisible by both 2 and 3. For a cycle of length d, full groups of d return to the start; the remainder tells you where you finish.

Common pitfalls

Explain it to yourself

Explain why checking the digit sum is enough for 9, but not for 4.

Count positive divisors, not how large a number looks

A prime is an integer greater than 1 with exactly two positive divisors: 1 and itself. A composite integer is greater than 1 and has additional positive divisors. The number 1 has only one positive divisor, so it is neither. The number 2 is prime and is the only even prime.

Why testing up to the square root is enough

If $\displaystyle n = a \times b$ and both a and b were greater than $\displaystyle \sqrt{n}$, their product would exceed n. A composite number therefore has a divisor at most $\displaystyle \sqrt{n}$. It is enough to test prime divisors in that range, since every composite divisor contains a prime divisor.

A rectangle is a factorization you can see

Arranging n tiles in a filled rectangle gives whole-number side lengths whose product is n. A prime permits only a 1-by-n rectangle. One nontrivial factor pair proves a number is composite. Failing a few tests proves primality only after every necessary prime up to the square root has been checked.

Common pitfalls

Explain it to yourself

Why is testing 2, 3, 5, and 7 sufficient to decide whether 97 is prime?

Break factors down until every factor is prime

Start with any nontrivial factor pair, and keep splitting composite factors. Every integer greater than 1 has one prime factorization, apart from the order of the factors. A factor tree may look different while its prime leaves agree.

A divisor makes an independent exponent choice

A divisor of 360 may use zero through three copies of 2, zero through two copies of 3, and zero or one copy of 5. Multiplying the numbers of choices counts every positive divisor exactly once. Include exponent zero, which means omitting that prime.

Squares pair every prime factor

Squaring an integer doubles all prime exponents. Conversely, an integer with only even prime exponents is a perfect square. To find the smallest multiplier that makes a square, include one copy of every prime whose exponent is odd; do not add unnecessary copies.

Common pitfalls

Explain it to yourself

Explain why a perfect square has an odd number of positive divisors.

Common means it must fit both numbers

A common divisor divides each number exactly. The greatest common divisor, or GCD, is the largest such integer. If a number is split into equal groups with no leftovers, the group size must divide the total. When the same group size must work for two totals, use common divisors.

Shared prime powers use the smaller exponent

A common divisor cannot use more copies of a prime than either number has. For each shared prime, take the smaller exponent. A prime missing from one number contributes exponent zero. Multiplying the shared powers gives the GCD.

Subtracting a multiple keeps the common divisors

If a divisor divides a and b, it also divides a−qb. Conversely, a divisor of b and a−qb divides a. This is the Euclidean algorithm: replace the larger number by the remainder, repeating until the remainder is zero. The last nonzero remainder is the GCD.

Common pitfalls

Explain it to yourself

In the cookie example, distinguish the number of boxes from the number of cookies in each box.

A common multiple contains both numbers

A multiple of n is n times an integer. A common multiple must be divisible by every given number. The least common multiple, or LCM, is the smallest positive one. It models the first positive time at which repeating schedules meet again when they start together.

Enough of every required prime

A multiple must contain at least as many copies of each prime as either original number needs. Choose the larger exponent for each prime that appears in either number. This meets every divisibility requirement without unnecessary factors.

Check both divisibility and minimality

After calculating an LCM, verify that dividing it by each original number gives an integer. A product of the numbers always works as a common multiple, but it often repeats shared prime factors unnecessarily. For two positive integers, $\displaystyle \operatorname{gcd}\, \left(a, b\right) \times \operatorname{lcm}\, \left(a, b\right) = a \times b$.

Common pitfalls

Explain it to yourself

When does $\displaystyle \operatorname{lcm}\, \left(a, b\right)$ equal $\displaystyle a \times b$? Explain using shared prime factors.

Translate before calculating

Ask what the unknown must do. Must it divide several totals? Look at common divisors. Must several periods or sizes divide the unknown? Look at common multiples. Then decide whether the question wants the greatest divisor, the least positive multiple, or some other constrained value.

The words alone do not choose the operation

“Largest” does not automatically mean GCD and “smallest” does not automatically mean LCM. Identify what divides what. A fixed number of groups might ask for items per group after you find the number of groups. A schedule problem might ask for clock time after you find elapsed minutes.

Extra conditions still matter

A GCD or LCM may produce only a candidate. Check inequalities, leftovers, excluded divisors, and units. If the first common multiple fails a condition, examine later multiples systematically. Explain why all smaller candidates fail to justify that your answer is least.

Common pitfalls

Explain it to yourself

Invent one situation where 6 divides the unknown and another where the unknown divides 6.