Concept

Chinese remainder theorem

The fact that remainders modulo coprime numbers can be chosen independently and determine one remainder modulo their product. It lets a computation modulo a composite number be split into smaller computations modulo its factors and reassembled.

Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.

One number, two dials: 3 and 5. A grid of remainder pairs, each cell holding the smallest number that leaves those two remainders.

Two dials at once

Watch one number on two clocks with different faces. If the faces share no factor, every pair of readings occurs exactly once — so two remainders name a number, and a hard calculation can be split into two easy ones.

number · Modular arithmetic

The walk x² + 1 modulo 101, drawn as the letter ρ. Starting at 2 and squaring and adding 1 modulo 101, the walk visits 8 values once on a tail and then runs round a cycle of 9 values for ever.

A collision that finds a factor

A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.

probability · Birthday problem

Powers of 5 and 6 until the digits settle. five-adic tail 0896109004106619977392256259918212890625; six tail 9103890995893380022607743740081787109376; settled after 8: 10, 9.

A number that is its own square

Square 625 and the answer, 390625, ends in 625. Square 9376 and it ends in 9376. Keep extending them and two endless strings of digits appear, running leftward, each equal to its own square — and their product is nought, though neither is. Base ten does this because ten is two times five: a number in base ten is secretly a pair of numbers, one in base two and one in base five, and these two strings are the pair (one, nought) and (nought, one). In a prime base no such thing can happen.

discrete · Modular arithmetic

Named alongside it

The objects these essays reach for when they reach for this one.

Modular arithmetic Greatest common divisor Bijection Birthday problem Collision Counting two ways Cyclic group Factoring Hensel lemma Iteration Lattice Lifting

All concepts