document.write (document.title)

 Math Help > Number Theory > Definitions in Number Theory

Number Theory Definitions and Principles

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²

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

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

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.

The webmaster and author of this Math Help site is Graeme McRae.