1.2 Properties of Integers
10
CHAPTER 1. PRELIMINARIES
1.2
Properties of Integers
1.2.1
The Well Ordering Principle and the Division Algorithm
We now focus on a special set, the integers, denoted Z, as this set plays an
important role in abstract algebra. We begin with an important result we will
use often, the Well Ordering Principle. We will state it as an axiom, as it cannot
be proven using the usual properties of arithmetic.
Axiom 23 (Well Ordering Principle) Every nonempty set of positive integers contains a smallest element.
Example 24 S = f1; 3; 5; 7; 9g is a set of positive integers. Its smallest element
is 1.
Can we say the same about sets of positive real numbers?
Next, we look at the concept of divisibility, an important concept in number
theory.
De¡nition 25 A nonzero integer t is a divisor of an integer s and we write
t j s (read " t divides s") if there exists an integer k such that s = kt. In this
case, we also say that s is a multiple of t. When t is not a divisor of s, we
write t - s.
De¡nition 26 A prime is a positive integer greater than 1 whose only positive
divisors are 1 and itself.
Example 27 The divisors of 8 are
1,
2,
Example 28 The divisors of 7 are
1 and
4 and
8.
7. So, 7 is prime.
Example 29 What are the divisors of 0?
A fundamental property of the integers is the division algorithm. Its proof
involves the Well Ordering Principle. We now state and prove this result which
we will use often.
Theorem 30 (Division Algorithm) Let a and b be integers with b > 0.
Then, there exists unique integers q and r with the property that
a = bq + r
(1.1)
where 0 r < b
Proof. First we prove existence, then uniqueness.
Existence. With a and b as given, consider the set S = fa
Either 0 2 S or 0 2
= S.
bk j k is an integer and a
bk
0g.
1.2. PROPERTIES OF INTEGERS
11
Case 1 0 2 S, then there exists an integer k, call it q, such that a qb = 0
a
or a = qb. hence, we have existence with q = and r = 0.
b
Case 2 0 2
= S. We want to use the Well Ordering Principle. For this, we
have to show S is a nonempty set of positive integers. Since a, b and
k are integers, a bk is also an integer. Since a bk 0 and 0 2
= S,
we know that a bk > 0. We need to show S 6= ?. If a > 0 then
a 0 b = a > 0 2 S. If a < 0, then a b (2a) = a (1 2b) > 0 2 S.
By the Well Ordering Principle, S has a smallest member. Call q
the value of k for which a bk is the smallest member of S and
r = a bq. Then, r 0 and a = bq + r. We still need to prove r < b.
We do a proof by contradiction. Suppose r b. Then a b (q + 1) =
a bq b = r b 0. However, a b (q + 1) < a bq and a bq is
the smallest member of S, so we can¡¯t have a b (q + 1) 0. Thus
r < b.
Uniqueness. We assume there are at least two integers satisfying the condition and we show they are equal. Suppose that there exist integers q and
q 0 and r and r0 such that a = bq + r and a = bq 0 + r0 with 0
r < b
and 0 r0 < b. Without loss of generality, we may assume r r0 . Then,
bq + r = bq0 + r0 or b (q 0 q) = r0 r. so b j r0 r but 0 r0 r < r0 < b.
So, we must have r0 r = 0 which also implies q 0 q = 0.
Remark 31 This is the division you have been doing since you were little. r is
the remainder. If r = 0, then b j a.
Example 32 For a = 20 and b = 3, the algorithm gives 20 = 3 6 + 2.
1.2.2
Greatest Common Divisor, Relatively Prime Integers
De¡nition 33 (Greatest Common Divisor) Let m and n be two nonzero
integers. The greatest common divisor of m and n, denoted gcd (m; n), is
de¡ned to be the largest of all common divisors of m and n.
De¡nition 34 (Relatively Prime) Two nonzero integers m and n are said
to be relatively prime if gcd (m; n) = 1.
There are di¡èerent techniques to ¡nd gcd (a; b). We illustrate one known as
the Euclidean algorithm. We begin with some remarks. Suppose we are given
integers a and b, assume a
b. Then, by the division algorithm, there exists
unique integers q1 and r1 , 0 r1 < b such that a = bq1 +r1 . Any integer dividing
a and b will also divide b and r1 (see problems) hence gcd (a; b) = gcd (b; r1 ).
We repeat the process with b and r1 . There exists unique integers q2 and r2 ,
0 r2 < r1 such that b = r1 q2 + r2 . As before, gcd (b; r1 ) = gcd (r1 ; r2 ). We
12
CHAPTER 1. PRELIMINARIES
repeat the process with r1 and r2 to obtain unique integers q3 and r3 , 0 r3 < r2
such that r1 = r2 q3 + r3 . As before gcd (r1 ; r2 ) = gcd (r2 ; r3 ). Continuing this
way, we obtain a sequence of remainders r1 > r2 > r3 ::: where each ri 0. By
the well ordering principle, this process has to stop and some ri must eventually
be 0. We have
gcd (a; b) = gcd (b; r1 ) = gcd (r1 ; r2 ) = ::: = gcd (ri ; 0) = ri
See the problems for the last equality. Thus, gcd (a; b) is the last nonzero remainder arising from our repeated division. We illustrate this with an example.
Example 35 Let¡¯s ¡nd gcd (100; 64).
100
=
64 1 + 36
64
=
36 1 + 28
36
=
28 1 + 8
28
=
8 3+4
8
=
4 2+0
Thus gcd (100; 64) = 4.
Remark 36 If a number is written as a product of prime factors, then ¡nding
the greatest common divisor is simply a matter of gathering the common prime
factors which are common to both. More speci¡cally, if a = ph1 1 ph2 2 :::phnn and
b = pk11 pk22 :::pknn where pi are primes, with the understanding that some of the
ki or hi might be 0 (if the corresponding prime is not present) and if we de¡ne
si = min (hi ; ki ) for each i = 1::n, then
gcd (a; b) = ps11 ps22 :::psnn
Example 37 Find gcd 23 32 5 74 ; 2 52 7
gcd 23 32 5 74 ; 2 52 7
=
2 5 7
=
70
Theorem 38 For any nonzero integers a and b, there exists integers s and t
such that
gcd (a; b) = as + bt
Moreover, gcd (a; b) is the smallest positive integer of the form as + bt.
Proof. There are di¡è erent ways to prove the existence part. We outline them
here.
Method 1: Here, we only show that gcd (a; b) = as + bt. We use the Euclidean
algorithm developed above. So, this is a constructive proof. It will show
1.2. PROPERTIES OF INTEGERS
13
us how to ¡nd s and t. Let us assume that the Euclidean algorithm gave
us the following:
a
= bq1 + r1
b
= r1 q2 + r2
r1
= r2 q3 + r3
..
.
ri
3
= ri
2 qi 1
+ ri
ri
2
= ri
1 qi
ri
1
= ri qi+1 + 0
1
+ ri
Thus gcd (a; b) = ri . But using ri 2 = ri 1 qi + ri , we can write ri =
ri 2 ri 1 qi thus writing ri as a linear combination of ri 1 and ri 2 .Using
the previous equation, we can write ri 1 = ri 3 ri 2 qi 1 thus we can
express ri as a linear combination of ri 2 and ri 3 . Using all the equations
in the Euclidean algorithm in reverse order, we can express ri as a linear
combination of a and b.
Method 2: This proof involves the division algorithm and the Well Ordering
Principle. It is similar in some ways to the proof of the division algorithm.
Here, we will prove everything stated in the theorem. But this proof is not
constructive, it does not tell us how to ¡nd s and t. Consider the set
S = fam + bn j am + bn > 0 and m and n are integersg. Since a, b, m,
n are all integers, am+bn is an integer. So, S is a set of positive integers.
It is not empty because if am + bn < 0 then a ( m) + b ( n) > 0. Thus,
by the Well Ordering Principle, S has a smallest member, say d = as + bt.
We now prove that d = gcd (a; b). For this, we ¡rst prove that d is a
divisor of both a and b and then that it is in fact, the largest common
divisor.
d is a divisor of both a and b. First, we establish d divides a.
Using the division algorithm, we can write a = dq + r with 0 r < d.
If we had r > 0, then
r
=
a
dq
=
a
(as + bt) q
=
a
asq
=
a (1
btq
sq) + b ( tq)
Thus we would have a (1 sq) + b ( tq) 2 S contradicting d is the
smallest member of S. Thus r = 0 hence a = dq or d j a. We can
carry a similar argument for d j b. Hence, d is a common divisor to
both a and b.
d is the largest common divisor to both a and b. Suppose d0 is
another common divisor to both a and b that is a = d0 h and b = d0 k.
14
CHAPTER 1. PRELIMINARIES
Then, d = as + bt = d0 hs + d0 kt = d0 (hs + kt) so d0 is a divisor of d,
hence d > d0 . Thus d is the greatest common divisor.
There is an important corollary of this theorem, which we will often use.
Remark 39 The proof shown in method 1: also gives a way to ¡nd what that
combination is.
Example 40 Find s and t such that gcd (100; 64) = 100s + 64t.
Recall from above that gcd (100; 64) = 4. Using our computations above, we
have
4
=
28
8 3
=
28
3 (36
=
4 28
3 36
=
4 (64
36)
=
4 64
7 36
=
4 64
7 (100
28 1)
3 36
64)
7 100 + 11 64
Corollary 41 If a and b are relatively prime, then there exists integers s and
t such that as + bt = 1.
The next lemma is very important and often used.
Lemma 42 (Euclid¡¯s Lemma) Let a and b be integers. If p is prime and
p j ab then p j a or p j b.
Proof. It is enough to prove that if p - a then we must have p j b. So, suppose
p j ab and p - a. Then a and p are relatively prime and therefore there exist
integers s and t such that 1 = as + pt. Then, b = abs + bpt. Since p divides the
right hand side, it must also divide b.
p
This fact is used in particular when proving that p is irrational when p is
prime.
Prime numbers are extremely important when dealing with integers. They
are their building blocks, as the next result shows.
Theorem 43 (Fundamental Theorem of Arithmetic) Every integer greater
than 1 is either prime or a product of primes . This product is unique, except
for the order of the factors.
Proof. We will prove this result later in the chapter.
Example 44 66 = 2
3
Example 45 100 = 22 52
11
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- fx 300es plus users guide eng support home casio
- 1 sample confidence intervals student notes
- test review charlotte county public schools
- ti 83 1 propztest
- 1 2 properties of integers
- using your ti nspire calculator for hypothesis testing
- 3 confidence interval intr
- ti 83 ti 84 1 prop z int palm beach state college
- using your ti 83 84 calculator for hypothesis testing the
- impact of scaffold exploration on novel dual acting
Related searches
- ied activity 5.1 calculating properties of shapes answer key
- 16.1 properties of logarithms answers
- 1 2 cup of rice
- 16 1 properties of logarithms answers
- 16 1 properties of logarithms answer key
- ied activity 5 1 calculating properties of shapes answer key
- 2 1 properties of matter worksheet
- 1 2 and 1 2 cream
- 1 2 of 1 4 tsp
- 16 1 properties of logarithms answers book
- lesson 16 1 properties of logarithms
- properties of group 2 compound