#number-theory

Topics tagged "number-theory".

• Prime Number

  An integer greater than 1 divisible only by 1 and itself — the indivisible building block from which every other integer is made.

• Sieve of Eratosthenes

  An ancient algorithm that finds every prime up to N by repeatedly striking out the multiples of each prime in turn.

• Fundamental Theorem of Arithmetic

  Every integer greater than 1 is a product of primes in exactly one way, up to the order of the factors.

• Greatest Common Divisor

  The largest integer dividing two numbers, found in a handful of steps by Euclid's algorithm of repeated remainders.

• Euler's Totient Function

  φ(n) counts the integers from 1 to n that share no factor with n — the size of the group of units that powers RSA.

• Fermat's Little Theorem

  For a prime p, a^p ≡ a (mod p) for every integer a — a congruence that underlies fast primality testing.

• Ulam Spiral

  Writing the integers in a square spiral and marking the primes reveals startling diagonal alignments where order seems to leak out of randomness.

• Number Theory

  The study of the integers — primes, divisibility, and congruence — whose oldest puzzles became the foundation of modern cryptography.

• Continued Fraction

  A representation of a real number as a nested stack of fractions, yielding the best possible rational approximations.

• Diophantine Equation

  An equation whose solutions must be whole numbers — solvable in the linear case exactly when the gcd of the coefficients divides the constant.