
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": ab if ak=b for some integer k
Definition of GCD: GCD(a,b)>=0, GCD(a,b)a, GCD(a,b)b, and if da and db then dGCD(a,b).
WellOrdering 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 ab and ac 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 pab then pa or pb, 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 nonnegative remainder or principle remainder of a (mod b). r=0 iff ba.
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 ab 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, ca and cb. 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 da and db then dGCD(a,b)That last item in the checklist is equivalent to the following statement:
for all integers d, it is true that da or db or dGCD(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 ab and ac then a(bx + cy) for any integers x and y.
Proof:
Suppose ab and ac.
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 wellordering principle.
Let d=xa+yb be the smallest element of S.
Now I'll divide a by d to show that da. By the division algorithm, there are integers q and r such that a=dq+r, and 0<=r<d.
r=adq
r=a(xa+yb)q
r=(1xq)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 da.
Similarly (starting with the division algorithm) we can show db.
Thus d is a divisor of a and b.
If c is an integer and ca and cb, then by the linear combination property c(ax+by)
d=ax+by, so cd.
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 pab then pa or pb, a and b integers. This is sometimes called Euclid's First Theorem.
Proof using the Euclidean Algorithm Property:
Let us assume that pab.
If pa we're done.
Now we can assume pa.
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.
ppxb and payb (because pab),
so p(pxb+ayb), by the Linear Combination Property.
Thus pb
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 rGCD(p²,q²)
rp², so rp by Euclid's principle
similarly, rq², so rq
rGCD(p,q) because rp and rq
so GCD(p,q) isn't 1, a contradictionOnly if:
Suppose p and q aren't mutually prime.
Let r=GCD(p,q)
So rp, which means rp²
Also, rq, which means rq²
so rGCD(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
pa², (def. of GCD)
pa, (Euclid's Principle)
An integer x exists such that px=a, (def. of "divides")
p²x²=a²
p²a²
pbc, (def. of GCD)
pb or pc (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 pb and pc then p²bc, which is false, so either pb or pc.
GCD(a,b)aa² and GCD(a,b)bbc, (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 pb and pc, 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 ab and ba ==> 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=abt 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, n^{4}+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.