GCD With Remainders (GCD WR)
For all integers
a
,
b
,
q
and
r
, if
a
=
qb
+
r
, then gcd(
a, b
) = gcd(
b, r
).
GCD Characterization Theorem (GCD CT)
For all integers
a
and
b
, and nonnegative integers
d
, if
d
is a common divisor of
a
and
b
, and there
exist integers
s
and
t
such that
as
+
bt
=
d
, then
d
= gcd(
a, b
).
B´
ezout's Lemma (BL)
For all integers
a
and
b
, there exist integers
s
and
t
such that
as
+
bt
=
d
, where
d
= gcd(
a, b
).
Common Divisor Divides GCD (CDD GCD)
For all integers
a
,
b
and
c
, if
c

a
and
c

b
then
c

gcd(
a, b
).
Coprimeness Characterization Theorem (CCT)
For all integers
a
and
b
, gcd(
a, b
) = 1 if and only if there exist integers
s
and
t
such that
as
+
bt
= 1.
Division by the GCD (DB GCD)
For all integers
a
and
b
, not both zero, gcd
(
a
d
,
b
d
)
= 1, where
d
= gcd(
a, b
).
Coprimeness and Divisibility (CAD)
For all integers
a
,
b
and
c
, if
c

ab
and gcd(
a, c
) = 1, then
c

b
.
Prime Factorization (PF)
Every natural number
n >
1 can be written as a product of primes.
Euclid's Theorem (ET)
The number of primes is infinite.
Euclid's Lemma (EL)
For all integers
a
and
b
and prime numbers
p
, if
p

ab
, then
p

a
or
p

b
.
Unique Factorization Theorem (UFT)
Every natural number
n >
1 can be written as a product of prime factors uniquely, apart from the
order of factors.
Divisors From Prime Factorization (DFPF)
Let
n
and
c
be positive integers, and let
n
=
p
α
1
1
p
α
2
2
· · ·
p
α
k
k
be a way to represent
n
as a product
of the distinct primes
p
1
, p
2
, . . . , p
k
, where some or all of the exponents may be zero. The integer
c
is a positive divisor of
n
if and only if
c
can be represented as a product
c
=
p
β
1
1
p
β
2
2
· · ·
p
β
k
k
,
where
0
≤
β
i
≤
α
i
for
i
= 1
,
2
, . . . , k.
GCD From Prime Factorization (GCD PF)
Let
a
and
b
be positive integers, and let
a
=
p
α
1
1
p
α
2
2
· · ·
p
α
k
k
,
and
b
=
p
β
1
1
p
β
2
2
· · ·
p
β
k
k
,
be ways to
express
a
and
b
as products of the distinct primes
p
1
, p
2
, . . . , p
k
, where some or all of the exponents
may be zero. Then gcd(
a, b
) =
p
γ
1
1
p
γ
2
2
· · ·
p
γ
k
k
where
γ
i
= min
{
α
i
, β
i
}
for
i
= 1
,
2
, . . . , k.
Linear Diophantine Equation Theorem, Part 1 (LDET 1)
For all integers
a
,
b
and
c
, with
a
and
b
both not zero, the linear Diophantine equation
ax
+
by
=
c
(in variables
x
and
y
) has an integer solution if and only if
d

c
, where
d
= gcd(
a, b
).
Linear Diophantine Equation Theorem, Part 2, (LDET 2)
Let
a
,
b
and
c
be integers with
a
and
b
both not zero, and define
d
= gcd(
a, b
). If
x
=
x
0
and
y
=
y
0
is one particular integer solution to the linear Diophantine equation
ax
+
by
=
c
, then the
set of all solutions is given by
{
(
x, y
) :
x
=
x
0
+
b
d
n, y
=
y
0
−
a
d
n, n
∈
Z
}
.
2