Chapters

Number theory and counting

Number theory is the mathematics of whole numbers: how they divide, how they build from primes, and how many ways a set of them can be arranged. It is the branch that answers "what is the smallest number both of these divide into?" and "how many different four-digit PINs are there?" This chapter first builds each idea from the ground up, then shows exactly how to compute it on the Castiel calculator.

If these ideas are new to you, read the concept sections in order — each one leans on the one before. If you already know the theory and just want the functions, jump to Computing this in Castiel.

Factors and multiples

Two words underpin everything that follows.

A factor (or divisor) of a whole number is a number that divides it exactly, leaving no remainder. The factors of 12 are 1, 2, 3, 4, 6, 12.
A multiple of a number is what you get by multiplying it by a whole number. The multiples of 4 are 4, 8, 12, 16, 20, ....

Factors and multiples are two views of the same relationship: because 4 divides 12, we say 4 is a factor of 12 and 12 is a multiple of 4. Almost every idea in this chapter is a question about factors or multiples in disguise.

Greatest common divisor and least common multiple

Take two numbers. They usually share some factors and some multiples, and two of those shared values have special names.

The greatest common divisor (GCD) — also called the highest common factor (HCF) — is the largest number that divides both. For 12 and 18, the common factors are 1, 2, 3, 6, so the GCD is 6. The GCD is what you use to reduce a fraction to lowest terms: 12/18 divided top and bottom by 6 becomes 2/3.

The least common multiple (LCM) is the smallest positive number that both divide into. The multiples of 12 are 12, 24, 36, 48, ... and of 18 are 18, 36, 54, ...; the first they share is 36, so the LCM is 36. The LCM is what you use to add fractions with different denominators — it is the smallest common denominator.

The two are linked by a tidy rule: for any two positive numbers, GCD × LCM = the product of the numbers. For 12 and 18, 6 × 36 = 216 = 12 × 18. Knowing one gives you the other.

Division with a remainder

Before calculators, dividing 17 by 5 did not give 3.4; it gave "3, remainder 2." That is division with remainder, and it is still the right tool whenever you care about whole groups and what is left over.

Splitting 17 into groups of 5 gives a quotient of 3 (three full groups) and a remainder of 2 (two left over): 17 = 5 × 3 + 2. The remainder is always smaller than the number you divided by, and it is 0 exactly when the division is clean — which is the same as saying the divisor is a factor.

The remainder on its own answers a surprising number of everyday questions: whether a number is even (remainder on division by 2), what day of the week falls 100 days from now (remainder on division by 7), or which hour a clock shows after many hours pass (remainder on division by 12). This "wrap-around" arithmetic is called modular arithmetic, and the remainder is the modulus.

Prime numbers and prime factorization

A prime number is a whole number greater than 1 whose only factors are 1 and itself: 2, 3, 5, 7, 11, 13, .... A number with more factors than that (like 12, which also has 2, 3, 4, 6) is composite.

Primes matter because they are the building blocks of every other number. The fundamental theorem of arithmetic says that every whole number above 1 can be written as a product of primes in exactly one way (apart from the order). Breaking a number down this way is called prime factorization:

12 = 2 × 2 × 3, usually written 2² × 3
360 = 2³ × 3² × 5

The prime factorization is the DNA of a number. Once you have it for two numbers, the GCD and LCM fall straight out: the GCD multiplies the primes they share (taking the lower power of each), the LCM multiplies every prime that appears in either (taking the higher power).

Factorials

Suppose you have 4 different books and want to know how many ways they can sit in a row on a shelf. The first slot has 4 choices, the second has 3 left, then 2, then 1: that is 4 × 3 × 2 × 1 = 24. This "multiply every whole number down to 1" operation is the factorial, written with an exclamation mark: 4! = 24.

In general n! counts the number of ways to arrange n distinct items in order. Factorials grow explosively — 10! is already over three million — which is why the calculator does the work. Two conventions are worth knowing: 1! = 1, and 0! = 1 (there is exactly one way to arrange nothing). Factorial is only defined for whole numbers 0 and above.

A close relative is the double factorial, which multiplies every other number down from n: 7!! = 7 × 5 × 3 × 1 = 105 and 8!! = 8 × 6 × 4 × 2 = 384. It appears in some probability and calculus formulas.

Permutations and combinations

Factorials arrange a whole set. Often you instead choose a few items from a larger group — and here one question splits into two, depending on whether order matters.

Permutations — order matters. How many ways can you award gold, silver, and bronze among 8 runners? Swapping who gets gold and who gets silver is a different outcome, so order counts. A choice of r items from n where the order matters is a permutation, written nPr. Here it is 8P3 = 8 × 7 × 6 = 336.

Combinations — order does not matter. How many ways can you pick a committee of 3 from those same 8 people? A committee is just a group; shuffling the same three names is the same committee. A choice of r from n where order does not matter is a combination, written nCr. Here it is 8C3 = 56.

The difference is the whole point. Because each committee of 3 could have been chosen in 3! = 6 different orders, combinations are always the permutation count divided by r!: 8C3 = 8P3 / 3! = 336 / 6 = 56. The plain-English test: if rearranging the chosen items makes a new outcome, use nPr; if it makes the same outcome, use nCr. Combinations also power the binomial coefficients used throughout probability distributions.

Computing this in Castiel

The School calculator, used for the number-theory examples

Every example below uses the School calculator, reached from the Calculate tile. Factorial has its own key; the rest you type by name into the entry line, which the calculator accepts as typed text.

The x! key. The keypad has a dedicated x! key in the scientific block. Type a whole number, press x!, and press EXE — 5 then x! gives 120. It takes the factorial of the operand in front of it.

Typing the other functions. The counting and divisibility functions do not have their own keys; type their names followed by the arguments in brackets, separated by commas — for example gcd(12, 18) or nCr(8, 3). Function names are lowercase; a few also accept a short calculator-style uppercase alias (shown in the table below). Press EXE to evaluate.

Whole numbers only. These functions work on integers. gcd, lcm, mod, nPr, nCr, factorial, and the rest expect whole-number arguments; feeding a fraction or a value out of range (a negative factorial, or choosing more items than you have) reports a domain error rather than a misleading number.

Function reference

Type each function by name, lowercase, with its arguments in brackets. The arguments column gives how many values each one takes.

Function	What it computes	Keypad / typed form	Arguments
Factorial	`n!`, the ways to arrange `n` items	`x!` key, or type `factorial(n)`	1
Double factorial	product of every other number down from `n`	type `doublefactorial(n)`	1
Permutations	`nPr`, ordered choices of `r` from `n`	type `nPr(n, r)` (also `P(n, r)`)	2
Combinations	`nCr`, unordered choices of `r` from `n`	type `nCr(n, r)` (also `C(n, r)`)	2
Greatest common divisor	largest number dividing both	type `gcd(n, m)` (also `HCF(n, m)`)	2
Least common multiple	smallest number both divide into	type `lcm(n, m)`	2
Modulus (remainder)	remainder of `n` divided by `m`	type `mod(n, m)` (also `Rmdr(n, m)`)	2
Quotient and remainder	both the whole quotient and the remainder together	type `quotrem(n, m)`	2
Prime factorization	the prime factors of `n` and their powers	type `primefactor(n)`	1
Modular power	`n` to the power `p`, then its remainder mod `m`	type `mod_exp(n, p, m)`	3

A few notes on ranges and behaviour:

nPr and nCr need whole numbers with r no larger than n; asking to choose more than you have is a domain error.
factorial accepts whole numbers from 0 upward; factorial(0) is 1.
primefactor needs a whole number of at least 2.
mod uses floored remainder semantics by default, which means the result carries the sign of the divisor m and always lands in the natural range for wrap-around arithmetic (for example mod(n, 12) is always from 0 to 11).
quotrem returns both pieces of a division at once — the whole-number quotient and the remainder — which is handy when you need the groups and the leftovers.

Worked examples in Castiel

Example 1 — GCD and LCM of two numbers. You are simplifying the fraction 12/18 and later need a common denominator. Find both the greatest common divisor and the least common multiple of 12 and 18.

Type gcd(12, 18) and press EXE. The result is 6 — the largest number dividing both, so 12/18 reduces to 2/3.
Type lcm(12, 18) and press EXE. The result is 36 — the smallest number both divide into, so 36 is the common denominator to use when adding twelfths and eighteenths.
As a check, 6 × 36 = 216, which equals 12 × 18. The GCD times the LCM always equals the product of the two numbers.

Both results commit to the working tape, so you can scroll back and see the two steps side by side.

Example 2 — a combinations count (nCr). A class has 8 students and you must pick a committee of 3. Order does not matter — a committee is just a group — so this is a combination.

Type nCr(8, 3) and press EXE. The result is 56: there are 56 different committees.
Compare with the ordered count. Type nPr(8, 3) and press EXE; the result is 336. That counts each committee once for every way to order its three members.
The two are linked by 3!: type factorial(3) (or press 3 then x!) to get 6, and note that 336 / 6 = 56. Dividing out the 3! = 6 orderings of each committee turns the permutation count back into the combination count.

The lesson is the one from the concept section: decide first whether rearranging the chosen items makes a new outcome. If it does, count with nPr; if it does not, count with nCr.