Summary Elementary number theory

(Almost) all theorems and definitions
Elementary Number Theory

1. Divide and Conquer
Definitions and examples
Definition. The natural numbers are {1, 2, 3, 4, . . . }.
Definition. The integers are {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}.
Definition. Suppose a and d are integers. Then d divides a, denoted d|a, if and only if
there is an integer k such that a = kd.
Definition. Suppose that a, b, n are integers, with n > 0. We say that a and b are
congruent modulo n if and only if n|(a − b). We denote this relationship as a ≡ b
(mod n) and read these symbols as ”a is congruent to b modulo n”.
Theorem. Let n be an integer. If 6|n, then 3|n.
Theorem. Let k be an integer. If k ≡ 7 (mod 2), then k ≡ 3 (mod 2).

Divisibility and congruence
Theorem. Let a, b, c be integers. If a|b and a|c, then a|(b + c).
Theorem. Let a, b, c be integers. If a|b and a|c, then a|(b − c).
Theorem. Let a, b, c be integers. If a|b and a|c, then a|bc.
Theorem. Let a, b, c be integers. If a|b, then a|bc.
Theorem. Let a and n be integers with n > 0. Then a ≡ a (mod n).
Theorem. Let a, b, n be integers with n > 0. If a ≡ b (mod n), then b ≡ a (mod n).
Theorem. Let a, b, c, n be integers with n > 0. If a ≡ b (mod n) and b ≡ c (mod n),
then a ≡ c (mod n).
Theorem. Let a, b, c, d, n be integers with n > 0. If a ≡ b (mod n) and c ≡ d (mod n),
then a + c ≡ b + d (mod n).
Theorem. Let a, b, c, d, n be integers with n > 0. If a ≡ b (mod n) and c ≡ d (mod n),
then a − c ≡ b − d (mod n).
Theorem. Let a, b, c, d, n be integers with n > 0. If a ≡ b (mod n) and c ≡ d (mod n),
then ac ≡ bd (mod n).
Theorem. Let a, b, k, n be integers with n > 0 and k > 0. If a ≡ b (mod n), then ak ≡ bk
(mod n).
Theorem. A natural number that is expressed in base 10 is divisible by 3 if and only if
the sum of its digits is divisble by 3.

1

, The Division Algorithm
Axiom (The Well-Ordering Axiom for the Natural Numbers). Let S be any nonempty
set of natural numbers. Then S has a smallest element.
Theorem. For every natural number n there is a natural number k such that 7k differes
from n by less than 7.
Theorem (The Division Algoritm). Let n and m be natural numbers. Then there exists
integers q (for quotient) and r (for remainder) such that m = nq + r and 0 ≤ r ≤ n − 1.
Moreover, if q, q ′ and r, r′ are any integers that satisfy m = nq + r = nq ′ + r′ with
0 ≤ r, r′ ≤ n − 1 , then q = q ′ and r = r′ .
Theorem. Let a, b, n be integers with n > 0. Then a ≡ b (mod n) if and only if a and b
have the same remainder when divided by n. Equivalently, a ≡ b (mod n) if and only if
when a = nq1 + r1 (0 ≤ r1 ≤ n − 1) and b = nq2 + r2 (0 ≤ r2 ≤ n − 1), then r1 = r2 .

Greatest common divisors and linear Diophantine equations
Definition. A common divisor of integers a and b is an integer d such that d|a and d|b.
Definition. The greatest common divisor of two integers a and b, not both 0, is the
largest integer d such that d|a and d|b. The greatest common divisor of two integers a
and b is denoted gcd(a, b) or more briefly as just (a, b).
Definition. If gcd(a, b) = 1, then a and b are said to be relatively prime.
Theorem. Let a, n, b, r, k be integers. If a = nb + r and k|a and k|b, then k|r.
Theorem. Let a, b, n1 , r1 be integers with a and b not both 0. If a = n1 b + r1 , then
(a, b) = (b, r1 ).
Theorem. Let a and b be integers. Then a and b are relatively prime if and only if there
exists integers x and y such that ax + by = 1
Theorem. For any integers a and b not both 0, there are integers x and y such that
ax + by = (a, b).
Theorem. Let a, b, c be integers. If a|bc and (a, b) = 1, then a|c.
Theorem. Let a, b, n be integers. If a|n, b|n and (a, b) = 1, then ab|n.
Theorem. Let a, b, n be integers. If (a, n) = 1 and (b, n) = 1, then (ab, n) = 1
Theorem. Let a, b, c, n be integers with n > 0. If ac ≡ bc (mod n) and (c, n) = 1, then
a ≡ b (mod n).
Theorem. Given integers a, b, c with a and b not both 0, there exists integers x and y
that satisfy the equation ax + by = c if and only if (a, b)|c




2