Chapter 4

Properties of Integers
1 The Well-Ordering Principle : Mathematical Induction
+
Z = the set of integers.
Z+ = {x Z|x > 0} = {x Z|x 1} Z+ Z
Q+ = {x Q|x > 0}
R+ = {x R|x > 0}

The Well-Ordering Principle : Every nonempty subset of Z+ contains a smallest element. (We often
express this by saying that Z+ is well ordering)

Theorem 1. (The Principle of Mathematical Induction)

Let S(n) denote an open mathematical statement that involves one or more occurrences of the variable
n , which represents a positive integer.

1. If S(1) is true ; and

2. If whenever S(k ) is true (for k Z+ ), then S(k + 1) is true;

then S(n) is true for all n Z+ .

i = 1 + 2 + 3 + + n = n (n+1)
Pn
Example 1 n Z+ , i =1 2
.

Example 2
Among the 900 three-digit integer (from 100999), where the integer is the same whether it is read
from left to right or from right to left, are called palindromes. Determine all of these three-digit palin-
dromes and their sum.

Example 3
procedure sum1 (n: pos integer) procedure sum2 (n: pos integer)
begin begin
sum :=0 sum := n*(n+1)*(2*n+1)/6
for i := 1 to n do end
sum := sum + i*i
end

i 2 = n (n +1)(2n +1)
Pn
Homework Prove that for each n Z+ , i =1 6
.

Example 4 1 1+3 1+3+5 1+3+5+7

1
Example 5
Harmonic number H 1 , H 2 , H 3 where
H n = 1 + 21 + 31 + + n1 for each n Z+ .
Prove thatPn
S(n ) : j =1 H j = (n + 1)H n n, n Z+ .

Theorem 2. (The Principle of Mathematical Induction - Alternative Form)

Let S(n) denote an open mathematical statement that involves one or more occurrences of the variable
n , which represents a positive int.
Also let n 0 , n 1 Z+ with n 0 n 1

1. If S(n 0 ),S(n 0 + 1), S(n 1 1), and S(n 1 ) are true ; and

2. If whenever S(n 0 ),S(n 0 + 1), S(n 1 1), and S(k ) are true for some k Z+ , where k n 1 then
S(k + 1) is also true;

then S(n) is true for all n n 0

2
2 Recursive Definitions
+
Consider the seq b 0 ,b 1 ,b 2 , , where b n = 2n. n N
Then b 0 = 0,b 1 = 2,b 2 = 4,
=explicit formula : b n = 2n
Consider the seq a 0 , a 1 , a 2 , , where
a 0 = 1, a 1 = 2, a 2 = 3, and
a n = a n1 + a n 2 + a n 3 , n Z+ where n 3
Recursive definition.

Example 1 Define the union operation recursively.

Consider the sets A 1 , A 2 , , A n , A n +1 , where A i U for all 1 i n + 1,

1. The union of A 1 and A 2 is A 1 A 2

2. The union of A 1 , A 2 , , A n , A n +1 , for n 2, is given by

A 1 A 2 A n+1 = (A 1 A 2 A n ) A n +1

Example 2 Fibonacci numbers

1. F0 = 0, F1 = 1; and

2. Fn = Fn 1 + Fn 2 for n Z+ , n 2

Example 3 Eulerian number a n ,k

a m ,k = (m k )a m 1,k 1 + (k + 1)a m 1,k 0 k m 1
a 0,0 = 1, a m ,k = 0, k m a m ,k = 0, k < 0

1 m 5; 0 k m 1; Row Sum
(m = 1) 1 1=1!
(m = 2) 1 1 2=2! Pm 1
(m = 3) 1 4 1 6=3! Conjecture : k =0 a m ,k = m !, m Z+
(m = 4) 1 11 11 1 24=4!
(m = 5) 1 26 66 26 1 120=5!

[inductive step.]

3
3 The Division Algorithm : Prime Numbers
Definition 1
If a ,b Z and b 6= 0, we say that b divides a , and we write b |a , if there is an int n such that a = b n.

+ b is a divisor of a , or a is a multiple of b .
Theorem 3.
For a ,b, c Z

1. 1|a and a |0

2. [(a |b ) (b |a )] a = b

3. [(a |b ) (b |c )] (a |c )

4. (a |b ) (a |b x ), x Z.

5. If x = y + z , for some x , y , z Z, and a divides two of the three ints x , y , and z , then a divides the
remaining integer.

6. [(a |b ) (a |c )] a |(b x + c y ), x , y Z

7. For 1 i n , let c i Z. If a divides each c i , then a |(c 1 x 1 + c 2 x 2 + + c n x n ), where x i Z for all

1 i n.

Example 1 Do there exist integers x , y , z so that 6x + 9y + 15z = 107?

Example 2 Let a ,b Z so that 2a + 3b is a multiple of 17. Prove that 17|(9a + 5b ).

+
prime: a integer that has exactly two positive divisors.
composite: a non-prime integer.

Lemma 1. If n Z+ and n is composite, then there is a prime p such that p |n .

Theorem 4. There are infinitely many primes.

Theorem 5. (The Division Algorithm)

If a ,b Z, with b > 0, then there exist unique q, r Z with a = qb + r, 0 r < b .

4
Example 3 Write 6137 in the octal system (base 8)

+
Base 10 Base 2 Base 16
0 0000 0
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 5
6 0110 6
7 0111 7
8 1000 8
9 1001 9
10 1010 A
11 1011 B
12 1100 C
13 1101 D
14 1110 E
15 1111 F
In general, if x Z and 0 x < 2n for n Z+ , we can write x in base 2 using n bits. (0 31 : 5 bits,
+

0 63 : 6 bits)

Example 4 a b = a + (b )
twos complement method

step1: binary

step2: 0 1

step3: add 1

5
4 The Greatest Common Divisor : The Euclidean Algorithm
Definition 1
For a ,b Z, a positive int c is said to be a common divisor of a and b if c |a and c |b .

Definition 2
Let a ,b Z, where either a 6= 0 or b 6= 0. Then c Z+ is called a greatest common divisor of a ,b if

1. c |a and c |b and

2. for any common divisor d of a and b , we have d |c .

Theorem 6.
For all a ,b Z+ , there exists a unique c Z+ that is the greatest common divisor of a ,b .

* denoted gcd(a ,b )

* gcd(a ,b ) = gcd(b, a ) ; if a 6= 0, gcd(a , 0)=|a |

* gcd(0, 0) is undefined

* relatively prime : gcd(a ,b ) = 1 or there exist x , y Z with a x + b y = 1

Theorem 7. Euclidean Algorithm

Let a ,b Z+ . Set r0 = a and r1 = b and apply the division algorithm n times as follows:

r0 = q1 r1 + r2 , 0 < r2 < r1
r1 = q2 r2 + r3 , 0 < r3 < r2
r2 = q3 r3 + r4 , 0 < r4 < r3
..
.
ri = qi +1 ri +1 + ri +2 , 0 < ri +2 < ri +1
..
.
rn 2 = qn 1 rn 1 + rn , 0 < rn < rn 1
rn 1 = qn rn

Then rn , the last nonzero remainder, equals gcd(a ,b ).

Example 1 For any n Z+ , prove that 8n + 3 and 5n + 2 are relatively prime.

6
Definition 4
For a ,b, c Z+ , c is called a common multiple of a ,b if c is a multiple of both a and b . Furthermore,
c is the least common multiple of a ,b if it is the smallest of all positive integers that are common
multiple of a ,b . We denote c by lcm(a ,b )

Example 2

1. lcm(3,4) = lcm(4,3) = 12
lcm(6,15) = 30

2. For all n Z+ , lcm(1, n) = lcm(1, n) = n.

3. For a , n Z+ , lcm(a , a n ) = a n

4. If a , m , n Z+ , with m n , then lcm(a m , a n ) = a n and gcd(a m , a n ) = a m .

Theorem 8. For all a ,b Z+ , a b = lcm(a ,b )gcd(a ,b )

7
5 The Fundamental Thm of Arithmetic
Lemma 2.
If a ,b Z+ and p is prime,
p |a b p |a or p |b .

Lemma 3.
Let a i Z+ for all 1 i n . If p is prime and p |a 1 a 2 a n , then p |a i for some 1 i n .

p
Example 1 Show that 2 is irrational.

Theorem 9.
Every integer n > 1 can be written as a product of primes uniquely, up to the order of the primes.

Example 2 980,220

Example 3 Determine the number of positive divisor of n, n Z+ , n > 1.

+ Pi-notation : Q n
i =m
X i = X m X m +1 X n .
Q7 Q7
1. i =3
x i = x 3x 4x 5x 6x 7 = j =3
xi
Q6
2. i =3
i = 3 4 5 6 = 6!
2!
Q11 Q4 Q4
3. i =7
x i = x 7 x 8 x 9 x 10 x 11 = j =0
x 7+j = j =0
x 11j

e f f f
Example 4 If m , n Z+ , let m = p 1e 1 p 2e 2 p t t and n = p 1 1 p 2 2 p t t (p i : prime e i 0, f i 0, 1 i t .)