Number Theory Definitions and Principles
This page has some basic definitions and proofs in number theory. Click
one of the links below to jump to a section of this page:
Modulo Arithmetic
Some properties of the Greatest Common Divisor (GCD)
Definition of "Divides": a|b if ak=b for some integer k
Definition of GCD: GCD(a,b)>=0, GCD(a,b)|a, GCD(a,b)|b, and if d|a and d|b then d|GCD(a,b).
Well-Ordering Principle: says that a set of positive integers has a smallest element
Division Algorithm: If a and m are any integers with m not zero,
then there are unique integers q and r such that a = qm+r with 0 < r < |m|.
Linear Combination: If a|b and a|c then a|(bx + cy) for any integers x and y.
Euclidean Algorithm Property: For any integers a and b, there exist integers x and y such that GCD(a,b)=ax+by.
Euclid's Principle: If a prime p|ab then p|a or p|b, a and b integers
Application of these principles: an exercise
Related pages in this website
Modulo Arithmetic
The MOD operator is defined such that
0 <= x MOD y < y and
x = q*y + (x MOD y)
In other words x MOD y is the remainder after dividing x by y.
The divides relation is defined such that x divides y <=> y = x * q for some integer q
Its properties include the following
x divides 0
x divides x
x divides y ==> x divides -y
x divides y and x divides z ==> x divides y + z
x divides y - (y MOD z)
The congruence operator == is defined such that
x == y (mod z) <=> z divides (x - y)
or equivalently
x == y (mod z) <=> x MOD z = y MOD z
z == 0 (mod z)
x == y (mod z) ==> y == x (mod z)
x == y (mod z) and y == t (mod z) ==> x == t (mod z)
x1 == x2 (mod z) and y1 == y2 (mod z) ==>
x1 + y1 == x2 + y2 and
x1 - y1 == x2 - y2 and
x1 * y2 == x2 * y2
Thus you can add, subtract, and multiply congruences.
Division
Division Theorem: If a and b are integers, b ≠ 0, a unique integer q
exists such that
a = bq+r, where
0 ≤ r < |b|
Here, r is called the least non-negative remainder or principle
remainder of a (mod b). r=0 iff b|a.
Some properties of the Greatest Common Divisor (GCD)
See the definition of GCD, below, for its defining properties. Some
other properties include:
GCD(m,n) = max {d : d divides m and d divides n}
domain(gcd) = (Z >< Z) \ {(0,0)}
GCD(m,n) = GCD(n,m)
GCD(m,0) = m
GCD(m,n) = GCD(m - n,n)
GCD(m,n) = GCD(m MOD n, n)
provided that the left hand side is defined.
These properties give rise to the Euclidean algorithm for calculating GCD
GCD(m,0) = m
GCD(0,m) = m
GCD(m,n) = GCD(m MOD n, n) if n >= m > 0
GCD(m,n) = GCD(m, n MOD m) if m >= n > 0
Definition of
"divides"
The symbol "|" means "divides" or
"is a factor of". By definition, when a and b are integers
a|b iff there exists an integer k such that ak=b. This definition leads to some unintuitive results, such as
all integers (including zero) divide zero. By the way, "iff" means "if and only
if".
Definition of GCD,
"Greatest Common Divisor"
GCD(a,b)=c means c>=0, c|a and c|b.
Furthermore, every integer d that divides a and b also divides c.
To put it another way,
here are the properties of GCD, in a nutshell -- this form is useful for
proofs, because it provides a checklist of things you must show in order
to establish GCD(a,b) as well as a set of facts you know if you know GCD(a,b):
GCD(a,b)>=0
GCD(a,b)|a
GCD(a,b)|b
if integer d exists such that d|a and d|b then d|GCD(a,b)
That last item in the
checklist is equivalent to the following statement:
for all integers d, it is true that d-|a or d-|b or d|GCD(a,b)
Cancellation Rule
m * p == m * q (mod n) and GCD(m,n) = 1 ==> p == q (mod n)
Thus m can safely be cancelled mod n so long as GCD(m,n) = 1.
Prime Numbers
An integer p is a prime number if and only if
p > 1 and {x : x divides p} = {1, p}
If p and q are both prime and p divides q, then p = q.
If p is prime and p does not divide n then GCD(p,n) = 1.
If p is prime and p divides n*m then p must divide either n or m (or both).
Any integer n can be factorized uniquely into the product of a list of primes p1 * p2 * ...
Well-Ordering Principle
...says that a set of positive integers has a smallest element.
Let S be a nonempty set of
positive integers. There exists some element a of S such that
a<=b for all elements b of S.
Division Algorithm Property
If a and m are any integers with m not zero, then there are unique
integers q and r such that a = qm+r with 0 < r < |m|.
Linear Combination Property
If a|b and a|c then a|(bx + cy) for any integers
x and y.
Proof:
Suppose a|b and a|c.
Then integers q and r exist such that b = aq and c = ar.
So, for any integers x and y, bx + cy = a(qx + ry)
and qx + ry is an integer, and hence a|(bx + cy).
An application of Linear Combination is this:
GCD(m,n)=GCD(m+kn,n), where k is any integer.
Proof:
GCD(m+kn,n)|n and GCD(m+kn,n)|m+kn, by the definition of GCD.
GCD(m+kn,n)|(m+kn)-kn, by the linear combination property
GCD(m+kn,n)|m
GCD(m+kn,n)|GCD(m,n)
similarly, GCD(m,n)|GCD(m+kn,n)
so GCD(m,n)=GCD(m+kn,n), where k is an integer.
Euclidean Algorithm Property, a.k.a. Bézout's Identity.
For any integers a and b,
there exist integers x and y such that GCD(a,b)=ax+by.
If a and b are zero, then x=y=0,
and the property is obviously true. Now we can assume a or b is nonzero.
Let S be the set of positive integers of the form sa + tb, where s and t are
integers.
Set S isn't empty so it has a smallest element by the well-ordering principle.
Let d=xa+yb be the smallest element of S.
Now I'll divide a by d to show that d|a. By the division algorithm, there are integers q and r such that a=dq+r, and
0<=r<d.
r=a-dq
r=a-(xa+yb)q
r=(1-xq)a + (-yq)b,
which has the form of elements of S, so either r=0 or r is
in S.
But r can't be in S, because r<d, the smallest element of S. So r=0.
a=dq+r, so a=dq, so d|a.
Similarly (starting with the division algorithm) we can show d|b.
Thus d is a divisor of a and b.
If c is an integer and c|a and c|b, then by the linear combination property
c|(ax+by)
d=ax+by, so c|d.
Any number that divides a and divides b also divides d, so d=GCD(a,b)
A constructive algorithm to find the integers x and y is the Extended
Euclidean Algorithm.
The converse: GCD(a,b)|ax+by is a consequence of the linear combination
property.
In particular, if x and y exist such that ax+by=1, then GCD(a,b)|1, so
GCD(a,b)=1.
Euclid's
principle:
If a prime p|ab then p|a or p|b, a and b integers. This is
sometimes called Euclid's First Theorem.
Proof using the Euclidean
Algorithm Property:
Let us assume that p|ab.
If p|a we're done.
Now we can assume p-|a.
In that case we have GCD(p,a)=1 since p is prime and hence there exist integers
x and y such that 1=px+ay (Euclidean Algorithm Property).
Multiply by b on both sides to get b=pxb+ayb.
p|pxb and p|ayb (because p|ab),
so p|(pxb+ayb), by the Linear Combination Property.
Thus p|b
Iff p and q are mutually prime, then p² and q² are mutually prime.
If:
Suppose p² and q² aren't mutually prime.
GCD(p²,q²) is not 1, so there exists a prime r such that r|GCD(p²,q²)
r|p², so r|p by Euclid's principle
similarly, r|q², so r|q
r|GCD(p,q) because r|p and r|q
so GCD(p,q) isn't 1, a contradiction
Only if:
Suppose p and q aren't mutually prime.
Let r=GCD(p,q)
So r|p, which means r|p²
Also, r|q, which means r|q²
so r|GCD(p²,q²), a contradiction
Exercise: Proof
Suppose that a, b, c are
integers such that GCD(a²,bc)=p where p is a prime. Prove that either a is
coprime to b or a is coprime to c.
GCD(a²,bc)=p
p|a², (def. of GCD)
p|a, (Euclid's Principle)
An integer x exists such that px=a, (def. of "divides")
p²x²=a²
p²|a²
p|bc, (def. of GCD)
p|b or p|c (Euclid's Principle)
if p²|bc (and we know p²|a²)
then p²|GCD(a²,bc),
which is false because p=GCD(a²,bc) and p²-|p, so p²-|bc.
if p|b and p|c then p²|bc, which is false, so either p-|b or p-|c.
GCD(a,b)|a|a² and GCD(a,b)|b|bc, (def. of GCD)
so GCD(a,b)|GCD(a²,bc), (def. of GCD(a²,bc))
so GCD(a,b)|p,
so either GCD(a,b)=1 or GCD(a,b)=p (def. of prime number)
Similarly, either GCD(a,c)=1 or GCD(a,c)=p.
If both GCD(a,b)=p and GCD(a,c)=p then p|b and p|c, but we've already
shown that p doesn't divide both b and c.
That means either GCD(a,b)=1 or GCD(a,c)=1.
Other Properties of GCD
Equality Property of
Division: If a and b are nonnegative integers, then a|b and b|a ==> a=b.
Proof:
Integers n and m exist such that an=b, and bm=a.
If a=0 then an=0=b. Likewise, if b=0 then bm=0=a,
so it's true when a or b is zero. From here on, we can assume a
and b are both positive...
Substituting an in place of b, anm=a, and since a is not zero, nm=1.
Both n and m are positive, because n=b/a>0 and m=a/b>0.
Solving n>=1, m>=1, and nm=1, we see that n=1 and m=1.
Since an=b, and n=1, we have proved that a=b.
Property 2. If a = bt + r, for integers t and r, then GCD(a,b) = GCD(b,r).
Proof:
Every common divisor of a and b also divides r, because r=a-bt is a
linear combination of a and b.
So GCD(a,b)|r, and since GCD(a,b)|b, it is true that GCD(a,b) is a
common divisor of b and r.
By the same logic, every
common divisor of b and r also divides a, because a=bt+r, a linear
combination of b and r.
GCD(b,r)|a, and since GCD(b,r)|b, it is true that GCD(b,r) is a common
divisor of a and b.
The product of any two coprimes of n is another coprime of n
That is, if GCD(a,n)=1 and GCD(b,n)=1 then GCD(ab,n)=1. Here's
the proof. This fact, and the fact that follows, are used to
show that the equivalence classes (mod n) of the coprimes of n form a
cyclic group under multiplication.
If a, b, c are coprimes of n, and b is not equal to c, then ab is not equal to ac
That is, the following five statements can't all be true:
1. GCD(a,n)=1,
2. GCD(b,n)=1,
3. GCD(c,n)=1,
4. a≠b
5. ab=ac
Here's the proof.
Internet References
Bézout's Identity,
from Mathworld, which says: For any integers a and b,
there exist integers x and y such that GCD(a,b)=ax+by. The numbers,
x and y, are called the Bézout Numbers for a and b.
Related pages in this website
Number Theory Glossary
Extended Euclidean
Algorithm -- to find the values of x and y in the Bézout's Identity.
Polynomial Remainder Theorem
Prove: For integers n>1, n4+4 is not a prime.
What's the Longest Arithmetic Progression of Perfect Squares?
Perfect Squares -- theorems
involving squares and square roots, including the fact that every square root
of a positive integer is either an integer or irrational.
Puzzles -- many of them deal with questions in
number theory
Formulas for Primitive Pythagorean
Triples and their deriviation -- a way to generate all the triples such
that a^2 + b^2 = c^2
Area of a triangle
with integer sides is not a perfect square. -- in other words there is no
Pythagorean Square Triangle.
