Graphics Reference
In-Depth Information
APPENDIX B
Basic Algebra
B.1
Number Theoretic Basics
Definition.
If a and b, b π 0, are integers and if a = kb for some integer k, then we
say that b
divides
a and that b is a
divisor
of a. We write b|a.
Definition.
A positive integer p greater than 1 whose only integer divisors are ±1 or
±p is called a
prime number
. Two integers a and b are said to be
relatively prime
if ±1
are the only common divisors. Given nonzero integers n
1
, n
2
,..., n
k
, the
greatest
common divisor
of these integers, denoted by gcd(n
1
,n
2
,...,n
k
) or simply (n
1
,n
2
) if k
= 2, is the largest integer that divides all the n
i
. The
least common multiple
of these
integers, denoted by lcm(n
1
,n
2
,...,n
k
), is defined to be the smallest nonnegative
integer m so that n
i
divides m for all i.
B.1.1. Theorem.
If a and b are integers that have a greatest common divisor d, then
there are integers s and t such that
sa
+=.
tb
d
Proof.
This follows from the Euclidean algorithm for integers. See, for example,
[Mill58].
Definition.
Let m be an integer. Two integers a and b are said to
congruent modulo
m
, or
mod m
, if m divides a - b, equivalently, a = b + km for some k. In that case we
shall write
(
)
a
∫
b mod m .
Definition.
Let a and m be integers. If (a,m) = 1, then a is called a
quadratic residue
modulo m if the congruence
x
2
(
)
∫
a mod m
has a solution; otherwise, a is called a
quadratic nonresidue
modulo m.
