|
|
|
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
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 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.
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
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".
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 * ...
...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.
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|.
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.
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.
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 contradictionOnly 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
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.
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
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.
Extended Euclidean Algorithm -- to find the values of x and y in the B�zout's Identity.
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.
The webmaster and author of this Math Help site is Graeme McRae.