Number Theory Toolkit

Study Sheet

Number Theory Toolkit

Divisibility, primes, and remainders

Divisibility Rules

Tip
The rules worth memorizing

Divisible by 3 or 9 when the digit sum is; by 4 when the last two digits form a multiple of 44; by 8 when the last three do; by 11 when the alternating digit sum (units −- tens ++ hundreds …\dots) is a multiple of 1111.

In plain terms. Instead of doing long division, just add or peek at a few digits. It is a shortcut to answer "does this divide evenly?" in one glance.

Example. Is 8,5148{,}514 divisible by 99? Digit sum =8+5+1+4=18= 8+5+1+4 = 18, and 1818 is a multiple of 99, so yes.

Concept
Why the digit-sum rule works

Because 10≡1(mod9)10 \equiv 1 \pmod 9, every power of ten leaves remainder 11, so a number and its digit sum leave the same remainder mod 99 (and mod 33).

In plain terms. Each "1010" is just "one more than a nine," so tens, hundreds, and so on don't change the remainder when you divide by 99 — only the digits themselves do.

Example. For 2323: 23=2⋅10+3=2⋅9+2+323 = 2\cdot 10 + 3 = 2\cdot 9 + 2 + 3, so its remainder mod 99 is 2+3=52+3 = 5, exactly the digit sum.

Primes and Factorization

Tip
Prime factorization is the master key

Write n=p1a1⋯pkakn = p_1^{a_1}\cdots p_k^{a_k}. Then the number of divisors is (a1+1)⋯(ak+1)(a_1+1)\cdots(a_k+1), and the sum of divisors is ∏piai+1−1pi−1\prod \dfrac{p_i^{a_i+1}-1}{p_i-1}.

In plain terms. Break a number into its prime "building blocks." Once you know the blocks, counting or adding up all its factors is just plugging into a formula.

Example. 72=23⋅3272 = 2^3\cdot 3^2, so it has (3+1)(2+1)=12(3+1)(2+1) = 12 divisors, and their sum is 24−11⋅33−12=15⋅13=195\dfrac{2^4-1}{1}\cdot\dfrac{3^3-1}{2} = 15\cdot 13 = 195.

Concept
Checking primality quickly

To test whether nn is prime you only need trial divisors up to n\sqrt n: if n=abn = ab with a≤ba\le b then a≤na \le \sqrt n.

In plain terms. A factor pair always has one member no bigger than the square root, so you never need to test past n\sqrt n — that cuts the work enormously.

Example. To check 9797: 97<10\sqrt{97} < 10, so only test 2,3,5,72,3,5,7. None divide it, so 9797 is prime.

GCD, LCM, and Units Digits

Tip
The GCD–LCM identity

For positive integers, gcd⁡(a,b)⋅lcm⁡(a,b)=ab\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab.

In plain terms. The greatest common divisor and least common multiple always multiply to give the two numbers' product — so knowing one gives the other.

Example. gcd⁡(12,18)=6\gcd(12,18) = 6, so lcm⁡(12,18)=12⋅186=36\operatorname{lcm}(12,18) = \dfrac{12\cdot 18}{6} = 36.

Concept
Units digits cycle

The last digit of ana^n repeats with a period dividing 44: powers of 22 cycle 2,4,8,62,4,8,6; of 33 cycle 3,9,7,13,9,7,1.

In plain terms. Last digits go in a short repeating loop, so you just find where your exponent lands in the loop instead of computing the whole power.

Example. Last digit of 71007^{100}: the cycle for 77 has length 44, and 100≡0(mod4)100\equiv 0\pmod 4, so it matches 747^4, whose last digit is 11.