Number theory

Start here

• ConceptDivisibility

  Divisibility is the relation between two integers $a$ and $b$ that holds when $b$ is an integer multiple of $a$. Then $a$ is a divisor of $b$, and we write $a \mid b$. The definition of divisibility gives the precise form.

• ConceptPrime number

  A prime number is a natural number greater than $1$ whose only positive divisors are $1$ and itself. The definition of a prime number gives the precise form.

• ConceptGreatest common divisor

  The greatest common divisor of two integers is the largest integer that divides both of them. We write it as $\gcd(a, b)$. The definition of the greatest common divisor gives the precise form and the convention for $\gcd(0, 0)$.

• ConceptLeast common multiple

  The least common multiple of two nonzero integers is the smallest positive integer that is a multiple of both of them. We write it as $\operatorname{lcm}(a, b)$. The definition of the least common multiple gives the precise form and the convention when one of the numbers is $0$.

• ConceptCoprime integers

  Two integers are coprime when no integer other than $1$ and $-1$ divides both of them. The definition of coprime integers states this with the greatest common divisor.

• ConceptEuclidean algorithm

  The Euclidean algorithm computes the greatest common divisor of two natural numbers $a$ and $b$. It uses two rules: $\gcd(a, 0) = a$, and $\gcd(a, b) = \gcd(b, a \bmod b)$ when $b \neq 0$. It applies the second rule until the second number is $0$. Then the first number is the result. The algorithm stops, because the second number gets smaller at each step.