Multiples, Powers, Pascal
Four facts that each become a row of numbers. The multiples of a until b divides one: the lcm. The powers of a mod a prime p, which land on 1 at exponent p - 1: Fermat. The same row one cell earlier: the modular inverse. And Pascal's triangle built one row from the last: combinations without factorials.
C(5, 2) is the number of ways to choose 2 of 5 things, and it sits at position 2 of row 5 in Pascal's triangle. Row 0 is just 1. Each next row is built from the row above: every cell is the sum of the two cells over it.
Check your understanding
The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.
Row 5 is built. What is C(5, 2), the value at position 2?
Answer: 10. Position 2 of row 5, counting from 0, is 10.
How it runs, step by step
C(5, 2) is the number of ways to choose 2 of 5 things, and it sits at position 2 of row 5 in Pascal's triangle. Row 0 is just 1. Each next row is built from the row above: every cell is the sum of the two cells over it.
Building Pascal's triangle row by row down to row 5 to read off C(5, 2).
Row 1: 1 1. Each inner cell is the sum of the two above it, and the ends stay 1.
Row 1 is 1, 1.
Row 2: 1 2 1. Each inner cell is the sum of the two above it, and the ends stay 1.
Row 2 is 1, 2, 1.
Row 3: 1 3 3 1. Each inner cell is the sum of the two above it, and the ends stay 1.
Row 3 is 1, 3, 3, 1.
Row 4: 1 4 6 4 1. Each inner cell is the sum of the two above it, and the ends stay 1.
Row 4 is 1, 4, 6, 4, 1.
Row 5: 1 5 10 10 5 1. Each inner cell is the sum of the two above it, and the ends stay 1. Position 2 holds C(5, 2) = 10.
Row 5 is 1, 5, 10, 10, 5, 1. Position 2 is 10.
C(5, 2) = 10. Pascal's rule C(n, k) = C(n-1, k-1) + C(n-1, k) is why each cell is the sum of the two above it, and it never multiplies big factorials, so nothing overflows.
C(5, 2) is 10.
Write it yourself
Define lcm(a, b) and return the least common multiple of a and b. It runs in your browser against this lesson's own 2 examples.
// The product divided by the greatest common divisor, or walk up the multiples of the larger until one divides by the smaller.function lcm(a, b) { return 0;}
Remember
- lcm(a, b) = a * b / gcd(a, b). Divide by the gcd before multiplying to keep the numbers small.
- Fermat: a^(p-1) = 1 mod p for prime p, so a^(p-2) is the inverse of a mod p.
- C(n, k) = C(n-1, k-1) + C(n-1, k). Build Pascal's rows and no factorial ever overflows.
Topics covered
Related
Where this is used
EmbeddedHyperperiod in real-time schedules
A cyclic executive - the fixed schedule table used in avionics under ARINC 653 and in AUTOSAR task sets - repeats on a major frame whose length is the lcm of every task period. Tasks at 5 ms, 20 ms and 50 ms line up again only after 100 ms, so the table is 100 ms long and then loops forever. This is why periods are chosen as multiples of each other: switch one task to 7 ms and the lcm, and the table, jumps to 700 ms.
CryptographyField inversion on Curve25519
Curve25519 does its arithmetic modulo the prime 2^255 - 19. Implementations keep points in projective coordinates so the ladder itself never divides, then pay for one inversion at the very end to convert back, and they compute that inversion as a^(p-2) with a fixed chain of 254 squarings and 11 multiplications rather than the extended Euclidean algorithm. The reason is timing: Euclid's loop runs a number of times that depends on the secret operand and leaks it, while the exponentiation chain is the same length for every input.
SecurityPrimality testing during key generation
Making an RSA or Diffie-Hellman key means finding a large random prime, and nobody factors a 2048-bit candidate to check one. The cheap screen is Fermat's theorem: take a random odd n, compute 2^(n-1) mod n, and if the result is not 1 then the congruence is violated and n is composite for certain, a verdict from one exponentiation instead of a search for factors. GnuPG's libgcrypt runs exactly this base-2 test before anything expensive; OpenSSL skips it and goes from trial division straight to Miller-Rabin. Nothing ships on the plain test alone, because it is fooled by Carmichael numbers such as 561, and Miller-Rabin is the same congruence plus a check on the intermediate square roots.
GraphicsBinomial blur kernels
Row n of Pascal's triangle divided by 2^n approximates a Gaussian, which is where the 1 4 6 4 1 over 16 five-tap filter comes from. OpenCV's pyrDown, the downsampling step of a Gaussian pyramid, convolves with exactly that row across and down before dropping every second pixel. Integer weights are the point: the filter runs in fixed point with shifts and adds, with no floating-point rounding drift across pyramid levels. Convolving the row with itself gives a longer row of the same family, so a stack of cheap passes converges on a true Gaussian instead of one expensive kernel.
Why it works this way
Why lcm divides before it multiplies
a * b / gcd(a, b) and a / gcd(a, b) * b are the same number in exact arithmetic, but the first builds the whole product before shrinking it. Take a = 1048576 and b = 3145728: the lcm is just 3145728, while a * b is 3298534883328, which is 3 * 2^40 and therefore has zeros in every one of its low 32 bits. In Int arithmetic the product is exactly 0, the division gives 0, and lcm quietly returns 0 with no exception anywhere. Dividing first is always safe because the gcd divides a exactly, so there is no reason to write the other form.
a^(p-2) is an inverse only when p is prime
The trick is Fermat's identity rearranged: a * a^(p-2) = a^(p-1) = 1 mod p. Both steps need p prime and a not a multiple of p, so against a composite modulus the exponent p-2 returns a number that means nothing - and it fails silently, since you get some answer either way. For a general modulus m an inverse exists exactly when gcd(a, m) = 1, and the extended Euclidean algorithm is what finds it. Problems fix the modulus at a prime like 998244353 precisely so the one-line Fermat version is available.
The powMod loop above is the teaching version
repeat(e) does e multiplications, so with p near a billion the inverse would take about a billion steps and is unusable. Real code squares instead: read e in binary, one squaring per bit and one extra multiply where the bit is set, which is about 30 squarings and at most 30 multiplies for a 30-bit exponent rather than 10^9 operations. The second half of the fix is the type - with a modulus near 2^30, r * a reaches 2^60 before the mod is applied, so the accumulator has to be a Long.
Pascal's rule dodges factorials, not growth
Building row by row keeps every intermediate value a real binomial coefficient, so the factorials never appear: 21! already passes a signed 64-bit integer, while C(21, 10) is only 352716. What the method does not dodge is the rest of the row. Asking for C(67, 2) still builds all of row 67, and its middle entry C(67, 33) is 14226520737620288370, past 2^63 - the ceiling is the largest entry in the row, not the answer you asked for. The IntArray above hits its own ceiling far sooner, at row 34, where C(34, 17) is 2333606220 and passes 2^31. Beyond the range you work modulo a prime, and then you cannot divide by k! at all, which is why the modular inverse and the triangle sit on the same page.
Read more
- Least common multipleWikipedia
- Fermat's little theoremWikipedia
- Modular inverse, both wayscp-algorithms
- Binomial coefficients modulo a primecp-algorithms
- Pascal's triangleWikipedia