Number System and Number Theory

1Divisibility, and how to test a composite

The rules for 2, 4, 5, 8 and 10 read the tail of the number; the rules for 3 and 9 read its digit sum; the rule for 11 reads the alternating digit sum. For 918082 the odd places give 9 + 8 + 8 = 25 and the even places 1 + 0 + 2 = 3, and 25 − 3 = 22 is a multiple of 11 — so the number is, and indeed 918082 = 11 × 83462.

For a composite divisor there is no single rule, and the correct move is to split it into factors that are coprime. 72 = 8 × 9 works because 8 and 9 share no factor. 12 = 2 × 6 does not: 18 passes both those tests and is not a multiple of 12.

Figure. Each prime has a digit test; a composite divisor requires every prime factor's test to pass. Checking 6 means checking 2 and 3, not inventing a separate rule.

2Counting divisors, and summing them

Write N = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}. Any divisor is built by choosing an exponent for each prime independently — anything from 0 to a_i for p_i — so the number of divisors is (a_1+1)(a_2+1)\cdots(a_k+1). The same independence gives the sum of all divisors as a product of geometric series, one per prime: \sigma(N)=\prod_i\frac{p_i^{a_i+1}-1}{p_i-1}.

Factors pair off around \sqrt{N}, so the count is odd exactly when N is a perfect square and its square root is left unpaired. An odd divisor count is therefore an instant square flag.

Figure. After prime factorisation n=\prod p_i^{e_i}, the divisor count is \prod(e_i+1) and the divisor sum multiplies each geometric series (p^{e+1}-1)/(p-1). The tree is bookkeeping for those products, not a substitute for the formulas.

How it works

1. Factorise completelyStrip out 2s first, then 3s, then 5s; stop when the quotient is prime.
2. Add one to each exponentThe extra choice is the exponent 0, which means leaving that prime out of the factor.
3. Multiply, then sumThe counts multiply for d(N). For \sigma(N), replace each count (a+1) by the geometric sum (p^{a+1}-1)/(p-1).

3Unit digits, and the cycle of four

The unit digit of a power depends on nothing but the unit digit of the base, and it repeats with a period of at most 4. Powers of 7 run 7, 9, 3, 1 and then start again; powers of 2 run 2, 4, 8, 6; powers of 4 and 9 have period 2; and 0, 1, 5 and 6 never change at all.

So reduce the exponent modulo the cycle length and read the cycle. The one thing to watch is a remainder of 0: an exponent that is an exact multiple of the cycle length lands on the last entry of the cycle, not the first.

Figure. Multiplying by 7 once more walks you one step round this loop, and after four steps you are back where you started. The exponent's remainder on division by 4 names the node — with the fourth node carrying remainder 0, which is the only place a candidate ever comes off this diagram wrong.

How it works

1. Throw the base awayKeep only its unit digit; 17, 27 and 1237 all behave exactly like 7.
2. Reduce the exponent mod the cycleFor cycle length 4, divide the exponent by 4 and keep the remainder, treating a remainder of 0 as 4.
3. Read the cycleCount that many places along the base's cycle, starting from the first power.

4HCF × LCM, and why only two numbers

For any two positive integers a and b, \mathrm{HCF}(a,b)\times\mathrm{LCM}(a,b)=a\times b. The identity is an immediate consequence of writing both numbers in primes: at each prime the HCF takes the smaller exponent and the LCM the larger, so the two exponents add to the sum of the original exponents and the primes multiply back to ab.

The same argument fails for three or more numbers. \mathrm{HCF}(a,b,c)\times\mathrm{LCM}(a,b,c) is not abc in general, because the middle exponents have nowhere to go. Always check the count of arguments before you reach for the product shortcut.

Figure. At the prime 2, the two exponents are 4 and 2. HCF keeps the shorter bar and LCM the longer; together they use each unit of exponent exactly once, which is why HCF × LCM recovers the product of the two numbers. The same min/max read at 3 and at 5 finishes the factorisations in the ledger.

How it works

1. Factor both numbersWrite each as a product of prime powers, lining the primes up in columns.
2. Min for HCF, max for LCMAt each prime, HCF keeps the smaller exponent and LCM the larger; a missing prime is exponent 0.
3. Check with the productMultiply HCF by LCM and confirm you recover ab — the check catches a mis-read exponent in one line.

5Remainders via Fermat and Euler

Fermat's Little Theorem says a^{p-1}\equiv 1\pmod{p} for a prime p that does not divide a. Euler's theorem generalises it: a^{\phi(n)}\equiv 1\pmod{n} whenever \gcd(a,n)=1, where \phi(n)=n\prod_{p\mid n}(1-1/p) counts the integers up to n that are coprime to n.

The exam move is always the same: reduce the base modulo n, collapse the exponent modulo \phi(n) (or modulo the base's cycle when that is shorter), then compute the small residue. For a power tower, peel from the base upward — reduce the base first, then the exponent modulo the cycle you just found.

Figure. Powers of 4 modulo 7 walk this three-node cycle. The tower example lands on remainder 1 for the exponent, which names the node 4 — the same residue the ledger reaches. Fermat's period 6 would also work, but the cycle you read off the powers is shorter and is what the figure shows.

How it works

1. Reduce the baseReplace a by a \bmod n before touching the exponent.
2. Find the cycle or φ(n)For a prime modulus use p-1; otherwise compute \phi(n), or read the cycle of the reduced base by direct powers.
3. Collapse the exponentReduce the exponent modulo that period, treating a remainder of 0 as a full period, then evaluate the small power.

6Trailing zeroes in n!

A trailing zero is a factor of 10, and a factor of 10 is a 2 paired with a 5. Inside n! the 2s vastly outnumber the 5s, so the number of zeroes is simply the number of 5s available — Legendre's formula \sum_{i\ge 1}\lfloor n/p^i\rfloor at p=5.

Count them in a ladder: \lfloor n/5\rfloor picks up one 5 from each multiple of 5, \lfloor n/25\rfloor picks up the second 5 that every multiple of 25 secretly carries, \lfloor n/125\rfloor the third, and so on until the term is zero. Forgetting the higher rungs is the only mistake this question ever tests.

Figure. Each trailing zero is a factor 10=2\times 5; fives are scarcer, so sum \lfloor n/5\rfloor+\lfloor n/25\rfloor+\lfloor n/125\rfloor+\cdots until the floor vanishes.