UNIT

03 Properties of the Integers

Names of Sub-Units

The Well-ordering Principle: Mathematical Induction, Recursive Definitions, the Division Algorithms:
Prime Numbers, the Fundamental Theorem of Arithmetic.

Overview

The unit started with the concept of integers and its properties. Also, the unit explained the
mathematical induction, recursive definitions, division algorithm for all the prime numbers and
fundamental theorem of arithmetic.

Learning Objectives

In this unit, you will learn to:

 Explain the concept of integers
 Describe the properties of integers
 Explain the meaning of well-ordering principle
 Analyse the principle of mathematical induction
 Describe the division algorithm for all the prime numbers
 Analyse the recursive definitions
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

Learning Outcomes

At the end of this unit, you would:

 Evaluate the value based on the principle of mathematical induction
 Prove formula that is valid for all n belongs to N by using principle of mathematical induction
 Calculate the division algorithm for the prime numbers
 Assess the problem based on the properties of the integers.
 Assess recursive function and its application
 Calculate the factorial of any number by using recursive function

3.1 INTRODUCTION
Properties of the integers include all basic properties of the positive integers, i.e., the set Z = {…...-1, 0,
1, 2, 3…….} includes commutative property for addition and commutative property for multiplication,
associative property for addition and associative property for multiplication, distributive property,
identity property for addition, identity property for multiplication, inverse property for addition and
zero property for multiplication.
The following rules of addition and multiplication of these numbers are
a) Associative law for multiplication and addition:
(a+b)+c = a+ (b+c)
And
(ab)c= a(bc)

b) Commutative law for multiplication and addition:

a+b = b+a
and
ab = ba
c) Distributive Law:
a(b+c) = ab +ac

d) Additive identity 0 and multiplicative identity 1:

a + 0 = 0+a = a
and
a*1 = 1*a = a

e) Additive inverse –a for any integer a:

a + (-a) = (-a) + a = 0

Example:
Use of correct symbol ,<, > or = between each pair of integers
(a) 4 > -7

2
UNIT 03: Properties of the Integers JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

(b) -2 > -9
(c) 6 < 8
(d) -8 < 3

3.2 THE WELL-ORDERING PRINCIPLE

Any Property of positive integers which is the same as the principle of mathematical induction is the
well-ordering principle.
Example:
Let x and y be any integers, then
(i) |a| ≥ 0, and |a| = 0 if a = 0.
(ii) -|a| ≤ a |a|.
(iii) |ab| = |a||b|
(iv) |a+b| ≤ |a| ≤|b|
(v) ||a|-|b|| ≤ |a±b|

3.2.1 Theorem (Well-ordering Principle)

Let A be a nonempty set of positive integers. Then A contains a least element; that is, A contains an
element a such that x ≤ a in A.
Normally, an ordered set A is said to be well ordered if every subset of A contains the first element. Thus
the well-ordering principle states that N is well ordered.
A set A of integers is called bounded from below if every element of A greater than some integers n.

3.3 PRINCIPLE OF MATHEMATICAL INDUCTION

The principle of Mathematical induction is used as a method of definition as well as a method of proof.
The principle of mathematical induction stated that positive integers N begin with the number 1 and the
other are obtained by successively adding 1.
Let D be a set of positive integers with the following two properties:
(i) 1 belongs to D.
(ii) If k belongs to D, then k+1 also belongs to D.
Then D is the set of all positive integers

Note: This principle is given as one of the axioms.

This principle can also be stated as:
Let P be a proposition defined on the integers n ≥ 1 such that:
(i) P(1) is true, i.e., the statement is true for n = 1, and

3
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

(ii) If P(k+1) is true whenever P(k) is true, the truth of P(k) implies the truth of P(k+1)
Thus P(n) is true for every integer n≥1, i.e., for all natural numbers n.
In order to prove a statement P(n) to be true for all natural numbers, you have the following working
rule:
1. Prove that P(1) is true,
i.e., P(n) is true for n= 1
2. Assume P(k) to be true ,
i.e., P(n) is true for n = k
3. Prove that P(k+1) is also true,
i.e., P(n) is also true for n = k+1

Example:
(a) Let P be the proposition that the sum of first n odd numbers is n2; , that is
P(n) = 1+3+5+…….+ (2n – 1) = n2
P(n) is true for n =1; that is
P(1): 1 = 12
Suppose P(n) is true. (Inductive Hypothesis).
Adding 2n+1 to both sides of P(n) you obtain
1+3+5+………+(2n-1)+(2n+1) = n2 + (2n+1)
= (n+1)2
Which is P(n+1).
You have shown that P(n+1) is true whenever P(n) is true.
Thus by the Principle of mathematical induction, P is is true for all n.
(b) Using the principle of mathematical induction, prove that n(n+1)(n+2) is a multiple of 6 for all n
belongs to N.
Let P(n): n(n+1)(n+2) is a multiple of 6
When n=1, P(1): 1.(1+1)(1+2) = 1.2.3 = 6, which is a multiple of 6
P(1) is true
Let us assume that P(k) is true for any natural number k
P(k): k(k+1)(k+2) is a multiple of 6 ------------------- (1)
Now, you shall prove that P(k+1) is also true
P(k+1): (k+1)(K+2)(k+3) is a multiple of 6
Now, (k+1)(K+2)(k+3) = (k+1)(K+2)k+3(k+1)(K+2)
=k(k+1)(K+2) + 6k’ ---------------------------------(2)
Equation (2) is a multiple of 6 as it is a sum of two multiples of 6.
[ by (1) , k(k+1)(K+2) is a multiple of 6]

4
UNIT 03: Properties of the Integers JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

Thus P(k+1) is true whenever P(k) is true.

Hence, by the principle of the mathematical induction, P(n) is true for all the natural numbers n i.e.
n(n+1)(n+2) is a multiple of 6, n belongs to

3.4 RECURSIVE FUNCTION

In many cases, it is not easy to define an object explicitly, i.e., an arrangement of numbers has no visible
pattern, then it is easy to define an object in terms of itself. This process is called recursion.
A sequence is said to be recursively defined in the sequence refers to itself. Recursion is used to define
sequences and functions.
Example:
(a)
Let <an> be the sequence given by an = 2n for n = 1,2,3......
Given sequence can also be defined by giving the first term of the sequence,
Say a0 = 2 and a formula for finding the term of the sequence from the previous one term, say
an+1 =2an, for n =0, 1, 2, ....
This formula is called the Recursive formula.
(b) For an = 5n – 3n + 2n, where a belongs to N.
we can find a1, a2, a3....
a1 = 4
a2 = 20
a3 = 106

3.4.1 Recursively Defined Function

A function is said to be a recursively defined function if we use two steps to define a function with the
set of nonnegative integers:
 Basic Step: You specify the value of the function at zero
 Recursive Step: You provide a rule for finding the value of the function at an integer n by using the
value of the function at smaller values of n.

Consider following factorial function,

f(n) = n!
You have 0! = 0, 1! = 1, 2! = 2 , 3! = 3*2*1 = 6
4! = 4*3*2*1 = 24, .....
5! = 5*4*3*2*1 = 120
6! = 6*5*4*3*2*1 = 720
f(n) can also be defined as
n! = n(n-1)! For n ≥ 1 and 0! =1.

5
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

3.5 DIVISION ALGORITHM

An Algorithm is a process of obtaining a result by repeated application of an operation. For example,
for finding the g.c.d of two numbers, we use repeated application of division operation. Therefore, this
process is known as the division algorithm.
Let a and b be integers with b≠ 0, then there exist integers q and r such that
a = bq+r and 0 ≤ r < |b|.
Here, the integers q and r are unique.
The number q in the above is called quotient, and r is called the remainder, r must be nonnegative.
Example:
109 = 15*7 + 4 and 0 < 4 <15
Here, You see that division of 109 by 15 gives us 7 as quotient and 4 as remainder.
Similarly,
-230 = 16(-15) + 10 and 0 <10 <|-15| =15
we see that division of -230 by 16 gives us -15 as quotient and 10 as remainder.
Theorem: Every integer n>1 can be written as a product of prime numbers.
Proof:
You prove the theorem by the principle of mathematical induction.
Let p=2. Since 2 is a prime number, n is a product of primes.
Suppose n > 2, and the theorem holds for positive integers less than n. if n is a prime number, then n is a
product of prime numbers. If n is a composite number then n = ab where a, b < n.
By induction, a and b are products of primes; hence n = ab is also a product of primes.
Example:
Find G.C.D(28, 49)
We have 49 = 28*1 + 21
28 = 21*1 + 7
21 = 7*3 + 0
Therefore, G.C.D of 28 and 49 = (28, 49) = 7

3.6 THE FUNDAMENTAL THEOREM OF ARITHMETIC

Every integer n>1 can be expressed uniquely as a product of primes. It is also called the unique
factorization theorem and prime factorisation theorem.
The primes in the factorization of n need not be distinct. Then n can be expressed uniquely in the form
r

mi
p
n = p 1 p 2 p r
m1 m2 mr
= i1 i

where the mt are positive an dp1  p2  pr . This is called the canonical factorisation of n.

6
UNIT 03: Properties of the Integers JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

Example:
(a) 15 = 3*5
Where 3 and 5 are prime numbers
(b) 30 = 2*3*5
Where 2 ,3 and 5 are prime numbers
(c) 1000 = 23 * 53
Where 2 and 3 are prime numbers.

In a competition, the time taken by two students to complete one round is 30 minutes and 45 minutes,
respectively. After how much time will they meet again at the starting point.
Solution:
As the time taken by student B is more compared to that of A to complete one round therefore it can be
assumed that A will reach early and both the students will meet again when A has already reached the
starting point. This time can be calculated by finding the L.C.M of the time taken by each.
30 = 2 × 3 × 5
45 = 3 × 3 × 5
The L.C.M is 90.

Thus, both the students will meet at the starting point after 90 minutes.
Prime factor of 70 is
70 = 2*5*7

Conclusion 3.7 CONCLUSION

 It is more essay to Prove formulas that are valid for all n belongs to N by using the Principle of
Mathematical induction.
 The division algorithm computes the Quotient as well as the remainder of the given number.
 Recursion function is used to compute power of a number, factorial function and to draw a type of
fractal.
 Integers are very applicable in daily life, i.e., integers are used in describing temperature above/
below, freezing point, the geographical level above/below sea level bonus and penalty in quizzes/
games, etc.

3.8 GLOSSARY

 Integers: A number which can not be a fraction; a whole number.

Z = {................-2, -1, 0, 1, 2,3............. }
 Prime Numbers: A number which can be divisible by itself and 1 only is called prime numbers.
 Recursive Function: Recursive function is to define an object in terms of itself, is called recursion
function.

7
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

 Division Algorithm:
Let a and b be integers with b≠ 0, then there exist integers q and r such that
a = bq+r and 0 ≤ r < |b|.
Here, the integer q and r are unique numbers.
 The Fundamental Theorem of Arithmetic: Every integer number n>1 can be expressed uniquely as
the product of primes. It is also called the unique factorization theorem.
 Factors: A factor is a number that divides into another number exactly and leaves a remainder zero
in all cases.

3.9 SELF-ASSESSMENT QUESTIONS

A. Essay Type Questions

1. Explain the properties of the integers.
2. Explain the uses of principle of Mathematical induction.
3. Discuss the concept of division algorithm.
4. Find all the integers n such that
(a) 1< 2n-6 < 14
(b) 2< 8- 3n < 18
5. For each pair of integers a and b, find integers q and r such that a = bq+ r and 0≤ r <|b|:
a = -381 and b = 14
6. List all primes between 50 and 100.

3.10 ANSWERS AND HINTS FOR SELF-ASSESSMENT QUESTIONS

A. Hints for Essay Type Questions

1. Properties of the integers include all basic properties of the positive integers, i.e., the set Z = {…...-1, 0,
1, 2, 3…….} includes commutative property for addition and commutative property for multiplication,
associative property for addition and associative property for multiplication, distributive property,
identity property for addition, identity property for multiplication, inverse property for addition
and zero property for multiplication. Refer to Section Properties of the Integers.
2. The principle of Mathematical induction is used as a method of definition as well as a method of
proof. The principle of mathematical induction stated that positive integers N begin with the number
1 and the other are obtained by successively adding 1. Refer to Section Principle of Mathematical
Induction.
3. An Algorithm is a process of obtaining a result by repeated application of an operation. For example,
for finding the g.c.d of two numbers, we use repeated application of division operation. Therefore,
this process is known as the division algorithm. Refer to Section Division Algorithm.
4.
(a) 4, 5, 6, 7, 8, 9

8
UNIT 03: Properties of the Integers JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

(b) –2, –1, 0, 1

5. q = –28 and r = 11
6. 51, 53, 57, 59,61, 71, 73, 79, 83, 87, 89, 91, 93, 97

@ 3.11 POST-UNIT READING MATERIAL

 https://byjus.com/maths/number-system/

3.12 TOPICS FOR DISCUSSION FORUMS

 Discuss why it is important to know about the properties of the integers.

 Discuss the fundamental theorem of arithmetic.