Basic Logic and Number Theory
Basic Logic and Number Theory
NUMBER THEORY
(MTS1 B01)
I SEMESTER
CORE COURSE
B.Sc. MATHEMATICS
(2020 Admission onwards)
UNIVERSITY OF CALICUT
School of Distance Education,
Calicut University P.O.
Malappuram - 673 635, Kerala.
19551
UNIVERSITY OF CALICUT
SCHOOL OF DISTANCE EDUCATION
Self Learning Material
B.Sc. Mathematics (First Semester)
(2020 Admission Onwards)
MTS1 B01 : Basic Logic and Number Theory
Scrutinized by:
Dr.Bijumon R., Associate Professor and Head,
Department of Mathematics,
Mahatma Gandhi College, Iritty
Keezhur P.O., Kannur Dt.
DISCLAIMER
'' The author shall be''solely responsible for the
content and views expressed in this book''
Contents
1 Propositions 3
2 Logical Equivalences 31
3 Quantifiers 42
4 Arguments 51
5 Proof Methods 71
6 Mathematical Induction 97
7 Recursion 110
15 Congruences 216
Syllabus 286
A note to the students
1
2
Take special care to do all the exercises listed in the book, that
will give you much confidence for future studies and to face the exams.
Doing problems in an analytic and systematic way helps to internal-
ize the abstract mathematical concepts more better. Always remember
that success is never an accident, it is the final outcome of
purposeful activities and hard work.
Queries and suggestions are most welcome and that can be mailed
to: vinodunical@gmail.com
Tirur
01. 12. 2021 Dr. Vinod Kumar P
Chapter 1
Propositions
Introduction
The basic building blocks of logic are propositions. Before giving the
definition of proposition, we note that statement is a declarative sentence
(i.e., a sentence that declares a fact). For example, the following are
statements:
3
4 Propositions
The following are not declarative sentences and hence not statements:
Definition
A proposition is a declarative sentence that is either true or false, but
not both. We denote it by the lowercase letters p ,q ,r, s, or t. The
variables p ,q ,r, s, or t are boolean variables (or logic variables).
Example 1
Consider the following statements.
1. 2 is an even number
2. 3 is an even number.
3. Chennai is a state of India.
4. Lotus is the national flower of India.
All these statements are propositions, since each of them has a truth
value. Propositions 1 and 4 are true, where 2 and 3 are false.
Some sentences that are not propositions are given in the next ex-
ample.
Propositions 5
Example 2
Consider the following sentences.
1. Wake up.
2. Who is that?
3. x + 2 = 12
4. x + y = z
Sentences 1 and 2 are not propositions because they are not declara-
tive sentences. Sentences 3 and 4 are not propositions because they are
neither true nor false, since the values are not assigned to the variables
in these sentences.
Notations
Letters are used to denote propositions, just as letters are used to denote
variables.
The conventional letters used for this purpose are p, q, r, s, . . . .
The area of logic that deals with propositions is called the proposi-
tional calculus or propositional logic.
Definition
Let p be a proposition. The statement
6 Propositions
Table 1 :
p ¬p
T F
F T
Example 3
Let p: Delhi is the capital of India.
The negation of p is
Definition
Let p and q be propositions. The proposition “p and q”, denoted by
p ∧ q, is the proposition that is true when both p and q are true and is
false otherwise. The proposition p ∧ q is called the conjunction of p
and q.
The truth table for p ∧ q is shown in Table 2. Note that there are
four rows in this truth table, one row for each possible combination of
Propositions 7
Table 2 :
p q p∧q
TT T
TF F
FT F
FF F
Example 4
Find the conjunction of the propositions p and q where p is the propo-
sition “Today is Friday” and q is the proposition “It is raining today”.
Solution
Expressions that yield the value true or false are boolean expressions,
and they often occur in both mathematics and computer science. For
instance, 1 < 2 and 3 < 1 are boolean expressions. If- statements and
while-loops in computer programs often use such expressions, and their
values determine whether or not if-statements and while-loops will be
executed.
Definition
Let p and q be propositions. The proposition “p or q”, denoted by p ∨ q,
is the proposition that is false when p and q are both false and true
otherwise. The proposition p ∨ q is called the disjunction of p and q
8 Propositions
Table 3 :
p q p∨q
TT T
TF T
FT T
FF F
Example 5
What is the disjunction of the propositions p and q where p is the propo-
sition “Today is Friday” and q is the proposition “It is raining today”.
Solution
This proposition is true on any day that is either a Friday or a rainy day
(including rainy Fridays). It is false on days that are not Fridays when
it also does not rain.
Definition
Let p and q be propositions. The exclusive or of p and q, denoted by
p ⊕ q, is the proposition that is true when exactly one of p and q is true
and is false otherwise.
Table 4 :
Propositions 9
p q p⊕q
TT F
TF T
FT T
FF F
Conditional Statements
Definition
Let p and q be the propositions. The implication p → q is the proposition
that is false when p is true and q is false and true otherwise. In this
implication p is called the hypothesis (or antecedent or premise) and q
is called the conclusion (or consequence).
Table 5 :
p q p→q
TT T
TF F
FT T
FF T
Various terminology for indicating p → q are:
“If p, q” ; “p only if q”
10 Propositions
“p is sufficient for q” ; “q if p”
Remark
Note that p → q is false only in that case p is true but q is false, so that
it is true when both p and q are true, and when p is false (no matter
what truth value q has).
The implication
Example 7
What is the value of the variable x after the statement
“if 2 + 2 = 4 then x := x + 1”
Solution
Example 8
Find the converse and the contra positive of the implication
Solution
1. The converse is
Definition
Let p and q be the propositions. The biconditional p ↔ q is the
proposition that is true when p and q have the same truth values and is
false otherwise.
The truth table for p ↔ q is shown in Table 6. Note that the bi-
conditional p ↔ q is true precisely when both the implications p → q
and q → p are true. Because of this, the terminology “p if and only if
q” is used for this biconditional. Other common ways of expressing the
Propositions 13
Table 6 :
p q p↔q
TT T
TF F
FT F
FF T
Example 9
Translate the following English sentence into a logical expression.
“You can access the Internet from campus only if you are a computer
science student or you are not a freshman.”
Solution
There are many ways to translate this sentence into a logical ex-
pression. Although it is possible to represent the sentence by a single
prepositional variable, such as p, this would not be useful when analyz-
ing its meaning or reasoning with it. Instead, we will use propositional
variables to represent each sentence part and determine the appropriate
logical connectives between them. In particular, we let a, c, and f rep-
resent “You can access the Internet from campus,” “You are a computer
science student,” and “You are a freshman,” respectively. Noting that
“only if” is one way an implication can be expressed, this sentence can
be represented as
a → (c ∨ ¬f ).
Example 10
14 Propositions
“You cannot ride the roller coaster if you are under 4 feet tall unless
you are older than 16 years old.”
Solution
There are many ways to translate this sentence into a logical ex-
pression. The simplest but least useful way is simply to represent the
sentence by a single propositional variable, say, p. Although this is
not wrong, doing this would not assist us when we try to use proposi-
tional variables to represent each of the sentence parts and to decide on
the appropriate logical connectives between them. In particular, we let
q, r, and s represent “You can ride the roller coaster,” “You are under 4
feet tall,” and “You are older than 16 years old,” respectively. Then the
sentence can be translated to
(r ∧ ¬s) → ¬q.
Order of Precedence
Definition
A compound proposition that is always true, no matter what the truth-
values of the propositions that occur in it, is called a tautology. A
compound proposition that is always false is called a contradiction. A
proposition that is neither a tautology nor a contradiction is called a
contingency.
Example 11
We can construct examples of tautologies and contradictions using just
one proposition. Consider the truth of p ∨ ¬p andp ∧ ¬p, shown in Table
1. Since p ∨ ¬p is always true, it is a tautology. Since p ∧ ¬p is always
false, it is a contradiction.
Table 7:
p ¬p p ∨ ¬p p ∧ ¬p
T F T F
T T T F
Exercises
1. Which of the following sentences are propositions? What are the
truth-values of those that are propositions?
3. 2 + 3 = 5.
4. 5 + 7 =10.
16 Propositions
5. x + 2 = 11.
1. Today is Monday.
3. 2 + 1 = 3.
p : It is below freezing.
q : It is snowing.
2. You drive over 65 miles per hour, but you do not get a speeding
ticket.
3. You will get a speeding ticket if you drive over 65 miles per hour.
4. If you do not drive over 65 miles per hour, then you will not get a
speeding ticket.
6. You get a speeding ticket, but you do not drive over 65 miles per
hour.
7. Whenever you get a speeding ticket, you are driving over 65 miles
per hour.
1. If 1 + 1 = 2, then 2 + 2 = 5.
2. If 1 + 1 = 3, then 2 + 2 = 4.
3. If 1 + 1 = 3, then 2 + 2 = 5.
8. If 2 + 2 = 4, then 1 + 2 = 3.
6. For each of the following sentences, state what the sentence means if
the or is an inclusive or (that is, a disjunction) versus an exclusive
or. What of these meanings of or do you think is intended?
2. When you buy a new car from Hindustan Motor Company, you
get Rs.20,000 back in cash or a 8% car loan.
3. Dinner for two includes two items from column A or three items
from column B.
4. School is closed if more than 2 feet of snow falls or if the wind chill
is below −100.
a tourist asks. Suppose you are a tourist visiting this area and come to
a fork in the road. One branch leads to the ruins you want to visit; the
other branch leads deep into the jungle. A villager is standing at the fork
in the road. What one question can you ask the villager to determine
which branch to take?
3. That India win the championship implies that they beat Sri Lanka.
6. If you drive more than 400 miles, you will need to buy gasoline.
1. If it is hot outside you buy an ice cream cone, and if you buy an
ice cream cone it is hot outside.
2. For you to win the contest it is necessary and sufficient that you
have only the winning ticket.
3. You get promoted only if you have connections, and you have con-
nections only if you get promoted.
20 Propositions
5. The trains run late on exactly those days when I take it.
10. State the converse and contra positive of each of the following im-
plications.
11. Construct a truth table for each of the following compound propo-
sitions.
a) p ∧ ¬p b) p ∨ ¬p
c) (p ∨ ¬q) → q d)(p ∨ q) → (p ∧ q)
e) (p → q) ↔ (¬q → ¬p) f) (p → q) → (q → p)
12. Construct a truth table for each of the following compound propo-
sitions.
a) p → ¬q b) ¬p ↔ q
c) (p → q) ∨ (¬p → q) d) (p → q) ∧ (¬p → q)
13. Construct a truth table for each of the following compound propo-
sitions.
a) p → (¬q ∨ r) b) ¬p → (q → r)
Propositions 21
c) (p → q) ∨ (¬p → r) d) (p → q) ∧ (¬p → r)
a) (p ∧ q) → p b)p → (p ∨ q)
c) ¬p → (p → q) d) (p ∧ q) → (p → q)
e) ¬(p → q) → p f) ¬(p → q) → ¬q
Answers
3. (a) p∧q (b) p∧¬q (c) ¬p∧¬q (d) p∨q (e) p → q (f) (p∨q)∧(p → ¬q)
(g) q ↔ p
(b) Inclusive or: You can take the rebate, or you can get a low-interest
loan, or you can get both the rebate and a low interest loan. Exclusive
or: You can take the rebate, or you can get a low-interest loan, but
you cannot get both the rebate and a low interest loan. Most likely the
exclusive or is intended.
(c) Inclusive or: You can order two items from column A and none
from column B, or three items from column B and none from column
A, or five items including two from column A and three from column B.
Exclusive or: You can order two items from column A or three items from
column B, but not both. Almost certainly the exclusive or is intended.
(d) Inclusive or: More than 2 feet of snow or wind chill below −100,
or both, will close school. Exclusive or: More than 2 feet of snow or
wind chill below −100, but not both, will close school. Certainly the
inclusive or is intended.
7. “If were to ask you whether the right branch leads to the ruins, would
you answer yes?”
(b) If it stays warm for a week, then the apple trees will bloom.
(c) If India win the championship, then they beat Sri Lanka
(d) If you get to the top of Long’s Peak, then you must have walked
8 miles.
(e) If you are world-famous, then you will get tenure as a professor.
Propositions 23
(f) If you drive more than 400 miles, then you will need to buy
gasoline.
(g) If your guarantee is good, then you must have bought your CD
player less than 90 days ago.
9. (a) You buy an ice cream cone if and only if it is hot outside.
(b) You win the contest if and only if you hold the only winning
ticket.
(d) Your mind will decay if and only if you watch television.
(e) The train runs late if and only if it is a day I take the train.
10. (a) Converse: “I will ski tomorrow only if it snows today”. Contra-
positive: “If I do not ski tomorrow, then it will not have snowed today”.
(b) Converse: “If I come to class, then there will be a quiz”. Contra-
positive: “If I do not come to class, then there will not be quiz”.
11.
(a) p ¬p p ∧ ¬p (b) p ¬p p ∨ ¬p
T F F T F T
F T F F T T
24 Propositions
(c) pq ¬q p ∨ ¬q (p ∨ ¬q) → q
TT F T T
TF T T F
FT F F T
FF T T F
(e) (p → q) ↔
pq p→q ¬q ¬p ¬q → ¬p
(¬q → ¬p)
TT T F F T T
TF F T F F T
FT T F T T T
FF T T T T T
(e) (p → q) ↔
pq p→q ¬q ¬p ¬q → ¬p
(¬q → ¬p)
TT T F F T T
TF F T F F T
FT T F T T T
FF T T T T T
Propositions 25
12.
(a) pq p → ¬q (b) pq ¬p ↔ q
TT F TT F
TF T TF T
FT T FT T
FF T FF F
(c) (p → q) ∨ (d) (p → q) ∧
pq pq
(¬p → q) (¬p → q)
TT T TT T
TF T TF F
FT T FT T
FF T FF F
13.
14.
28 Propositions
(p ↔ q) ↔
pqrs p↔q r↔s
(r ↔ s)
TTTT T T T
TTTF T F F
TTFT T F F
TTFF T T T
TFTT F T F
TFTF F F T
TFFT F F T
TFFF F T F
FTTT F T F
FTTF F F T
FTFT F F T
FTFF F T F
FFTT T T T
FFTF T F F
FFFT T F F
FFFF T T T
15.
(c) pq ¬p p→q ¬p → (p → q)
TT F T T
TF F F T
FT T T T
FF T T T
16. In each case we will show that if the hypothesis is true, then the
conclusion is also.
(c) If the hypothesis ¬p is true, that is, if p is false, then the conclusion
p → q is true.
(d) If the hypothesis p ∧ q is true, then both p and q are true so that the
conclusion p → q is also true.
Definition
The proposition p and q are logically equivalent if p ↔ q is a tautology.
Notations
31
32 Logical Equivalences
Example 1
Show that ¬(p∨q) and ¬p∧¬q are logically equivalent. This equivalence
is one of De Morgan’s laws for propositions named after the English
mathematician Augustus De Morgan of the mid-nineteenth century.
Solution
Table 1:
p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
Example 2
Show that the propositions p → q and ¬p ∨ q are logically equivalent.
Solution
Table 2:
p q ¬p ¬p ∨ q p→q
TT F T T
TF F F F
FT T T T
FF T T T
Example 3
Show that the propositions p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically
equivalent. This is the distributive law of disjunction over conjunction.
Solution
Table 3 :
Example 4
Verify that p ∧ T ≡ p and p ∨ F ≡ p.
Solution
p T p∧T p F p∨F
T T T T F T
F T F F F F
Example 5
Verify that ¬(¬p) ≡ p.
Solution.
Verification is made through the following truth table.
p ¬p ¬¬p
T F T
F T F
Equivalence Name
p∧T⇔p
Identity laws
p∨F⇔p
p∨T⇔T
Domination laws
p∧F⇔F
p∨p⇔p
Idempotent laws
p∧p⇔p
¬(¬p) ⇔ p Double negation
law
p∨q ⇔q∨p
Commutative
p∧q ⇔q∧p
laws
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)
Associative laws
(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)
Distributive laws
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
¬(p ∧ q) ⇔ ¬p ∨ ¬q
De Morgan’s laws
¬(p ∨ q) ⇔ ¬p ∧ ¬q
p ∨ ¬p ⇔ T
P ∧ ¬p ⇔ F
(p → q) ⇔ (¬p ∨ q)
The associative law for disjunction shows that the expression p ∨ q ∨ r
is well defined, in the sense that it does not matter whether we first take
the disjunction of p and q and then the disjunction of p ∨ q with r, or if
we first take the disjunction of q and r and then take the disjunction of p
and q ∨ r. Similarly, the expression p ∧ q ∧ r is well defined. By extending
this reasoning, it follows that p1 ∨ p2 ∨ ... ∨ pn and p1 ∧ p2 ∧ ... ∧ pn
36 Logical Equivalences
and
¬(p1 ∧ p2 ∧ ... ∧ pn ) ⇔ (¬p1 ∨ ¬p2 ∨ ... ∨ ¬pn ).
Example 6
Verify that p ∨ p ≡ p and p ∧ p ≡ p
Solution
p p p∧p p p p∨p
T T T T T T
F F F F F F
The logical equivalences in Table 4, as well as any others that have been
established (such as those shown in table 5), can be used to construct ad-
ditional logical equivalences. The reason for this is that a proposition in a
compound proposition can be replaced by one that is logically equivalent
to it without changing the truth-value of the compound proposition.
Example 7
Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent.
Solution
at a time starting with ¬(p ∨ (¬p ∨ ¬q)) and ending with¬p ∧ ¬q. We
have the following equivalences.
Example 8
Show that (p ∧ q) → (p ∨ q) is a tautology,
Solution
(p ∧ q) → (p ∨ q) ⇔ ¬(p ∧ q) ∨ (p ∨ q) by Example 3
Exercises
a) p ∧ T ⇔ p b) p ∨ F ⇔ p
c) p ∧ F ⇔ F d) p ∨ T ⇔ T
e) p ∨ p ⇔ p f) p ∧ p ⇔ p
a) p ∨ q ⇔ q ∨ p b) p ∧ q ⇔ q ∧ p
a) [p ∨ (p ∧ q)] ⇔ p b) [p ∧ (p ∨ q)] ⇔ p
Answers
p q p∨q q∨p
T T T T
2. (a) T F T T
F T T T
F F F F
p q p∧q q∧p
T T T T
(b) T F F F
F T F F
F F F F
4. (a) If p is true, then p ∨ (p ∧ q) is true since the first proposition
40 Logical Equivalences
(b) If p is false, then p∧(p∨q) is false since the first part of the conjunction
is false. On the other hand, if p is true, then both parts of the conjunction
are true since p ∨ q is also true. Since p and p ∧ (p ∨ q) always have the
same truth value, they are equivalent.
5. These are not logically equivalent since when p, q, and r are all false,
(p → q) → r is false, but p → (q → r) is true.
Introduction
are often found in mathematics. These statements are neither true nor
false when the values of the variables are not specified. In this chapter
we will discuss the ways of producing propositions from such statements.
The statement “x is greater than 4” has two parts. The first part,
the variable x, is the subject of the statement. The second part- the
predicate, “is greater than 4”- refers to a property that the subject of
the statement can have. We can denote the statement “x is greater than
4” byP (x), where P denotes the predicate “is greater than 4” and x is
the variable. P is called the propositional function. The statement
P (x) is also said to be the value of the propositional function P at
42
Quantifiers 43
x. Once a value has been assigned to the variable x, the statement P (x)
becomes a proposition and has a truth-value. Consider the following
example.
Example 1
Let P (x) denote the statement “x > 4”. What are the truth values of
P (5) and P (2)?
Solution
We can also have statements that involve more than one variable.
For instance consider the statement “x = y + 2”. We can denote this
statement by Q(x, y), where x and y are variables and Q is the predicate.
When values are assigned to the variables x and y, the statement Q(x, y)
has a truth-value.
Example 2
Let Q(x, y) denote the statement “x = y +2”. What are the truth-values
of the propositions Q(1, 2) and Q(2, 0)?
Solution
Example 3
Let R(x, y, z) denote the statement “x + y = z”. When values are as-
signed to the variables x, y, and z this statement has a truth value. What
44 Quantifiers
are the truth values of the propositions R(1, 2, 3) and R(0, 0, 1)?
Solution
Quantifiers
Definition
The universal quantification of P (x) is the proposition
Quantifiers 45
Notation
∀xP (x) denotes the universal quantification of P (x). Here ∀ is called
the universal quantifier. The proposition ∀xP (x) is also expressed as
Remark
It is best to avoid the word “any” since it is often ambiguous as to
whether it means “every’ or “some.”.
Example 4
Express the statement
as a universal quantification.
Solution
Then the statement “Every student in this class has studied calculus”
can be written as ∀xP (x), where the universe of discourse consists of the
students in this class.
∀xS(x) → P (x)
“ x is in this class”.
46 Quantifiers
P (x) is as before, and the universe of discourse is the set of all students.
Example 4 illustrates that there is often more than one good way to
express quantification.
Example 5
Let P (x) be the statement “x + 1 > x.” What is the truth-value of the
quantification ∀xP (x), where the universe of discourse is the set of real
numbers?
Solution
Since P (x) is true for all real numbers x, the quantification ∀xP (x)
is true.
Example 6
Let Q(x) be the statement “x < 2.” What is the truth-value of the
quantification ∀xQ(x), where the universe of discourse is the set of real
numbers?
Solution
Q(x) is not true for all real numbers x, since, for instance, Q(3) is
3 < 2 which is false. Thus ∀xQ(x)is false.
Example 7
What is the truth-value of ∀xP (x), where P (x) is the statement “x2 <
10” and the universe of discourse consists of the positive integers not
exceeding 4?
Quantifiers 47
Solution
since the universe of discourse consists of the integers 1,2,3, and 4. Since
P (4), which is the statement “42 < 10” is false, it follows that ∀xP (x)
is false.
Definition
The existential quantification of P (x) is the proposition
Notation
We use the notation
∃x P (x)
or
Example 8
Let P (x) denote the statement “x > 3.” What is the truth value of the
quantification ∃x P (x), where the universe of discourse is the set of real
numbers?
Solution
Since “x > 3” is true - for instance, when x = 5 - the existential quan-
tification of P (x), which is ∃ xP (x), is true.
Example 9
Let Q(x) denote the statement “x = x + 1.” What is the truth value of
the quantification ∃xQ(x), where the universe of discourse is set of real
numbers?
Solution
Since Q(x) is false for every real numbers x, the existential quantifi-
cation of Q(x), which is ∃xQ(x), is false.
Example 10
What is the truth value of ∃x P (x) where P (x) is the statement “x2 >
10” and the universe of discourse consists of the positive integers not
exceeding 4?
Solution
Quantifiers 49
Since the universe of discourse is {1, 2, 3, 4}, the proposition ∃xP (x)
is the same as the disjunction P (1) ∨ P (2) ∨ P (3) ∨ P (4). Since P (4),
which is the statement “42 > 10,” is true, it follows that ∃xP (x) is true.
Table 1 : Quantifiers
At the end of this chapter, we like to point out that what we discussed
in Sections 1 and 2 is propositional logic; it deals with unquanti-
fied propositions. However, as we saw throughout this section, not all
propositions can be symbolized in propositional logic, so quantifiers are
needed. The area of logic that deals with quantified propositions is
known as predicate logic.
Exercises
4. ¬(∀x)(x3 = x)
Let P (x) : x2 > x, Q(x) : x2 = x, and the UD is the set of all integers.
Determine the truth value of each proposition.
5. (∀x)[¬P (x)]
6. (∃x)[P (x) ∧ Q(x)]
7. (∃x)[P (x) ∨ Q(x)]
Negate each proposition, where x is an arbitrary integer.
8. (∀x)(x2 > 0)
9. (∃x)(x2 6= 5x − 6)
Rewrite each sentence symbolically, where the UD consists of real num-
bers.
11. For each real number x, there is some real number y such that
x·y =x
Introduction
51
52 Arguments
The terms lemma and corollary are used for certain types of theorems.
5. Four colour problem was another conjecture till 1976 (See the end
section of this chapter). After the proof was given in 1976, four
colour conjectures is now called four colour theorems.
Table 1, given in the next page lists some important rules of inference.
The verifications of these rules of inference can be found in Examples
and as Exercises of the previous Chapter.
Example 1
Suppose that the implication “if it snows today, then we will go skiing”
and its hypothesis, “it is snowing today,” are true. Then, by modus
ponens, it follows that the conclusion of the implication, “we will go
skiing,” is true.
Example 2
State which rule of inference is the basis of the following arguments:
Solution
p
...p ∨ q
Solution
p∧q
...p
p
p→q
...q
Using this notation, the hypotheses are written in a column and the
conclusion below a bar. (The symbol . . . denotes “therefore.”) Modus
ponens states that if both an implication and its hypothesis are known
to be true, then the conclusion of this implication is true.
Example 4
The implication “if n is divisible by 3, then n2 is divisible by 9,” is true.
Consequently, if n is divisible by 3, then by modus ponens, it follows
that n2 is divisible by 9.
Example 5
State which rule of inference is used in the argument:
barbecued food – food cooked on a metal frame over hot coals in an open
fire
Solution
p→q
q→r
. . . p→r
Definition
An argument is called valid if whenever all the hypotheses are true, the
conclusion is also true. Consequently, showing that q logically follows
from the hypothesis p1 , p2 , . . . , pn is the same as showing that the
implication
(p1 ∧ p2 ∧ . . . ∧ pn ) → q
Attention!
A valid argument can leads to a incorrect conclusion if one or more false
propositions are used within the argument. For example:
When there are many premises, several rules of inference are often
needed to show that an argument is valid. This is illustrated by the
following examples, where the steps of arguments are displayed step by
step, with the reason for each step explicitly stated. These examples also
show how arguments in English can be analyzed using rules of inference.
Example 6
Show that the hypotheses “It is not sunny this afternoon and it is colder
than yesterday,” “We will go swimming only if it is sunny,” “If we do
not go swimming, then we will take a canoe2 trip,” and “If we take a
canoe trip, then we will be home by sunset” lead to the conclusion “We
will be home by sunset.”
2
canoe – a light narrow boat with both ends sharp that is usually pro-
pelled by paddling
Solution
Step − Reason
1. ¬p ∧ q − Hypothesis
3. r → p − Hypothesis
5. ¬r → s − Hypothesis
7. s → t − Hypothesis
Example 7
Show that the hypothesis “If you send me an e-mail message, then I will
finish writing the program,” “If you do not send me an e-mail message,
then I will go to sleep early,” and “If I go to sleep early, then I will wake
up feeling refreshed” lead to the conclusion “If I do not finish writing
the program, then I will wake up feeling refreshed.”
Solution
The following arguments shows that our hypothesis lead to the de-
sired conclusion.
Step − Reason
1. p → q − Hypothesis
2. ¬q → ¬p − Contrapositive of Step 1
3. ¬p → r − Hypothesis
Arguments 59
5. r → s − Hypothesis
Exercises
d) If it snows today, the university will close. The university is not closed
today. Therefore, it did not snow today.
e) If I go swimming, then I will stay in the sun too long. If I stay in the
sun too long, then I will sunburn. Therefore, if I go swimming, then I
will sun burn.
a) “If I take the day off, it either rains or snows.” “I took Tuesday off
or I took Thursday off”. It was sunny on Tuesday.” It did not snow on
Thursday.”
b) “If I eat spicy foods, then I have strange dreams.” “I have strange
dreams if there is thunder while I sleep.” “I did not have strange
dreams.”
g) “All rodents gnaw their food.” “Mice are rodent.” “Rabbits do not
gnaw their food.” “Bats are no rodents.”
11. Prove that the sum of an irrational number and a rational number
is irrational using a proof by contradiction.
15. Prove that if x and y are real numbers, then max(x, y) + min(x, y) =
x + y (Hint: Use a proof by cases with the two cases corresponding to
x ≥ y and x < y, respectively.)
16. Prove that if x and y are real numbers then |x|+|y| ≥ |x + y| (where
|x| represents the absolute value of x if x ≥ 0 and equal −x if x ≤ 0).
min(a, min(b, c)) = min(min(a, b), c) whenever a, b and c are real num-
bers.
21. Prove or disprove that every positive integer can be written as the
sum of the squares of two integers.
22. We define the floor and ceiling functions on the set of real numbers,
respectively, as below: For real number x,
That is, bxc , called the floor of x, denotes the greatest integer that does
not exceed x and dxe , called the ceiling of x, denotes the least integer
that does not exceed x.
Prove or disprove each of the following statements about the floor and
ceiling functions.
e) x2 = x+1
2 for all real numbers x.
27. Prove or disprove that there are three consecutive odd positive inte-
gers that there are primes, that is, odd primes of the form p, p+2, and
p+4
Answers
1. a) Addition b) Simplification
e) Hypothetical syllogism
2. Let w be “Asok works hard,” let d be “Asok is a dull boy”, and let j
be “Asok will get the job.” The hypotheses are w, w → d, and d → ¬ j.
Arguments 65
Using modus ponens and the first two hypotheses, d follows. Using
modus ponens and the last hypothesis, which is the desired conclusion,
¬ j: “Asok will not get the job”, follows.
4. a) Valid conclusions are “I did not take Tuesday off,” “I took Thursday
off,” “It rained on Thursday.”
b) “I did not eat spicy foods and it did not thunder” is a valid con-
clusion.
e) “That you buy lots of stuff is good for the U.S. and is good for
you” is a valid conclusion.
f) “ Mice gnaw their food” and “Rabbits are not rodents” are valid
conclusions.
16. There are four cases. Case 1 : x ≥ 0 and y ≥ 0. Then |x| + |y| =
x + y = |x + y|. Case 2 : x < 0 and y < 0. Then x| + |y| = −x + (−y)
= −(x + y) = |x + y| since x + y < 0. Case 3 : x ≥ 0 and y < 0. Then
68 Arguments
17. There are three cases to consider : Case 1, a is smallest, or tied for
smallest; Case 2, b is smallest, or tied for smallest; Case 3, c is smallest, or
tied for smallest. Since one of a, b, and c is smallest, or tied for smallest,
these three cases cover all possibilities. In Case 1, a ≤ min(b, c), so the
left-hand side is a and the right hand side is also a since min (a, c) = a.
The argument in the other two cases is similar.
20. This proposition is true. Suppose that m is neither 1 nor −1. Then
mn has a factor m larger than 1. On the other hand, mn = 1, and 1 has
no such factor. Hence m = 1 or m = −1. In the first case n = 1, and in
1
the second case n = −1, since n = m.
21. The positive integer 3 is not the sum of two squares of integers, so
that the proposition is false.
1
b) False; x = 2 is a counter example.
23. a) If x is positive integer, then the two side are equal. So suppose
that x = n2 +m+ε, where n2 is the largest perfect square less than x, m
√ p √
is a nonnegative integer, and 0 < ε ≤ 1. Then x and bxc = n2 + m
are between n and n + 1, so both sides equal n.
26. We will show that the four statements are equivalent by showing
that (i) implies (ii), (ii) implies (iii), (iii) implies (iv), and (iv) implies
(i). First, assume that n is even. Then n = 2k for some integer k. Then
n + 1 = 2k + 1, so that n + 1 is odd. This shows that (i) implies (ii).
Next, suppose that n + 1 is odd, so that n + 1 = 2k + 1 for some integer
k. Then 3n + 1 = 2n + (n + 1) = 2(n + k) + 1, which shows that 3n + 1 is
odd, showing that (ii) implies (iii). Next, suppose that 3n + 1 is odd, so
that 3n + 1 = 2k + 1 for some integer k. Then 3n = (2k + 1) − 1 = 2k,
so that 3n is even. This shows that (iii) implies (iv). Finally, suppose
that n is not even. Then n is odd, so n = 2k + 1 for some integer k.
Then 3n = 3(2k + 1) = 6k + 3 = 2(3k + 1) + 1, so that 3n is odd. This
completes an indirect proof that (iv) implies (i).
27. The integers 3, 5, and 7 are three primes of the desired form.
Direct Proof
71
72 Proof Methods
a proof, assume that p is true and use rules of inference and theorems
already proved to show that q must also be true.
Example 1
Give a direct proof of the theorem “If n is odd, then n2 is odd.”
Solution
Example 2
Give an indirect proof of the theorem “If 3n + 2 is odd, then n is odd”
Solution
q: n is odd.
For this assume that the conclusion of this implication is false; namely,
assume that n is even. Then n = 2k for some integer k. It follows that
3n + 2 = 3(2k) + 2 = 6k + 2 =2(3k + 1), so 3n + 2 is even (Since it is
Proof Methods 73
Vacuous Proof
Example 3
Show that the proposition P (0) is true where P (n) is the propositional
function “If n > 1 then n2 > n.”
Solution
Note that the proposition P (0) is the implication “If 0 > 1, then
2
0 > 0.” Since the hypothesis 0 > 1 is false, the implication P (0) is
automatically true.
Remark
The fact that the conclusion of this implication, 02 > 0, is false is irrel-
evant to the truth-value of the implication, because an implication with
a false hypothesis is guaranteed to be true.
Trivial Proof
Example 4
Let P (n) be the proposition “If a and b are positive integers with a ≥ b,
then an ≥ bn .” Show that the proposition P (0) is true.
Solution
Contradiction Method
Example 5
√
Prove that 2 is irrational by giving a proof by contradiction.
Solution
√
Let p be the proposition “ 2 is irrational.” Suppose that ¬p is true.
√
Then 2is rational. We will show that this leads to a contradiction.
√
Under the assumption that 2 is rational, there exists integers a and
√
b with 2 = a/b, where a and b have no common factors (So that the
√
fraction a/b is in lowest terms). Since 2 = a/b, when both sides of this
Proof Methods 75
2 = a2 /b2
Hence, 2b2 = a2
This means that a2 is even, implying that a is even (See Example 19).
Furthermore, since a is even, a = 2c for some integer c. Thus
2b2 = 4c2 ,
so b2 = 2c2 .
Example 6
Give a proof by contradiction of the theorem “if n2 is even, then n is
even.”
Solution
q: n is even
Example 7
Give a proof by contradiction of the theorem “if 3n+2 is odd, then n is
odd.”
Solution
Proof by Cases
Proof Methods 77
(p1 ∨ p2 ∨ . . . ∨ pn ) → q
the tautology
can be used as a rule of inference. This shows that the original impli-
cation with a hypothesis made up of a disjunction of the propositions
p1 , p2 , . . . , pn can be proved by proving each of the n implications
pi → q, i = 1, 2, . . . , n, individually. Such an argument is called a
proof by cases. Sometimes to prove that an implication p → q is true,
it is convenient to use a disjunction p1 ∨ p2 ∨ ... ∨ pn instead of p as
the hypothesis of the implication, where p and p1 ∨ p2 ∨ ... ∨ pn are
equivalent.
Example 8
Prove the implication “If n is an integer not divisible by 3, then n2 ≡
1(mod3).”
Solution
n2 = 9k 2 + 6k + 1 = 3(3k 2 + 2k) + 1.
n2 = 9k 2 + 12k + 4 = 3(3k 2 + 4k + 1) + 1.
Since it has been shown that both p1 → q and p2 → q are true, it can
be concluded that (p1 ∨ p2 ) → q is true. Moreover, since p is equivalent
to p1 ∨ p2 , it follows that p → q is true.
can be used. That is, the proposition “p if and only if q,” can be proved
if both the implications “if p, then q” and “if q, then p” are proved.
Example 9
Prove the theorem “The integer n is odd if and only if n2 is odd”.
Solution
The theorem has the form “p if and only if q,” where p is “ n is odd”
and q is “n2 is odd”. To prove this theorem, we need to show that p → q
and q → p are true.
Proof Methods 79
p1 ↔ p2 ↔ ... ↔ pn .
which states that all n propositions have the same truth-values. One
way to prove these mutually equivalent is to use the tautology
Example 10
Prove that when n is an integer, the following three statements are
equivalent.
p1 : n mod 3 = 1 or n mod 3 = 2
80 Proof Methods
p2 : n is not divisible by 3
p3 : n2 ≡ 1(mod3)
Solution
To show that the statements are equivalent, we can prove that the
implications p1 → p2 , p2 → p3 and p3 → p1 are true.
Existence Proof
Proof Methods 81
Solution
Let x = (n + 1)! + 1
x + 1, x + 2, . . . , x + n.
Remark
Note that in the solution above, a number x such x + i is composite for
i = 1, 2, . . . , n has been produced. Hence, this is an example of a
constructive existence proof.
Solution
Remark
The argument in the above example is a non-constructive existence proof
because a prime larger than n has not been produced. It has simply been
shown that one must exist.
Proof Methods 83
Counter Examples
Suppose a statement of the form ∀xP (x) is false. How can we show this?
Recall that the propositions ¬∀xP (x) and ∃x¬P (x) are equivalent. This
means that if we find an element a such that P (a) is false, then we have
shown that ∃x¬P (x) is true, which means that ∀xP (x) is false. An
element a for which P (a) is false is called a counterexample.
Example 13
Show that the assertion “All primes are odd” is false.
Solution
Attention!
It is a common mistake to assume that one or more examples establish
the truth of a statement. No matter how many examples there are where
P (x) is true; the universal quantification ∀xP (x) may still be false. An
illustration is given in the following example.
Example 14
Is n2 − n + 41 prime for all non-negative integers n? That is, “is the
statement ∀nP (n) a theorem,” where P (n) is the statement “n2 − n + 41
84 Proof Methods
Solution
Remark
The above examples illustrate the crucial point that a statement may
not be true, even though there are many examples for which it is true.
Exercises
d) If it snows today, the university will close. The university is not closed
today. Therefore, it did not snow today.
e) If I go swimming, then I will stay in the sun too long. If I stay in the
sun too long, then I will sunburn. Therefore, if I go swimming, then I
will sun burn.
Proof Methods 85
a) “If I take the day off, it either rains or snows.” “I took Tuesday off
or I took Thursday off”. It was sunny on Tuesday.” It did not snow on
Thursday.”
b) “If I eat spicy foods, then I have strange dreams.” “I have strange
dreams if there is thunder while I sleep.” “I did not have strange
dreams.”
f) “All rodents gnaw their food.” “Mice are rodent.” “Rabbits do not
gnaw their food.” “ Bats are no rodents.”
11. Prove that the sum of an irrational number and a rational number
is irrational using a proof by contradiction.
15. Prove that if x and y are real numbers, then max(x, y) + min(x, y) =
x + y (Hint: Use a proof by cases with the two cases corresponding to
x ≥ y and x < y, respectively.)
16. Prove that if x and y are real numbers then |x|+|y| ≥ |x + y| (where
|x| represents the absolute value of x if x ≥ 0 and equal −x if x ≤ 0).
min(a, min(b, c)) = min(min(a, b), c) whenever a, b and c are real num-
bers.
21. Prove or disprove that every positive integer can be written as the
sum of the squares of two integers.
22. We define the floor and ceiling functions on the set of real numbers,
respectively, as below: For real number x,
That is, bxc , called the floor of x, denotes the greatest integer that does
not exceed x and dxe , called the ceiling of x, denotes the least integer
that does not exceed x.
Prove or disprove each of the following statements about the floor and
ceiling functions.
e) x2 = x+1
2 for all real numbers x.
27. Prove or disprove that the there are three consecutive odd positive
integers that there are primes, that is, odd primes of the form p, p+2,
and p+4
29. Prove that there are infinitely many primes congruent to 3 modulo 4.
Is your proof constructive or nonconstructive? (Hint: One approach is to
assume that there are only finitely many such primes p1 , p2 , . . . , pn .
Let q = 4p1 p2 . . . pn + 3. Show that q must have a prime factor congru-
90 Proof Methods
31. Prove that there are irrational numbers a and b such that ab is
rational. Is your proof constructive or non-constructive? [Hint: Let
√ √
a = 2 and b = 2. Show that either ab or (ab )b is rational].
32. Prove that it is impossible to cover completely with dominos the 8×8
chessboard with two squares at opposite corners of the board removed.
Answers
1. a) Addition b) Simplification
e) Hypothetical syllogism
2. Let w be “Asok works hard,” let d be “Asok is a dull boy”, and let j
be “Asok will get the job.” The hypotheses are w, w → d, and d → ¬ j.
Using modus ponens and the first two hypotheses, d follows. Using
modus ponens and the last hypothesis, which is the desired conclusion,
¬ j: “Asok will not get the job”, follows.
4. a) Valid conclusions are “I did not take Tuesday off,” “I took Thursday
off,” “It rained on Thursday.”
b) “I did not eat spicy foods and it did not thunder” is a valid con-
clusion.
Proof Methods 91
e) “That you buy lots of stuff is good for the U.S. and is good for
you” is a valid conclusion.
f) “Mice gnaw their food” and “Rabbits are not rodents” are valid
conclusions.
Let a = 3m. Then 3b3 = 27m3 , or b3 = 9m3 . Thus 3|b3 , which shows
that 3|b. This is a contradiction of the assumption that gcd(a, b) = 1.
16. There are four cases. Case 1 : x ≥ 0 and y ≥ 0. Then |x| + |y| =
x + y = |x + y|. Case 2 : x < 0 and y < 0. Then x| + |y| = −x + (−y)
= −(x + y) = |x + y| since x + y < 0. Case 3 : x ≥ 0 and y < 0. Then
|x| + |y| = x + (−y). If x ≥ −y, then |x + y| = x + y. But since y < 0,
−y > y, so that |x| + |y| = x + (−y) > x + y = |x + y|. If x < −y, then
|x + y| = −(x + y) = −x + (−y). But since x ≥ 0, x ≥ −x, so that
|x| + |y| = x + (−y) ≥ −x + (−y) = |x + y|. Case 4 : x < 0 and y ≥ 0.
Identical to Case 3 with the roles of x and y reversed.
17. There are three cases to consider : Case 1, a is smallest, or tied for
smallest; Case 2, b is smallest, or tied for smallest; Case 3, c is smallest, or
tied for smallest. Since one of a, b, and c is smallest, or tied for smallest,
these three cases cover all possibilities. In Case 1, a ≤ min(b, c), so the
94 Proof Methods
left-hand side is a and the right hand side is also a since min (a, c) = a.
The argument in the other two cases is similar.
18. First, assume that n is odd, so that n = 2ki + 1 for some integer k.
Then 5n + 6 = 5(2k + 1) + 6 = 10k + 11 = 2(5k + 5) + 1. Hence 5n + 6
is odd. To prove the converse, suppose that n is even, so that n = 2k
for some integer k. Then 5n + 6 = 10k + 6 = 2(5k + 3), so that 5n + 6
is even. Hence n is odd if and only if 5n + 6 is odd.
20. This proposition is true. Suppose that m is neither 1 nor −1. Then
mn has a factor m larger than 1. On the other hand, mn = 1, and 1 has
no such factor. Hence m = 1 orm = −1. In the first case n = 1, and in
1
the second case n = −1, sincen = m.
21. The positive integer 3 is not the sum of two squares of integers, so
that the proposition is false.
1
e) False; x = 2 is a counter example.
23. a) If x is positive integer, then the two side are equal. So suppose
thatx = n2 + m + ε, where n2 is the largest perfect square less than x, m
√ p √
is a nonnegative integer, and 0 < ε ≤ 1. Then x and bxc = n2 + m
are between n and n + 1, so both sides equal n.
26. We will show that the four statements are equivalent by showing
that (i) implies (ii), (ii) implies (iii), (iii) implies (iv), and (iv) implies
(i). First, assume that n is even. Then n = 2k for some integerk. Then
n + 1 = 2k + 1, so that n + 1 is odd. This shows that (i) implies (ii).
Next, suppose that n + 1 is odd, so that n + 1 = 2k + 1for some integer
k. Then 3n + 1 = 2n + (n + 1) = 2(n + k) + 1, which shows that 3n + 1 is
odd, showing that (ii) implies (iii). Next, suppose that 3n + 1 is odd, so
96 Proof Methods
27. The integers 3, 5, and 7 are three primes of the desired form.
32. Every domino placed on a chessboard covers exactly one white and
one black square. Hence a set of dominos covers exactly the same number
of white squares and black squares. Since removing opposite corners
leaves a board with 2 more black squares than white squares or 2 more
white squares than black squares, no set of dominos can cover the board
with opposite corners removed.
Chapter 6
Mathematical Induction
Introduction
Well-Ordering Property of N:
If S is a subset of N and if S 6= Φ, then there exist m ∈ S such that
m ≤ k for all k ∈ S.
97
98 Mathematical Induction
Example 1
Prove that there is no positive integer between 0 and 1.
Solution
Example 2
Prove that every nonempty set of nonnegative integers has a least ele-
ment.
Solution
Case 2 Suppose 0 ∈
/ S. Then S contains only positive integers. So, by
the well-ordering principle, S contains a least element.
1) The number 1 ∈ S.
Then we have S = N.
Example 3
Prove that for each n ∈ N, the sum of the first n natural numbers is
100 Mathematical Induction
given by
1
1 + 2 + ··· + n = n(n + 1).
2
Solution
To prove the formula, we let S be the set of all n ∈ N for which the
formula is true.
1
1 + 2 + ... + k = k(k + 1).
2
1
1 + 2 + ... + k + (k + 1) = k(k + 1) + (k + 1)
2
1
= (k + 1)(k + 2).
2
Since this is the stated formula for n = k +1, we conclude that k +1 ∈ S.
Therefore, condition (2) is satisfied. Consequently, by the Principle of
Mathematical Induction, we infer that S = N, so the formula holds for
all n ∈ N.
Attention!
Careless use of the Principle of Mathematical Induction can lead to ob-
Mathematical Induction 101
“Proof (!!!)”. Let S be the subset of N for which the claim is true.
Evidently, 1 ∈ S “since” if p, q ∈ N and their maximum is 1, then both
equal 1 and so p = q. Now assume that k ∈ S and that the maximum of
p and q is k + 1. Then the maximum of p − 1 and q − 1 is k. But since
k ∈ S, then p − 1 = q − 1 and therefore p = q. Thus, k + 1 ∈ S, and we
conclude that the assertion is true for all n ∈ N.
1) P (1) is true
Remarks
2. The assumption that “P (k) is true” [in the first part of condition
102 Mathematical Induction
Example 4
For each n ∈ N, the sum of the squares of the n natural numbers is given
by
1
12 + 22 + · · · + n2 = n(n + 1)(2n + 1).
6
Prove this.
Solution
1
12 + 22 + · · · + k 2 = k(k + 1)(2k + 1).
6
1
12 + 22 + · · · + k 2 + (k + 1)2 = k(k + 1)(2k + 1) + (k + 1)2
6
1
= (k + 1)(2k 2 + k + 6k + 6)
6
1
= (k + 1)(k + 2)(2k + 3).
6
Consequently, P (k + 1) is true. Hence by the Principle of Mathematical
Induction, P (n) is true for all n ∈ N. i.e., the formula is valid for all
n ∈ N.
Example 5
Given two real numbers a and b, prove that a − b is a factor of an − bn
for all n ∈ N.
Mathematical Induction 103
Solution
= a(ak − bk ) + bk (a − b).
Remark/Special case:
A variety of divisibility results can be derived from the fact in Example
4. For example, since 11 − 7 = 4, we see that 11n − 7n is divisible by 4
for alln ∈ N.
Example 6
Establish the inequality
2n ≤ (n + 1)!
by Mathematical Induction.
Solution
2k ≤ (k + 1)!. Then
2k+1 = 2 · 2k
= (k + 2)!
Example 7
Prove the following formula for the sum of the terms in a “geometric
progression”.
1 − rn+1
1 + r + r2 + ... + rn =
1−r
Solution
Remark
The result in Example 5 can also be proved without using Mathematical
Induction. If we let Sn = 1+r+r2 +...+rn , then rSn = r+r2 +...+rn+1 ,
Mathematical Induction 105
so that
(1 − r)Sn = Sn − rSn = 1 − rn+1
Example 8 (An example showing that the Careless use of the Principle
of Mathematical Induction can lead to obviously absurd conclusions.)
You may read the following statement and its proof. Find the mistake
in the “proof”.
S = {n ∈ Z| P (n) is true }.
Now assume (2). i.e., assume that for all k ≥ n0 , P (k) is true. Then
n0 , n0 + 1, ..., k belong to S. So, by condition (2), k + 1 also belong to
S. Therefore, by Theorem 2, S contains all integers Thus, P (n) is true
for every integer n ≥ n0 .
The number n0 in (1), is called the base, which serves as the starting
point,) and the implication in (2), which can be written P (k) ⇒ P (k+1),
is called the bridge, since it connects the case k to the case (k + 1).
Example 9
Prove that 2n > 2n + 1 is true for n ∈ N and n = 3.
Mathematical Induction 107
Solution
= 2(k + 1) + 1.
i.e., we have shown that for all k ≥ 3, the truth of 2k > 2k + 1 implies
the truth of 2k+1 > 2(k + 1) + 1. Hence, with the base n0 = 3, we can
apply Mathematical Induction to conclude that the inequality holds for
all n ≥ 3.
Attention!
There are statements that are true for many natural numbers but that
are not true for all of them. For example, the formula p(n) = n2 − n + 41
gives a prime number for n = 1, 2, ..., 40. However, p(41) = 412 − 41 +
41 = 412 is divisible by 41, so it is not a prime number.
Exercises
1 1 1 n
1. Prove that 1·2 + 2·3 + ... + for all n ∈ N.
n(n+1) = n+1
2
1
2. Prove that 13 + 23 + ... + n3 = 2 n(n + 1) for all n ∈ N.
Pn h i2
3. Show that r=1 r3 = n(n+1) 2 for n ∈ N.
108 Mathematical Induction
1 1 1
+ + ··· + ,
1·3 3·5 (2n − 1) · (2n + 1)
14. Conjecture a formula for the sum of the first n odd natural numbers
1 + 3 + ... + (2n − 1), and prove your formula by using Mathematical
Induction.
20. Find all natural numbers n such that n2 − 2n . Prove your assertion.
22. Let S be a subset of N such that (a) 2k ∈ S for all k ∈ N, and (b) if
k ∈ S and k ≥ 2, then k − 1 ∈ S. Prove that S = N.
√ √ √ √
23. Prove that 1/ 1 + 1/ 2 + ... + 1/ n > n for all n ∈ N.
110
Recursion 111
Terminal Step: Only values thus obtained are valid functional values.
(Usually we drop this step from the recursive definition.)
Remark
Example 1
Show that recursion can be employed to find the minimum and maxi-
mum of three or more real numbers. Hence find min{5, −7, 4, −9} and
max{5, −7, 4, −9}.
Solution
Then
Similarly,
Hence
Also
Compute
Solution
Thus,
f (99) = f (100).
Thus,
f (100) = f (101)
Thus,
f (99) = f (100) = f (101) = 91.
Thus,
f (f (99)) = f (92).
Thus,
f (f (99)) = f (93).
f (f (99)) = f (99).
f (f (99)) = 91.
Factorial Function
n! = 1 · 2 · 3 . . . (n − 2)(n − 1)n.
5! = 1 · 2 · 3 · 4 · 5 = 120, 6! = 1 · 2 · 3 · 4 · 5 · 6 = 720
n! = n · (−1)!
(a) If n = 0, then n! = 1
f (4) = 4 · f (4 − 1) = 4 · f (3) = 4 · 3 · f (3 − 1)
= 4 · 3 · f (2) = 4 · 3 · 2 · f (2 − 1) = 4 · 3 · 2 · f (1)
116 Recursion
= 4 · 3 · 2 · 1f (1 − 1) = 4 · 3 · 2 · 1 · f (0) = 4 · 3 · 2 · 1 = 24.
|{z}
1
Example 3
A popular handshake problem is that there are n guests at a party.
Not being able to shake hands with oneself, and not counting multiple
handshakes with the same person, the problem is to find the number of
handshakes.
Solution
In particular,
h(1) = 0,
and so on.
Recursion 117
Step 1) apply the recurrence formula iteratively and look for a pattern
to predict an explicit formula;
Step 2) use induction to prove that the formula does indeed hold for
every possible value of the integer n. The following example illustrates
this method.
Example 4
Obtain an explicit formula corresponding to the recursive relation
Solution
= h(n − 2) + (n − 2) + (n − 1)
= h(n − 3) + (n − 3) + (n − 2) + (n − 1)
..
.
= h(1) + 1 + 2 + · · · + (n − 2) + (n − 1)
= 0 + 1 + 2 + · · · + (n − 2) + (n − 1)
n(n + 1)
1 + 2 + ··· + n = .
2
118 Recursion
n(n − 1)
h(n) = .
2
Exercises
In exercise 1-4, compute the first four terms of the sequence defined
recursively.
1. a1 = 1
an = an−1 + 3, n ≥ 2
2. a0 = 1
an = an−1 + n, n ≥ 1
3. a1 = 1
n
an = n−1 an−1 , n≥2
4. a1 = 1, a2 = 2
an = an−1 + an−2 , n ≥ 3
7. 0, 3, 9, 21, 45,. . .
Answers
1.a2 = 4, a3 = 7, a4 = 10
2.a1 = 2, a2 = 4, a3 = 7
3.a2 = 2, a3 = 3, a4 = 4
4.a3 = 3, a4 = 5
5.a1 = 1, an = an−1 + 3, n ≥ 2
6.a1 = 3, an = an−1 + 5, n ≥ 2
7.a1 = 0, an = 2an−1 + 3, n ≥ 2
Chapter 8
Division Algorithm
a = qb + r 0 ≤ r < b.
The integers q and r are called, respectively, the quotient and remain-
der in the division of a by b.
S = {a − xb| x an integer, a − xb ≥ 0}
120
Division Algorithm 121
so
a − (−|a|)b = a + |a|b ≥ a + |a| ≥ 0.
r = a − qb ( 0 ≤ r )
We argue that r < b. If this were not the case, then r ≥ band
a − (q + 1)b = (a − qb) − b = r − b ≥ 0
The implication is that the integer a − (q + 1)b has the proper form
to belong to the set S. But a − (q + 1)b = r − b < r, leading to a
contradiction of the choice of r as the smallest member of S. Hence,
r < b.
a = qb + r = q 0 b + r0 . . . (1)
Then
r0 − r = b(q − q 0 )
and
−b < −r ≤ 0 . . . (4)
−b < r0 − r < b
That is,
|r0 − r| < b.
which gives
0 ≤ |q − q 0 | < 1.
|q − q 0 | = 0.
Hence q = q 0 .
r = r0 .
Example 1
Division Algorithm 123
2. −123 is divided by 5.
Solution
1. 107 = 8 · 13 + 3; so q = 8 and r = 3.
2. Though
−123 = (−24) · 5 + (−3)
is true, this is not the equation we search for in the form of Division
Algorithm. In the Division Algorithm, the remainder can never be neg-
ative.
Remark
a = qb + r 0 ≤ r < b.
124 Division Algorithm
Therefore,
r = amodb = a − bq = a − b · ba/bc .
Card dealing
Example 2
As an application of both div and mod operators, let us consider a
standard deck of 52 playing cards. They are originally assigned the
numbers 0 through 51 in order. Use the suit labels 0 = clubs, 1 =
diamonds, 2 = hearts, and 3 = spades to identify each suit, and the card
labels 0 = ace, 1 = deuce, 2 = three, . . . , and 12 = king to identify
the cards in each suit. Suppose card x is drawn at random from a well-
shuffled deck, where 0 ≤ x ≤ 51. How do we identify the card?
Solution
Solution
Column label 0 1 2 3 4 5 6 7
→
Row label ↓
0 0 1 2 3 4 5 6 7
1 8 9 10 11 12 13 14 15
2 16 17 18 19 20 21 22 23
3 24 25 26 27 28 29 30 31
4 32 33 34 35 36 37 38 39
5 40 41 42 43 44 45 46 47
6 48 49 50 51 52 53 54 55
7 56 57 58 59 60 61 62 63
Because the squares are labelled 0 through 63, we can label each row
with the numbers 0 through 7 and each column with the same numbers
0 through 7. Clearly, each row label = br/8cand each column label =
c mod 8, where 0 ≤ r, c ≤ 63. Thus, the queen in square x lies in row
bx/8c and column x mod 8, and that in square y lies in row by/8cand
column y mod 8. Hence we have the following:
1. The two queens will be in the same row if and only if bx/8c =
by/8c, and
2. The two queens will be in the same column if and only if xmod8
= ymod8.
126 Division Algorithm
Now we determine when they lie on the same diagonal? There are 15
northeast diagonals and 15 southeast diagonals.
But if x = 24, y = 13, then one queen cannot capture the other, because
Proof
We prove this by the method of contradiction. Let there be m pigeons
and n pigeonholes where m > n. Assume that no two pigeons occupy
the same pigeonhole. In this case, every pigeon must occupy a distinct
pigeonhole, so n ≥ m, which is a contradiction to the above condition.
Thus, two or more pigeons must occupy same pigeonhole
Divisibility
a = qb + 0 = qb.
Solution
x − y = (bq1 + r) − (bq2 + r)
= b(q1 − q2 )
Thus, x − y is divisible by b.
Theorem 3
Let a and b positive integers such that a|b and b|a. Then a = b.
Proof
a|b and b|a. implies there are integers q1 and q2 such that
b = q1 a and a = q2 b.
a = q2 (q1 a)
1 = q2 q1 .
a = b.
Theorem 4
Let a, b, c, α, and β be any integers. Then
Division Algorithm 129
Remark
Condition 2 in theorem 4 says that if a is a factor of b and c, then a is
also a factor of any linear combination of b and c.
Notation
Let x be a positive real number. The number of positive integers ≤ x is
denoted by bxc . For example, if x = 10.65 then bxc = b10.65c = 10.
Theorem 5
Let a and b be any positive integers. Then the number of positive
integers ≤ a and divisible by b is ba/bc .
Proof
Suppose there are kpositive integers ≤ a and divisible by b. We need to
show that k = ba/bc . The positive multiples of b less than or equal to a
are b, 2b, · · · , kb. Clearly, kb ≤ a, that is, k ≤ a/b. Further, (k+1)b > a.
Thus, k + 1 > a/b or a/b − 1 < k. Therefore,
a a
−1<k ≤
b b
Let A be a finite set and |A| the number of elements in A. For example,
if A = {12, 13, 24, 100, 108}, then |A| = 5.
Definition
Let A and B be sets. The union of the sets A and B, denoted byA ∪ B,
is the set that contains those elements that are either in A or in B, or in
both. That is,
A ∪ B = {x|x ∈ A or x ∈ B}
A ∪ B = {x|x ∈ A ∨ x ∈ B}
Definition
Let A and B be sets. The intersection of the sets A and B, denoted by
A ∩ B, is the set containing those elements in both A and B. That is,
A ∩ B = {x|x ∈ A ∧ x ∈ B}.
Once the universal set U has been specified, the complement of a set can
be defined as follows:
Definition
Division Algorithm 131
A0 = {x : x ∈ U, x ∈
/ A}.
n
[ X X \
Ai = |Ai | − Ai Aj
i=1 1≤i≤n 1≤i≤j≤n
X \ \ n
\
+ Ai Aj Ak − · · · + (−1)n+1 Ai
1≤i<j<k≤n i=1
Proof
We first prove this result for two sets.
Likewise,
|A ∩ B ∩ C|.
Mathematical Induction.
Example 4
Find the number of positive integers ≤ 2076 and divisible by neither 4
nor 5.
Solution
Then
|A ∪ B| = |A| + |B| − |A ∩ B|
Thus, among the first 2076 positive integers, there are 2076−831 = 1245
integers not divisible by 4 or 5.
a = qb + r (0 ≤ r < b).
Then we get
a = 2q + r, where 0 ≤ r < 2.
It follows from this definition that every integer is either even or odd,
but not both.
Properties
Exercises
Find the quotient and the remainder when the first integer is divided by
the second.
1.68, 132.357, 753. − 128, 134. − 73, 35
7. Prove that the sum of an even integer and an odd integer is odd.
9. Prove that the sum of any two integers of the form 4k + 1 is even.
134 Division Algorithm
11. n3 − n is divisible by 2.
n(n+1)(2n+1)
12. Forn ≥ 1,prove that 6 is an integer
13. (The Two Queens Puzzle) There are two queens on an 8 × 8 chess-
board. One can capture the other if they are on the same row, col-
umn, or diagonal. The 64 squares on the board are numbered 0 through
63. Suppose one queen is in square x and the other in square y, where
0 ≤ x, y ≤ 63. Can one queen capture the other?
15. Show that the number of leap years l after 1600 and not exceeding
a given year y is given by
12. By the Division Algorithm, n has one of the forms 6k,6k+1, . . . , 6k+
5;establish the result in each of these six cases.
14. 1629.
Chapter 9
Prime and Composite Numbers
Any integer a > 1 is divisible by the positive integers 1 and a ;if these
exhaust the positive divisors of a, then it is said to be a prime number.
Definition
A positive integer p > 1 is called a prime number or simply a prime,
if its only positive divisors are 1 and p. An integer greater than 1 that
is not a prime is termed composite.
Example 1
The first six primes are 2, 3, 5,7,11 and 13.
Lemma
Every integer n ≥ 2 has a prime factor.
Proof
135
136 Prime and Composite Numbers
Theorem 1 (Euclid)
There is an infinite number of primes.
Proof
The proof is by contradiction. Let p1 = 2, p2 = 3, p3 = 5, p4 = 7, . . .
be the primes in ascending order, and suppose that there is a last prime,
called pn . Now consider the positive integer
N = p1 p2 · · · pn + 1.
Theorem 2
√
Every composite number n has a prime factor ≤ b nc .
Proof
The Proof is by contradiction. Let n be a composite number. Then it
has factors other than 1. We choose two positive integers a and b such
√
that n = ab, where 1 < a < n and 1 < b < n. Suppose a > n and
√ √ √
b > n. Then n = ab > n · n = n,that is we get n > n which is
√ √
impossible. Therefore, either a ≤ n or b ≤ n. Since both a and b are
√ √
integers, it follows that either a ≤ b nc or b ≤ b nc .
Remark
Example 2
Determine whether 1601 is a prime number.
Solution
√ √
We have 1601 = 40. Therefore the primes which are ≤ 1601
are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37. Since none of them is a
factor of 1601 (verify), Hence by above theorem 1601 is a prime.
Sieve of Eratosthenes
√
“ If an integer a > 1 is not divisible by any prime p ≤ a, then a is
a prime.”
Example 3
Using Sieve of Eratosthenes find all primes not exceeding 100.
Solution
Taking the first prime 2, we begin by crossing out all even integers
from our listing, except 2 itself (See the Table below.)
Prime and Composite Numbers 139
2 3 \
4
/ 5 \
6
/ 7 \/8 9 1
Z
0
Z
11 1
Z
2
Z 13 \
14
/ 15 16
Z
Z 17 18
Z
Z 19 2
Z
0
Z
21 2
Z
2
Z 23 2
Z
4
Z 25 26
Z
Z 27 28
Z
Z 29 3
Z
0
Z
31 3
Z
2
Z 33 3
Z
4
Z 35 36
Z
Z 37 38
Z
Z 39 4
Z
0
Z
41 4
Z
2
Z 43 4
Z
4
Z 45 46
Z
Z 47 48
Z
Z 49 5
Z
0
Z
51 5
Z
2
Z 53 5
Z
4
Z 55 56
Z
Z 57 58
Z
Z 59 6
Z
0
Z
61 6
Z
2
Z 63 6
Z
4
Z 65 66
Z
Z 67 68
Z
Z 69 7
Z
0
Z
71 7Z
Z
2
73 7Z
Z
4
75 76
Z
Z 77 78
Z
Z 79 8Z
Z
0
81 8Z
Z
2
83 8Z
Z
4
85 86
Z
Z 87 88
Z
Z 89 9
Z
0
Z
91 9Z
Z
2
93 9Z
Z
4
95 96
Z
Z 97 98
Z
Z 99 100
H
H
The first of the remaining integers is 3, which must be a prime. We
keep 3, but strike all higher multiples of 3, so that 9, 15, 21, . . . are now
removed (the even multiples of 3 having been removed in the previous
step).
Now, the smallest integer after 3 that has not yet been deleted is 5.
It is not divisible by either 2 or 3 – otherwise it would have been crossed
out – hence, it is also a prime. All proper multiples of 5 being composite
numbers, we next remove 10, 15, 20, . . . (some of these are, of course,
already crossed out), while retaining 5 itself.
Now, the first surviving integer is 7 and is a prime, for it is not divis-
ible by 2, 3, or 5, the only primes that precede it. After eliminating the
√
proper multiples of 7, the largest prime less than 100 = 10, all com-
posite integers in the sequence 2, 3, 4, 5, . . . , 100 have fallen through
the sieve.
The positive integers that remain are 2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, are all of the
primes less than 100.
140 Prime and Composite Numbers
Example 4
Prove that there is no polynomial f (n) with integral coefficients that
will produce primes for all integers n.
Solution
A Number-Theoretic function
Theorem 3
√
Let p1 , p2 , · · · , pt be the primes ≤ n. Then
√ X n X n
π(n) = n − 1 + π( n) − +
i
pi i<j
pi pj
X n
n
t
− + · · · + (−1)
p i pj pk p1 p2 · · · p t
i<j<k
Example 5
Find the number of primes ≤ 100.
Solution
√ √
Here n = 100. Then π( n) = π( 100) = π(10) = 4. The four primes
≤ 10 are 2, 3, 5, and 7; call them p1 , p2 , p3 , and p4 , respectively. Then,
by Theorem 3,
100 100 100 100
π(100) = 100 − 1 + 4 − + + +
2 3 5 7
100 100 100 100 100 100
+ + + + + +
2·3 2·5 2·7 3·5 3·7 5·7
142 Prime and Composite Numbers
100 100 100 100 100
− + + + +
2·3·5 2·3·7 2·5·7 3·5·7 2·3·5·7
= 103 − (50 + 33 + 20 + 14) + 16 + 10 + 7 + 6 + 4 + 2)
−(3 + 2 + 1 + 0) + 0 = 25.
π(x)
lim =1
x→∞ x/ ln x
Theorem 4
For every positive integer n, there are n consecutive integers that are
composite numbers.
Proof
Consider the n consecutive integers (n + 1)! + 2,(n + 1)! + 3, . . . (n +
1)! + (n + 1), where n ≥ 1. Suppose 2 ≤ k ≤ n + 1, then k|(n + 1)!, so
k|[(n + 1)! + k], by Theorem 4 in chapter 1, for every k. Therefore, each
of them is a composite number.
Example 6
Find six consecutive integers that are composites.
Solution
Fibonacci Numbers
Prime and Composite Numbers 143
Suppose two newborn rabbits are placed in a fenced-in yard and left
to, well, breed like rabbits. Also suppose:
1. Rabbits can’t reproduce until they are at least one month old, so
for the first month, only one pair remains.
2. At the end of the second month, the female gives birth, leaving
two pairs of rabbits. When month three rolls around, the orig-
inal pair of rabbits produce yet another pair of newborns while
their earlier offspring grow to adulthood. This leaves three pairs of
rabbit, two of which will give birth to two more pairs the follow-
ing month. The order goes as follows (under another assumption
that rabbits under consideration never die): 1, 1, 2, 3, 5, 8, 13,
21, 34, 55, 89, 144, . . . . Each number from third position is the
sum of the previous two. This sequence of numbers is known as
the Fibonacci numbers or the Fibonacci sequence. The ratio
between the numbers (1.618034) is frequently called the golden
ratio or golden number.
F1 = 1, F2 = 1 [initial conditions]
Using the recursive definition, we can list the first few terms of the
Fibonacci sequence as:
Theorem 5(Lucas)
b(n−1)/2c
!
X n−i−1
Fn = , n≥1
i=0 i
Lucas Numbers
The numbers 1, 3, 4, 7, 11, ... , are called the Lucas numbers They
Prime and Composite Numbers 145
L1 = 1, L2 = 3
Binet’s formulas
where
√ . √ .
α = (1 + 5 ) 2β = (1 − 5 ) 2
Fermat numbers
n
Numbers of the form fn = 22 + 1are called Fermat numbers, due to the
French mathematician Pierre de Fermat. The first five Fermat numbers
are
Theorem 7
Letfn denote the nth Fermat number. Then fn = fn−1
2
− 2fn−1 + 2,
where n ≥ 1.
Proof
2
We shall substitute for fn−1 in the expression fn−1 − 2fn−1 + 2, simplify
it, and show that it equals fn :
n−1 n−1
2
fn−1 − 2fn−1 + 2 = (22 + 1)2 − 2(22 + 1) + 2
146 Prime and Composite Numbers
n n−1 n−1
= (22 + 2.22 + 1) − 2.22 −2+2
n
= 22 + 1
= fn
A Recursive Definition of fn ,
ie, f0 = 3
f1 = f02 − 2f0 + 2 = 9 − 2 · 3 + 2 = 5
and
f2 = f12 − 2f1 + 2 = 25 − 2 · 5 + 2 = 17
Example 7
Show that 641|f5 .
Solution
641 = 5 · 27 + 1 . . . (1)
5
So 22 + 1 = 232 + 1 = 24 · 228 + 1
Thus, 641|f5 .
Theorem 8
Every prime factor of fn is of the form k · 2n+2 + 1, where n ≥ 2.
Example 8
Show that f4 = 65537 is prime.
Solution
Exercises
5. Find the consecutive integers < 100 that are composite numbers.
6. 2 and 3 are the only two consecutive integers that are primes.
Definition
If a and b are arbitrary integers, then an integer d is said to be a
common divisor of a and b if both d|a and d|b.
Remarks
149
150 The Greatest Common Divisor
The greatest common divisor (gcd) of two integers a and b, not both
zero is the largest positive integer that divides both a and b; it is denoted
by (a, b).
Definition
Let a and b be given integers, with at least one of them different from
zero. The greatest common divisor of a and b, denoted by (a, b), is the
positive integer d satisfying the following:
Example 1
The positive divisors of −12 are 1, 2, 3, 4, 6, 12, whereas those of 30
are 1, 2, 3, 5, 6, 10, 15, 30. Hence, the positive common divisors of −12
and 30 are 1, 2, 3, 6. Because 6 is the largest of these integers, it follows
that (−12, 30) = 6. In the same way, we can show that
Definition
Two integers a and b, not both of which are zero, are said to be
relatively prime whenever(a, b) = 1.
For example, 6 and 11 are relatively prime. Also 12 and 25 are relatively
prime.
The Greatest Common Divisor 151
Theorem 1
Any two consecutive Fibonacci numbers are relatively prime.
Proof
Proof of the Theorem is by the method of contradiction. Let Fn and
Fn+1 be two consecutive Fibonacci numbers and let p be a prime factor
of both Fn and Fn+1 . Then, p| ± 1, which is a contradiction. Thus,
(Fn+1 , Fn ) = 1. This completes the proof.
Lemma
Let fi denote the i th Fermat number. Then
where n ≥ 1.
Proof
n
We have numbers of the form fn = 22 + 1 are called Fermat numbers.
f0 f1 · · · fk−1 = fk − 2
Then
f0 f1 · · · fk−1 fk = (f0 f1 · · · fk−1 )fk
k k
= (22 − 1)(22 + 1)
k+1 k+1
= 22 − 1 = (22 + 1) − 2
152 The Greatest Common Divisor
= fk+1 − 2
Theorem 2 (Polya)
Let m and n be distinct nonnegative integers. Then fm and fn are
relatively prime.
Proof
Assume, for convenience, that m < n. Let d = (fm , fn ). Then d|fm and
d|fn . But fn − 2 = f0 f1 · · · fm · · · fn−1 .
Since d|fm , d|f0 f1 · · · fm. · · · fn . So d|(fn − 2), but d|fn ; therefore, d|2, by
Theorem 4 in chapter 8. Consequently, d must be 1 or 2. But Fermat
numbers are all odd, so d 6= 2. Therefore, d = 1; that is, (fm , fn ) = 1.
Theorem 3
There is an infinitude of primes.
Proof
We have every Fermat number has a prime factor. Therefore, by Polya’s
theorem, not two distinct Fermat numbers have common prime factors,
meaning each has a distinct prime factor. So, since there are infinitely
many Fermat numbers, there are also infinitely many primes.
Theorem 4
Let (a, b) = d. Then
1.(a, a − b) = d.
2.(a/d, b/d) = 1
Proof
and d0 ≤ d.
To show that d ≤ d0 :
To show that d0 ≤ d :
Since d0 is a common factor of a and a−b, a = αd0 and a−b = βd0 for
some integers α and β. Then a−(a−b) = αd0 −βd0 ; that is, b = (α−β)d0 .
Thus, d0 is a common divisor of a and b, so d0 ≤ d.
d = ax + by.
a b a
Because d and d are integers, by Theorem 3, we can conclude that d
b
and d are relatively prime.
154 The Greatest Common Divisor
Linear Combinations
The next theorem indicates that the gcd (a, b) can be represented as
linear combination of a and b. This is illustrated by, say,
or
(−8, 36) = 4 = (−8)4 + (−36)(−1)
Theorem 5 (Euler)
The gcd of the positive integers a and b is a linear combination of a and
b.
Proof
Consider the set S of all positive linear combinations of a and b:
a = am + b · 0
r = a − qd = a − q(αa + βb)
and so a = qd,
or equivalently d|a.
Corollary 1
If a and bare given integers, not both zero, then the set
d|(aα + bβ)
d = ax0 + by0
It may happen that 1 and −1 are the only common divisors of a given
pair of integers a and b, whence (a, b) = 1. For example:
Theorem 6
If d = (a, b) and d0 is any common divisor of a and b, then d0 |d.
Proof
Since d = (a, b), Theorem 5, there exist α and β such that d = αa + βb.
If d0 is any common divisor of aand b,then d0 |a and d0 |b, by Theorem 4
in Chapter 1, d0 |(αa + βb); so d0 |d.
Theorem 7
Let a, b, and c be any positive integers. Then (ac, bc) = c(a, b).
Proof
Proof is left as an exercise.
1 = αa + βb.
Proof
If a and b are relatively prime so that (a, b) = 1,then Theorem 5 guar-
antees the existence of integers α and βsatisfying
1 = αa + βb.
1 = αa + βb.
d = (a, b).
158 The Greatest Common Divisor
d|(αa + βb).
Hence d|1.
Corollary 2
If (a, b) = 1 = (a, c), then (a, bc) = 1.
Corollary 3
If a|c and b|c with (a, b) = 1, then ab|c.
Proof
As a|c and b|c, integers m and n can be found such that c = ma = nb.
Now the relations (a, b) = 1 allows us to write
1 = αa + βb
Hence ab|c.
Note that(6, 8) 6= 1.
Proof
Since(a, b) = 1, by Theorem 5 we can write
1 = αa + βb
Because a|ac and a|bc, it follows that a|(acα + bcβ), implies by Eq.
(1) that a|c.
Example 2
Find (12, 18, 28), (12, 36, 60, 108), and (15, 28, 50).
Solution
b) 12 is the largest factor of 12, and 12 is a factor of 12, 36, 60, and 108;
so (12, 36, 60, 108) = 12.
c) Since (15, 28) = 1, the largest common factor of 15, 28, and 50 is 1;
that is, (15, 28, 50) = 1.
160 The Greatest Common Divisor
Theorem 10
The gcd of the positive integers a1 , a2 , . . . , an is the least positive in-
teger that is a linear combination of a1 , a2 , . . . , an .
Example 3
Express (12, 15, 21) as a linear combination of 12, 15, and 21.
Solution
First, you may notice that (12, 15, 21) = 3. Next, find integers α, β,
and γ, by trial and error, such that α · 12 + β · 15 + γ · 21 = 3; α = −1,
β = 1, and γ = 0 is such a combination: (−1) · 12 + 1 · 15 + 0 · 21 = 3.
Theorem 11
Let a1 , a2 , . . . , an be n(≥ 3) positive integers. Then (a1 , a2 , . . . , an ) =
((a1 , a2 , . . . an−1 ), an )
Proof
Let d = (a1 , a2 , . . . , an ), d0 = (a1 , a2 , . . . , an−1 ), and d00 = (d0 , an ).
We will show that d = d00 :
Since d00 = (d0 , an ), d00 |d0 and d00 |an . But d00 |d0 implies d00 |ai for
1 ≤ i ≤ n − 1. Thus, d00 |ai for 1 ≤ i ≤ n, so d00 |d.
Example 4
Using recursion, evaluate (18, 30, 60, 75, 132)
Solution
(18, 30, 60, 75, 132) = ((18, 30, 60, 75), 132)
=3
Corollary 4
If d = (a1 , a2 , . . . , an ), then d|ai for every integer i, where 1 ≤ i ≤ n.
Corollary 5
If d|a 1 a2 . . . an and (d, ai ) = 1 for 1 ≤ i ≤ n − 1, then d|an .
For example, the integers 8, 15, and 49 are pairwise relatively prime,
whereas the integers 6, 25, 77, and 91 are not pairwise relatively prime.
Corollary 6
162 The Greatest Common Divisor
Corollary 7
There are infinitely many primes.
Proof
Suppose there is only a finite number of primes, p1 , p2 , . . . , pk . Consider
the Fibonacci numbers Fp1 , Fp2 , . . . , Fpk . Clearly, they are pairwise rel-
atively prime. Since there are only k primes, each of these Fibonacci
numbers has exactly one prime factor, that is, each is a prime. This is
a contradiction, since F19 = 4181 = 37 · 113. Thus, our assumption that
there are only finitely many primes is false. In other words, there are
infinitely many prime numbers.
Exercises
(a) a + b, a2 − b2
(b) a2 − b2 , a4 − b4 .
(a)15, 18, 24
8. Prove that the sum of the squares of two odd integers cannot be a
perfect square.
10. Establish that the differences of two consecutive cubes is never di-
visible by 2.
11. For a nonzero integera, show that(a, 0) = |a| , (a, a) = |a|, and(a, 1) =
1.
12. If a and b are integers, not both of which are zero, verify that
13. Prove that, for a positive integer n and any integer a, (a, a+n)divides
n; hence, (a, a + 1) = 1.
14. Given integers a and b, prove that there exist integers x and y for
which c = ax + by if and only if (a, b)|c
a) (2a + 1, 9a + 4) = 1.
b) (5a + 2, 7a + 3) = 1
164 The Greatest Common Divisor
18. If a and b are integers, not both of which are zero, prove that
(2a − 3b, 4a − 5b)divides b; hence, (2a + 3, 4a + 5) = 1.
a2 + (a + 2)2 + (a + 4)2 + 1
is divisible by 12.
(3n)!
20. Prove that the expression (3!)n is an integer for alln ≥ 0.
21. Prove that the product of any three consecutive integers is divisible
by 6.
22. Prove that the product of any four consecutive integers is divisible
by 24.
23. Prove that the product of any five consecutive integers is divisible
by 120.
(a, c) = (b, c) = 1.
f) If (a, b) = 1, then(a2 , b2 ) = 1.
31. Let tn denote the nth triangular number. For what values of n does
tn divide the sum t1 + t2 + · · · + tn ?
d|(a + b) − a, or d|b.
a = q 1 b + r1 0 ≤ r1 < b
166
Euclidean Algorithm 167
b = q 2 r1 + r2 0 ≤ r2 < r1
r 1 = q 3 r 2 + r3 0 ≤ r3 < r2
This division process continues until some zero remainder appears, say,
at the (n+1)th stage where rn−1 is divided by rn (a zero remainder occurs
sooner or later because the decreasing sequence b > r1 > r2 > · · · ≥ 0
cannot contain more that b integers).
Claim rn , the last nonzero remainder, is equal to(a, b). Proof of the
claim is based on the lemma below.
Lemma
Let a and b be two positive integers , and r the remainder, when a is
divided by b. Then (a, b) = (b, r).
Proof
If d = (a, b), then the relations d|a and d|b together imply that
168 Euclidean Algorithm
Using the result of the lemma, we simply work down the displayed
system (1) of equations, obtaining
as claimed.
rn = rn−2 − qn rn−1
Now solve the preceding equation in the algorithm for rn−1 and sub-
stitute to obtain
Example 1
Using Euclidean Algorithm calculate(12378, 3054). Also represent the
greatest common divisor as a linear combination of 12378 and 3054.
Solution
162 = 1 · 138 + 24
138 = 5 · 24 + 18
24 = 1 · 18 + 6
18 = 3 · 6 + 0.
Our previous discussion tells us that the last nonzero remainder ap-
pearing in these equations, namely, the integer 6, is the greatest common
divisor of 12378 and 3054:
6 = (12378, 3054).
6 = 24 − 18
= 24 − (138 − 5 · 24)
= 6 · 24 − 138
= 6 · 162 − 7 · 138
Thus, we have
Remark
Note that the above is not the only way to express the integer 6 as
a linear combination of 12378 and 3054; among other possibilities, we
could add and subtract 3054 · 12378 to get
Remark
The number of steps required in the Euclidean Algorithm is at most five
times the number of digits in the smallest integer.
rk
|rk+1 | < ,
2
3054 = 19 · 162 − 24
162 = 7 · 24 − 6
24 = (−4)(−6) + 0
As the last nonzero remainder is −6, the scheme produces “greatest com-
mon divisor” as −6. Hence the greatest common divisor is 6. (Note that
this scheme produces the negative of the value of the greatest common
divisor of two integers.)
Example 2
Using the Euclidean algorithm, express (4076, 1024) as a linear combi-
nation of 4076 and 1024.
Solution
reverse order, each time substituting for the remainder from the previous
equation:
= 1004 − 50 · 20
= 51 · 1004 − 50 · 1024
A Jigsaw Puzzle
15 = 1 · 9 + 6
Euclidean Algorithm 173
9=1·6+3
6=2·3
Lamé’s Theorem
The number of divisions needed to compute (a, b) by the euclidean al-
gorithm is no more than five times the number of decimal digits in b,
where a ≥ b ≥ 2.
Exercises
Using the Euclidean algorithm, find the gcd of the given integers.
7. Let a and b be any two positive integers, and let r be the remainder
when a is divided by b. Let d = (a, b)and d0 = (b, r). Prove that d0 |d.
8. Let a and b be any two positive integers with a ≥ b. Using the sequence
of equations in the Euclidean algorithm, prove that (a, b) = (rn−1 , rn ),
where n ≥ 1.
Answers
1. 8 3. 4 4. 8 6. 4
174 Euclidean Algorithm
Definition
An integer c is said to be a common multiple of two nonzero integers
a and b whenever a|c and b|c.
Examples
Theorem 1 (Euclid)
If p is a prime and p|ab, then p|a or p|b.
175
176 The Fundamental Theorem of Arithmetic
Proof
If p|a, there is nothing to prove. So let us assume that p - a. Then we
have to show that p|b. Because the only positive divisors of p are 1 and p
itself, this implies that (p, a) = 1. i.e., we have now p|ab and (p, a) = 1,
this using Euclid’s lemma, implies p|b . This completes the proof.
Corollary 1
If p is a prime and p|a1 a2 · · · an , then p|ai for some i, where 1 ≤ i ≤ n.
Proof
We proceed by induction on n, the number of factors. When n = 1, the
stated conclusion obviously holds; whereas when n = 2, the result is the
content of Theorem 1.
a1 , a2 , . . . , an .
Corollary 2
If p, q1 , q2 , . . . , qn are all primes and p|q1 q2 . . . qn , then p = qi for
some i, where 1 ≤ i ≤ n.
Proof
By the help of Corollary 1 we know that p|qi for some i, with1 ≤ i ≤ n.
The Fundamental Theorem of Arithmetic 177
Proof
Either n is a prime or it is composite. If n is a prime, there is nothing
more to prove. If n is composite, then there exists an integer d satisfying
d|n and 1 < d < n. Among all such integers d, choose p1 to be the
smallest (this is possible by the Well-Ordering Principle). Then p1 must
be a prime number. Otherwise it too would have a divisor q with 1 <
q < p1 ; but then q|p1 and p1 |n imply that q|n, which contradicts the
choice of p1 as the smallest positive divisor, not equal to 1, of n.
n = p 1 p 2 · · · pk .
n = p1 p2 · · · pr = q1 q2 · · · qs wherer ≤ s
p1 ≤ p2 ≤ · · · ≤ pr and q1 ≤ q2 ≤ · · · ≤ qs .
p 2 p 3 · · · pr = q 2 q 3 · · · q s .
p3 p4 · · · p r = q 3 q 4 · · · q s
Hence, r = s and
p1 = q1 and p2 = q2 , . . . , pr = qr
Remark
By the above theorem every composite number n can be factored into
primes. Such a factorization is called a prime factorization of n.
Canonical Decomposition
There are two different techniques for finding the canonical decomposi-
tion. We illustrates this by the following examples.
Example 1
Find the canonical decomposition of 2520.
Solution
180 The Fundamental Theorem of Arithmetic
Beginning with the smallest prime 2, since 2|2520, 2520 = 2 · 1260. Now
2 is a factor of 1260, so 2520 = 2·2·630; 2|630 again, so 2520 = 2·2·2·315.
Now 2 - 315, but 3 does, so 2520 = 2 · 2 · 2 · 3 · 105; 3 is a factor of 105
also, so 2520 = 2 · 2 · 2 · 3 · 3 · 35. Continuing like this we get
2520 = 2 · 2 · 2 · 3 · 3 · 5 · 7 = 23 · 32 · 5 · 7
Example 2
Find the canonical decomposition of 2520, by Method 2.
Solution
Notice that 2520 = 40 · 63. Since none of the factors are primes, split
them again: 40 = 4 · 10 and 63 = 7 · 9, so 2520 = (4 · 10) · (7 · 9). Since 4,
10, and 9 are composites, split each of them: 2520 = (2 · 2)(2 · 5)(7)(3 · 3).
Now all the factors are primes, so the procedure stops. Rearranging
them yields the canonical decomposition: 2520 = 23 · 32 · 5 · 7.
It can be seen that 9!=362,880 has one trailing zero, while 11!=39,916,800
has two trailing zeros. We now apply the fundamental theorem of arith-
metic and the floor function to determine the number of trailing zeros
in the decimal value of n!, without computing it.
Example 3
Find the number of trailing zeros in 112!.
The Fundamental Theorem of Arithmetic 181
Solution
112! = 2a 5b c,
where a and b are positive integers and c denotes the product of primes
other than 2 and 5 (Note: Here c is not a prime, but a product of prime
factors of 112! other than 2 and 5). We note that 112! is the product
of positive integers from 1 to 112; among those integers, multiples of 2
up to 112 and multiplies of 5 up to 112 are included. It can be seen
that number of multiples of 2 are greater than number of multiples of
5. Hence while factorizing by prime number, 112 has more 2s than 5s.
Hence a > b.
= b112/5c = 22
Each of them contributes a 5 to the prime factorization of 112!.
= b112/25c = 4
Each of them contributes an additional 5 to the prime factorization of
182 The Fundamental Theorem of Arithmetic
112!.
Remark
By the above example, the highest power b of 5 such that 5b divides 112!
is given by
b = b112/5c + b112/25c = 22 + 4 = 26.
In the above summands we haven’t considered b112/125c = 112 53 ,
112 54 , and so on, as their values are 0, because 125, 54 are greater
than 112.
h = bn/pc + n p2 + · · · + n pk−1
where k is the smallest positive such that pk > n so that n pk = 0,
k+1
n p = 0, and so on.
Example 4
Find the largest power of 3 that divides 207! .
Solution
We note that 5 is the smallest positive such that 35 = 243 > 207 so
that 207 35 = 0, 207 36 = 0, and so on. Hence the largest power h
of 3 that divides 207! is
= 69 + 23 + 7 + 2
= 101
Example 5
Find the largest power of 2 that divides 109! .
Solution
We note that 7 is the smallest positive such that 27 = 128 > 109 so
that 109 27 = 0, 109 28 = 0, and so on. Hence the largest power h
of 2 that divides 109! is
j k j k j k j k j k
2 3 4 5 6
h = b109/2c + 109/2 + 109/2 + 109/2 + 109/2 + 109/2
= 54 + 27 + 13 + 6 + 3 + 1
= 104
Theorem 3
Let h denote the highest power of 2 that divides n! and b the number of
1s in the binary representation of n. Then n = h + b.
Example 6
We have see that the highest power of 2 that divides n! = 109! is h = 104.
Using the Division Algorithm, the binary representation of n = 109is
obtained as follows:
109 = 54 · 2 + 1
54 = 27 · 2 + 0
27 = 13 · 2 + 1
13 = 6 · 2 + 1
184 The Fundamental Theorem of Arithmetic
6=3·2+0
3=1·2+1
1=0·2+1
109 = 1 · 26 + 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20
(109)2 = 1101101.]
n = 109 = 104 + 5 = h + b.
Example 7
Using the canonical decompositions of 720 and 3528, ?nd their gcd.
Solution
Theorem 4
Let a and b be positive integers with the following canonical decomposi-
tions:
min{a1 , b1 } min{a2 , b2 } n , bn }
(a, b) = p1 p2 · · · pmin{a
n .
For example,
Hence
= 23 · 32 · 50 · 70 = 8 · 9 · 1 · 1 = 72
as obtained above.
4n + r, where r = 0, 1, 2, or 3;
Theorem 5
The product of any two integers of the form 4n + 1 is also of the same
form.
Proof
Let a and b be any two integers of the form 4n + 1, say, a = 4p + 1 and
b = 4q + 1 for some integers p and q. Then
= 4(4pq + p + q) + 1 = 4k + 1
Remark
This result can be extended to any ?nite number of such integers.
Theorem 6
There are in?nitely many primes of the form 4n + 3.
Proof
The proof looks similar to Euclid’s proof, which established the infinitude
of primes. (by contradiction)
Suppose there are only finitely many primes of the form 4n + 3, say,
p0 , p1 , . . . , pk , where p0 = 3 and p0 < p1 < · · · < pk . Consider the
The Fundamental Theorem of Arithmetic 187
positive integer
N = 4 p1 p2 · · · pk + 3.
Case 2a) Let p = p0 = 3. Then 3|N. Now, so 3|N and 3|3, so using
the result “ a|band a|c implies a|αb + βc” it follows with a = 3, α = 1,
b = N,β = −1, c = 3 that 3|(N − 3). i.e., 3|(4 p1 p2 · · · pk + 3 −3) i.e.,
| {z }
N
3|4 p1 p2 · · · pk .i.e., 3|2 · 2 · p1 p2 · · · pk . Now using the result “Let p be
a prime and p|a1 a2 · · · an , where a1 , a2 , . . . , an are positive integers,
then p|ai for some i, where 1 ≤ i ≤ n” it follows that 3|2 or 3|pi , where
1 ≤ i ≤ k, but both are impossible.
Theorem 7
There are infinitely many primes of the form 4n + 1.
188 The Fundamental Theorem of Arithmetic
Special Cases:
Exercises
1. 1947 2.1976
3. 1863 4.227+1
Find the gcd of each pair, where p, q and r are distinct primes.
5. 23 · 3 · 5, 2 · 32 · 53 · 72
6. 24 · 32 · 75 , 34 · 5 · 112
7. p2 q 3 , pq 2 r
8. p3 qr3 , p3 q 4 r5
Prove each of the following
10. The product of any n integers of the form 4k + 1is also of the same
form.
Definition
The least common multiple of two nonzero integers a and b, is the
positive integer m satisfying the following:
Example 1
The positive common multiples of the integers −12 and 30 are 60, 120,
180, . . . ; hence[−12, 30] = 60
Given nonzero integers a and b, [a, b]always exist and [a, b] ≤ |ab|.
190
Least Common Multiple 191
Example 2
Find least number which when divided by 9 gives the remainder 8, when
divided by 8 gives the remainder 7, when divided by 7 gives the remainder
6, . . . , when divided by 3 gives the remainder 2, when divided by 2 gives
the remainder 1.
Solution
Remark
Let a and b be two positive integers with the following canonical decom-
position:
Example 3
Using the canonical decompositions of 1050 and 2574, find their lcm.
Solution
Theorem 1
For positive integers a and b
ab
[a, b] = .
(a, b)
Proof
Let a = p1 a1 p2 a2 ...pn an and b = p1 b1 p2 b2 ...pn bn be the canonical decom-
position of a and b, respectively. Then
And
[a, b] = p1 max{a1 , b1 } p2 max{a2 , b2 } ...pn max{an , bn }
Therefore,
(a, b) · [a, b] = p1 min{a1 , b1 } p2 min{a2 , b2 } ...
= ab
Thus,
ab
[a, b] =
(a, b)
Example 4
Find[3054, 12378].
Solution
3054 · 12378
[3054, 12378] =
(3054, 12378)
3054 · 12378
= = 6300402
6
The following corollary immediately follows from Theorem 2.
Corollary 1
For any choice of positive integers a andb, [a, b] = ab if and only if
(a, b) = 1.
Theorem 2
Let a1 , a2 , . . . , an be n(≥ 3) positive integers. Then [a1 , a2 , . . . , an ] =
[[a1 , a2 , . . . , an−1 ], an ].
Example 5
Evaluate [24, 28, 36, 40].
Solution
[24, 28, 36, 40] = [[24, 28, 36], 40] = [[[24, 28], 36], 40]
= 2520
(You can verify this using the canonical decompositions of 24, 28, 36,
194 Least Common Multiple
and 40.)
Corollary 2
If the positive integers a1 , a2 , . . . , an are pairwise relatively prime, then
[a1 , a2 , . . . , an ] = a1 a2 . . . an−1 an .
Corollary 3
Let m1 , m2 , . . . , mk and a be positive integers such that mi |a for 1 ≤
i ≤ k. Then [m1 , m2 , . . . , mk ]|a.
Exercises
10. Find positive integers a and b such that gcd(a, b) = 20 and [a, b] =
840.
14. Find the smallest positive integer ≥ 2 that is a square, a cube, and
a fifth power.
Chapter 14
Linear Diophantine Equations
ax + by = c
where a, b, c are given integers and a, b, are not both zero. A solution of
this equation is a pair of integers x0 , y0 that, when substituted into the
equation, satisfy it; that is, we obtain ax0 + by0 = c.
196
Linear Diophantine Equations 197
Solution
3(−6) + 6 · 6 = 18
3 · 10 + 6(−2) = 18
2x + 8y = 13
Solution
2x + 8y = 13
Example 3
Solve the following epigram problem.
198 Linear Diophantine Equations
1 1
Diophantus’s boyhood lasted 6 of his life; his beard grew after 12
1
more; after 7 more he married and his son was born 5 years later; the
son lived to half his father’s age and the father died 4 years after his son.
Then at what age Diophantus died?
Solution
If x was the age at which Diophantus died, the given data leads to
the equation
1 1 1 1
x+ x+ x+5+ x+4=x
6 12 7 2
with solution x = 84.
Theorem 1
The linear diophantine equation ax + by = c has a solution if and only
if d|c, where d = (a, b).
Proof
We note that if d = (a, b), then there are integers r and s for which
a = dr and b = ds.
Conversely, assume that d|c, say c = de. Since d = (a, b) there are
integers r and s such that
d = ra + sb.
Linear Diophantine Equations 199
x = re and y = se
Theorem 2
The linear diophantine equation ax + by = c has a solution if and only if
d|c, where d = (a, b). If x0 , y0 is any particular solution of this equation,
then all other solutions are given by
b a
x = x0 + t, y = y0 − t
d d
Proof
The first part is the content of Theorem 1. To establish the second
assertion of the theorem, let us suppose that a solution x0 ,y0 of the
given equation is known. If x0 , y 0 is any other solution, then
which is equivalent to
relatively prime. Hence there exist relatively prime integers r and s such
200 Linear Diophantine Equations
that
a b
d = r and d = s.
Hence
a = dr, b = ds.
Substituting these values into Eq.(1) and cancelling the common factor
d, we find that
r(x0 − x0 ) = s(y0 − y 0 ).
Substituting, we obtain
x0 − x0 = st
= c.
Thus there are an infinite number of solutions of the given equation, one
for each value of t.
Remark
If the linear diophantine equation ax + by = c has a solution, then it
has infinitely many solution. They are given by the general solution
x = x0 + db t and y = y0 − ad t, t being an arbitrary integer, by giving
Example 4
Find the complete solution of the linear Diophantine equation
Solution
20 = 1 · 12 + 8
12 = 1 · 8 + 4
8 = 2 · 4.
4 = 12 − 8
202 Linear Diophantine Equations
= 12 − (20 − 12)
= 2.12 − 20
= 2(172 − 8.20) − 20
= 2 · 172 + (−17)20
Now we try to find the solutions in the positive integers, if any hap-
pen to exist. For this, t must be chosen to satisfy simultaneously the
inequalities
or the inequalities
or
36
−98 > t > −100
43
Corollary 1
If (a, b) = 1 and if x0 , y0 is a particular solution of the linear diophantine
equation ax + by = c, then all solutions are given by
x = x0 + bty = y0 − at
Example 5
The equation 5x + 22y = 18 has x0 = 8,y0 = −1 as one solution. Since
(5, 22) = 1, this with corollary gives a complete solution
Solution
equation
63x + 7 = 23y
Now let us find the general solution to Mahavira’s puzzle. The linear
diophantine equation is
63 = 2 · 23 + 17
23 = 1 · 17 + 6
17 = 2 · 6 + 5
6=1·5+1
5=1·5+1
5=5·1+0
Linear Diophantine Equations 205
1=6−1·5
= 6 − 1(17 − 2 · 6)
= 3 · 6 − 1 · 17
= 3(23 − 1 · 17) − 1 · 17
= 3 · 23 − 4 · 17
= 3 · 23 − 4(63 − 2 · 23)
= (−4) · 63 + 11 · 23
= 63 · 28 − 23 · 77
Example 7
A customer bought a dozen pieces of fruit, apples and oranges, for Rs 132.
If an apple costs 3 rupees more than an orange and more apples than
oranges were purchased, how many pieces of each kind were bought?
Solution
206 Linear Diophantine Equations
(z + 3)x + zy = 132
or equivalently we obtain
3x + (x + y)z = 132.
or
This simplifies to
x + 4z = 44.
x + 4z = 44. . . . (1)
1 = 1(−3) + 4 · 1
by 44 to get
44 = 1(−132) + 4 · 44
it follows that
x0 = −132, z0 = 44
serves as one solution. By Corollary, all other solutions of Eq. (1) are of
Linear Diophantine Equations 207
the form
x = −132 + 4t, z = 44 − t
where t is an integer.
Not all of the choices for t furnish solutions to the original problem.
Only values of t that ensure 12 ≥ x > 6 should be considered. This
requires obtaining those values of t such that
12 ≥ −132 + 4t > 6
Solution
equation, we obtain
5x + 3y + 13 (100 − x − y) = 100,
or 7x + 4y = 100. . . . (2)
x = 4t, y = 25 − 7t,
so that
z = 75 + 3t,
x = 4y = 18z = 78
x = 8y = 11z = 81
x = 12y = 4z = 84
Solution
The first sailor gets up and divides n coconuts into five equal piles, with
one left over (which he throws out for the monkey) means
n − 1 = 5u1
or n = 5u1 + 1.
As the first sailor takes and hides u1 coconuts, there remains only 4u1 coconuts.
210 Linear Diophantine Equations
The second sailor gets up and divides these 4u1 coconuts into five equal
piles, with one left over (which he throws out for the monkey) means
4u1 − 1 = 5u2
or 4u1 = 5u2 + 1.
Likewise, we obtain
4u2 = 5u3 + 1
4u3 = 5u4 + 1
4u4 = 5u5 + 1
4u5 = 5z + 1.
By Cassini’s formula,
Theorem 3
The linear diophantine equation
a1 x1 + a2 x2 + · · · + an xn = c
Example 10
Determine whether the linear diophantine equations
are solvable.
Solution
(6, 12, 15) = 3, but 3 6 |10, so the 6x + 12y + 15z = 10 has no integral
solutions.
Example 11
Find the general solution of the linear diophantine equation 6x + 8y +
12z = 10.
Solution
8y + 12z = 4u . . . (3)
y = −10 − 6t + 3t0
z = 5 + 3t = 2t0
Exercises
12. A pile of mangoes was collected. The king took one-sixth, the queen
one-fifth of the remainder, the three princes one-fourth, one third, and
one half of the successive remainders, and the youngest child took the
three remaining mangoes. Find the number of mangoes in the pile.
13. A person bought some 12-cent stamps and some 15-cent stamps.
The postal clerk told her the total cost was $.5.50. Is that possible?
14. A piggy bank contains nickels and dimes for a total value of $3.15.
Find the possible number of nickels and dimes.
persons if together they pay 20 coins, each man paying 3, each woman
2 and each child 21 .
Chapter 15
Congruences
Definition
Let n be a fixed positive integer. Two integers a and b are said to be
congruent modulo n, symbolized by
a ≡ b(mod n)
Example 1
13 ≡ 3(mod5), since 13 − 3 is divisible by 5.
216
Congruences 217
Similarly,
18 ≡ 3(mod5),
6 ≡ 6(mod4),
38 ≡ 6(mod4),
59 ≡ 10 (mod7),
40 ≡ 1 (mod13).
Definition
When n doesn’t divide a − b, we say that a is incongruent to b modulo
n, and in this case we write a/≡ b(mod n).
Example 2
The following are examples for incongruence.
Similarly,
4/≡ 2(mod4)
36/≡ 6(mod4)
50/≡ 10(mod7)
41/≡ 1(mod13)
Theorem 1
Let n > 1 be fixed and a, b, c, d be arbitrary integers. Then the following
properties hold:
1. a ≡ a(mod n).
Proof
For any integer a, we have a − a = 0 · n, so that a ≡ a(mod n).
a − b = hn and b − c = kn.
It follows that
a − c = (a − b) + (b − c) = hn + kn = (h + k)n
(a + c) − (b + d) = (a − b) + (c − d)
Congruences 219
= k1 n + k2 n = (k1 + k2 )n
The proof of property (e) is covered by (d) and the fact that c ≡
c(mod n).
This is the form the statement should take for k + 1,and so the induction
step is complete.
Characterization of Congruences
Theorem 2
For arbitrary integers a and b, a ≡ b(mod n), if and only if a and b leave
the same nonnegative remainder when divided by n.
Proof
First take a ≡ b(mod n), so that a = b + kn for some integer k. Upon
division by n, b leaves a certain remainder r ; that is, b = qn + r, where
220 Congruences
0 ≤ r < n. Therefore,
a = b + kn = (qn + r) + kn = (q + k)n + r
a ≡ b(mod n).
Corollary 1
The integer r is the remainder when a is divided by m if and only if
a ≡ r(mod m), where 0 ≤ r < m.
Corollary 2
Every integer is congruent modulo n to exactly one of the values 0, 1, 2, ..., n−
1; in particular, a ≡ 0(modn) if and only if n|a.
Proof
Given an integera, let q and r be its quotient and remainder upon divi-
sion by n, so that
a = qn + r0 ≤ r < n.
Example 3
Prove that no prime of the form 4n + 3 can be expressed as the sum of
two squares.
Solution
Congruence classes
Clearly, these classes are nonempty, pairwise disjoint, and their union is
the set of integers. Accordingly, these classes form a partitioning of
222 Congruences
Definition
The set of n integers 0, 1, 2, ..., n − 1 is called the set of least nonneg-
ative residues modulo n.
Definition
A collection of n integers a1 , a2 , ..., an is said to form a complete set
of residues (or a complete system of residues) modulo n if every
integer is congruent modulo n to one and only one of the ak .
Remark
If a1 , a2 , ..., an is a complete set of residues, then a1 , a2 , ..., an are
congruent modulo n to0, 1, 2, ..., n − 1, taken in some order.
Example 4
Based on the Remark,
−3 ≡ 2(mod5), 9 ≡ 4(mod5),
81 ≡ 1(mod5).
Remark
Any set of n integers form a complete set of residues modulo n if and
only if no two of the integers are congruent modulo n.
Congruences 223
Example 5
Because the integers −56 and −11 can be expressed in the form
with the same remainder 7, Theorem 1 tells us that −56 ≡ −11(mod 9).
Going in the other direction, the congruence −31 ≡ 11(mod 7) implies
that −31 and 11 have the same remainder when divided by 7; this is
clear from the relations
Example 6
Show that 41 divides 220 − 1.
Solution
Example 7
224 Congruences
1! + 2! + 3! + 4! + · · · + 99! + 100!
by 12.
Solution
We note that
4! ≡ 24 ≡ 0(mod 12).
Thus, for k ≥ 4,
k! ≡ 4! · 5 · 6 · · · k ≡ 0 · 5 · 6 · · · k ≡ 0(mod 12)
Example 8
Show that 1919 cannot be expressed as the sum of the cube of an integer
and the fourth power of another integer.
Solution
But
62 ≡ −3(mod13)
Congruences 225
and 64 ≡ −4(mod13),
so 66 ≡ −1(mod13).
Therefore,
Example 9
Show that no integer of the form 8n + 7 can be expressed as a sum of
three squares.
Solution
N ≡ 7(mod8)
so
x2 + y 2 + z 2 ≡ 7(mod8)
Theorem 3
If ca ≡ cb(mod n) and gcd(c, n) = 1,then a ≡ b(mod n).
Proof
Suppose ca ≡ cb(mod n), where , gcd(c, n) = 1. Then n|(ca − cb); that
is, n|c(a − b).
Theorem 4
n
If ca ≡ cb(mod n), then a ≡ b mod d , where d = gcd(c, n).
Proof
By hypothesis, we can write
c(a − b) = ca − cb = kn
Remark
Theorem says that if ca ≡ cb(mod n), with d = gcd(c, n), then we can
divide both sides of the congruence by c to get
n
a ≡ b mod .
d
Example 10
Consider the congruence33 ≡ 15(mod 9). It can be written as, 3 · 11 ≡
3 · 5(mod 9). Because gcd(3, 9) = 3,Theorem 4 leads to the conclusion
that 11 ≡ 5(mod 3).
Attention!
In Theorem 3, it is unnecessary to stipulate that c/≡ 0(modn). Indeed, if
c ≡ 0(modn), then gcd(c, n) = nand the conclusion of the theorem would
state that a ≡ b(mod 1), (i.e., 1 divides a − b,) which holds trivially for
all integers a and b .
Example 11
Illustrate that the product of two integers, neither of which is congruent
to 0, may turn out to be congruent to 0.
Solution
4/≡ 0(mod 12) and
3/≡ 0(mod 12)
Example 12
Consider the congruence−35 ≡ 45(mod8). It can be written as 5·(−7) ≡
5 · 9(mod 8). The integers 5 and 8 being relatively prime, we may cancel
the factor 5 to obtain a correct congruence−7 ≡ 9(mod 8).
228 Congruences
Results
Corollary 3
If ca ≡ cb(mod p) and p - c, where p is a prime number, then a ≡
b(mod p).
Proof
The conditions p - c, and p a prime imply that gcd(c, p) = 1. Hence the
result follows from theorem 3.
Example 13
1999
Find the last digit in the decimal value of 19971998 .
Solution
c c
We note that ab = a(b ) . Let N denote the given number. The last
digit in N equals the least residue of N modulo 10. Since
1997 ≡7 (mod10),
74 ≡ 1(mod10), 75 ≡ 7(mod10)
Congruences 229
Example 14
Show that 11 · 14n + 1 is a composite number.
Solution
Let N = 11 · 14n + 1. We are going to show that p|N for some prime
p.
N ≡ 1 · (−1) + 1 ≡ 0(mod5),
so 5|N .
Example 15
Find the remainder when (n2 + n + 41)2 is divided by 12.
Solution
230 Congruences
Theorem 5
If a ≡ b(modm1 ),a ≡ b(modm2 ), ... , a ≡ b(modmk ), then a ≡
b(mod[m1 , m2 , . . . , mk ]).
Proof
By the given assumptions,
[m1 , m2 , . . . , mk ]|(a − b)
Example 16
We can verify that 85 ≡ 5(mod2),85 ≡ 5(mod8), and 85 ≡ 5(mod10);
so by above theorem, 85 ≡ 5(mod[2, 8, 10]); that is, 85 ≡ 5(mod40).
Congruences 231
Corollary 4
If a ≡ b(modm1 ), a ≡ b(modm2 ), ... , a ≡ b(modmk ), where the moduli
are pairwise relatively prime, then a ≡ b(modm1 m2 · · · mk ).
Proof
If m1 , m2 , . . . , mk are pair wise relatively prime, then [m1 , m2 , . . . , mk ] =
m1 m2 · · · mk . Hence the result follows from the previous theorem.
Exercises
4. (a) Find the remainders when 250 and 4165 are divided by 7.
15 + 25 + 35 + · · · + 995 + 1005
5. Prove that the integer 53103 + 10353 is divisible by 39, and that
111333 + 333111 is divisible by 7.
(b) Using part (a), show that any n consecutive integers form a complete
set of residues modulo n.
Definition
A linear congruence is an equation of the form ax ≡ b(mod n). A so-
lution of a linear congruence is an integer x0 for whicha x0 ≡ b (mod n).
Remark
a x0 ≡ b (mod n) if and only if n|a x0 − b i.e., if and only if a x0 − b = n y0
for some integer y0 . Hence, the problem of finding all integers that will
satisfy the linear congruence a x ≡ b(mod n) is identical with that of
obtaining all solutions of the linear Diophantine equation a x − ny = b.
234
Linear Congruence 235
Theorem 1
The linear congruence ax ≡ b(mod n) has a solution if and only if d|b,
where d = gcd(a, n). If d|b, then it has d mutually incongruent solutions
modulo n.
Proof
In the Remark above, we have observed that the given congruence is
equivalent to the linear Diophantine equation
ax − ny = b.
n a
x = x0 + ty = y0 + t.
d d
n 2n (d − 1)n
x0 , x0 + , x0 + , . . . , x0 + .
d d d
We claim that these integers are incongruent modulo n, and all other
236 Linear Congruence
n n
x0 + t1 ≡ x0 + t2 (mod n)
d d
n n
t1 ≡ t2 (mod n).
d d
Now gcd( nd , n) = n
d, and therefore by Remark below Theorem 4 in the
n
Chapter “Congruences”, the factor d could be cancelled to arrive at the
congruence
t1 ≡ t2 (mod d)
Hence
n n
x0 + t = x0 + (qd + r)
d d
n
= x0 + nq + r
d
n
≡ x0 + r(mod n)
d
n
with x0 + d r being one of our d selected solutions. This completes
the proof.
Corollary 1
Linear Congruence 237
Example 1
Consider the linear congruence 18x ≡ 30(mod 42). Because gcd(18, 42) =
6 and 6 surely divides 30, Theorem guarantees the existence of exactly
six solutions, which are incongruent modulo 42. By inspection, one so-
lution is found to be x = 4. Our analysis tells us that the six solutions
are as follows:
42
x=4+ t ≡ 4 + 7t(mod 42), t = 0, 1, . . . , 5
6
i.e.,
x ≡ 4, 11, 18, 25, 32, 39(mod 42)
Example 2
Solve the linear congruence 9x ≡ 21(mod 30).
Solution
As gcd(9, 30) = 3 and 3|21, we know that there must be three in-
congruent solutions.
x = 9 + 10t
9x − 30y = 21
so that
21 = 7 · 3 = 9(−21) − 30(−7).
Thus,
x = −21, y = −7
Linear Congruence 239
Modular Inverses
Example 3
Since 3 · 7 ≡ 1(mod2), 3 is invertible and 7 is an inverse of 3 modulo
2; that is, 3−1 is 7 modulo 2; 9 is its own inverse modulo 2, because
9 · 9 ≡ 1(mod2).
The next result shows that inverses are useful in solving linear congru-
ences.
Theorem 2
The unique solution of the linear congruence ax ≡ b (mod m), where
240 Linear Congruence
Proof.
We have the congruence
ax ≡ b (mod m),
1x ≡ a−1 b (mod m)
i.e.,
x ≡ a−1 b (mod m).
Example 4
Using the above theorem, solve the hundreds fowls riddle in Example 8
of chapter 17.
Solution
x + y + z = 100
z
5x + 3y + = 100
3
Linear Congruence 241
7x + 4y = 100.
This gives
7x ≡ 100(mod4).
3x ≡ 0(mod4).
Hence
3(3x) ≡ 3 · 0(mod4).
Since
3−1 ≡ 3(mod4)
7(4t) + 4y = 100
y = 25 − 7t.
z = 3t + 75.
Example 5
Find the last nonzero digit (from the left) in the decimal value of 234!.
242 Linear Congruence
Solution
First, notice that the product of the four integers between any two
consecutive multiples of 5 is congruent to −1 modulo 5; that is, if n ≡
0(mod5), then
It can be seen that 234! has 56 trailing zeros. Hence, the desired digit d
is the ones digit in 234! 1056 . Since the canonical decomposition of 234!
contains more 2s than 5s, d must be even. Thus, d = 2, 4, 6, or 8.To
extract the correct value of d, we compute 234! 1056 (mod5) in seven
steps:
231 · 232 · 233 · 234 ≡ −1(mod5)
230! 230!
= ≡ (−1)46 ≡ 1(mod5)
546 · 46! 5 · 10 · 15 · · · 230
46! 46!
= ≡ (−1)9 ≡ −1(mod5)
59 · 9! 5 · 10 · 15 · · · 230
9!
≡ (−1)2 ≡ 1(mod5)
5
230! 46! 9!
· 9 · ≡ 1 · (−1) · 1 ≡ 4(mod5)
546 · 46! 5 · 9! 5
234! 230! (231 · 232 · 233 · 234)
= ≡ (−1) · 4 ≡ −4 ≡ 1(mod5)
556 556
Since 256 ≡ 428 ≡ (−1)28 ≡ 1(mod5) and (2, 5) = 1, this implies
234! 234!
= 56 56 ≡ 1(mod5)
1056 2 5
Exercises
(a) 4x + 51y = 9.
In Exercises 4-6, how many solutions are there to each of the following
congruences: 4. 15x ≡ 25(mod 35);
5. 15x ≡ 24(mod 35);
6. 15x ≡ 0(mod 35).
7. Solve the each of the following sets of simultaneous congruences:
11. Solve the linear congruence 17x ≡ 3(mod 2 · 3 · 5 · 7)by solving the
system
17x ≡ 3 (mod 2)17x ≡ 3 (mod 3)
13. (a) Obtain three consecutive integers, each having a square factor.
16. A band of 17 pirates stole a sack of gold coins. When they tried to
divide the fortune into equal portions, 3 coins remained. In the ensuing
brawl over who should get the extra coins, one pirate was killed. The
wealth was distributed, but this time an equal division left 10 coins.
Again an argument developed in which another pirate was killed. But
now the total fortune was evenly distributed among the survivors. What
was the least number of coins that could have been stolen?
(b) Use (a) to show that the following system does not possess a solution:
(c) Find an integer having the remainders 3, 11, 15 when divided by 10,
13, 17, respectively.
21. Let tn denote the nth triangular number. For which values of n
does tn divide
t21 + t22 + · · · + t2n .
3x + 4y ≡ 5(mod 13)
2x + 5y ≡ 7(mod 13)
23. Obtain the two incongruent solutions modulo 210 of the system
2x ≡ 3(mod 5)
4x ≡ 2(mod 6)
3x ≡ 2(mod 7)
3x + 4y ≡ 5(mod 8).
1. 5x + 3y ≡ 1(mod 7)
2. 3x + 2y ≡ 4(mod 7).
3. 7x + 3y ≡ 6(mod 11)
4. 4x + 2y ≡ 9(mod 11).
Linear Congruence 247
6. 6x + 3y ≡ 8(mod 20).
Chapter 17
Divisibility Tests
248
Divisibility Tests 249
Because 10 ≡ 0(mod 2), 10i ≡ 0(mod 2i ) for all positive integers i.So, we
have
n ≡ n0 (mod 2)
≡ n2 n1 n0 (mod 23 )
..
.
Example 1
Let n = 256, 036. Since 2|6, 2|n; 4|36 so, 4|n; but 8 6 |036, so, 8 6 |n.
Theorem 1
Let
a = an 10n + an−1 10n−1 + · · · + a2 102 + a1 10 + a0 .
Proof
250 Divisibility Tests
We observe that
so
a = an 10n + an−1 10n−1 + · · · + a2 102 + a1 10 + a0
≡ an + an−1 + · · · + a2 + a1 + a0 (mod9).
Theorem 2
3 divides a if and only if 3 divides the sum of the digits of a.
Proof
Since 9 divides 10n − 1 for all n, so does 3. The proof is the same as for
9.
Theorem 3
Suppose
Proof
Since 2 divides 10, we have 10r ≡ 0(mod2) for all r ≥ 1. So a ≡ a0 (mod2).
Hence 2 divides a if and only if 2 divides a0 .
Theorem 4
5 divides a if and only if 5 dividesa0 .
Divisibility Tests 251
Proof
Since 5 divides 10, we have 10r ≡ 0(mod5) for all r ≥ 1. So a ≡ a0 (mod5).
Hence 5 divides a if and only if 5 divides a0 .
Theorem 5
11 divides a if and only if 11 divides the alternating sum of the digits of
a.
Proof
Since 10 ≡ −1 (mod11),it follows that 10r ≡ (−1)r (mod11) for all r.
Then
a = an 10n + an−1 10n−1 + · · · + a2 102 + a1 10 + a0
Exercises
1. 427,364
2. 30,587,648
3. 800,358,816
5. 87,654
252 Divisibility Tests
6. 639576
7. 43,979
8. 502,458
9. Find all four-digit integers of the form 4ab8 that are divisible by 2, 3,
4, 6, 8, and 9.
10. Develop a divisible test for 37. [Hint: 103 ≡ 1(mod 37)]
11. Find the smallest number that leaves a remainder i when divided by
i + 1 where 1 ≤ i ≤ 9.
Chapter 18
Wilson’s Theorem
Lemma
A positive integer a is self-invertible modulo p if and only if a ≡ ±1(mod p).
Proof
Suppose a is self-invertible. Then a2 ≡ 1(mod p); that is, p|(a2 − 1); so
p|(a − 1)(a + 1). Then, p|(a − 1) or p|(a + 1); thus, either a ≡ 1(mod p)
or a ≡ −1(mod p).
The next result tells that if p is a prime number, then p divides (p−1)!+1.
253
254 Wilson’s Theorem
If p is a prime, then
Proof
When p = 2,
(2 − 1)! = 1! = 1 ≡ −1(mod 2)
and when p = 3
(3 − 1)! = 2! = 2 ≡ −1(mod 3).
a2 − 1 ≡ 0(mod p)
and is equivalent to
(a − 1) · (a + 1) ≡ 0 (mod p).
Wilson’s Theorem 255
Therefore,
2 · 3 · · · · · (p − 2) ≡ 1 (mod p).
That is,
(p − 2)! ≡ 1(mod p).
Example 1
Taking p = 13, explain the proof of Wilson’s theorem.
Solution
(p−3)
It is possible divide the integers 2, 3, . . . , 11 into 2 = 5 pairs,
each product of which is congruent to 1 modulo 13. To write these
congruences out explicitly:
2 · 7 ≡ 1 (mod 13)
256 Wilson’s Theorem
3 · 9 ≡ 1 (mod 13)
4 · 10 ≡ 1 (mod 13)
5 · 8 ≡ 1 (mod 13)
6 · 11 ≡ 1 (mod 13)
and so
12! ≡ 12 ≡ −1 (mod 13)
Example 2
Let p be a prime and n any positive integer. Prove that
(np)!
≡ (−1)n (mod p)
n!pn
Solution
In other words, the product of the p − 1integers between any two con-
secutive multiples of p is congruent to −1 modulo p. Then
(np)! (np)!
=
n!pn p · 2p · 3p · · · (np)
Wilson’s Theorem 257
n
Y
= [(r − 1)p + 1] · · · [(r − 1)p + (p − 1)]
r=1
n
Y
≡ (p − 1)! (mod p)
r=1
n
Y
≡ (−1) (mod p)
r=1
≡ (−1)n (mod p)
Example 3
If 2p + 1 is a prime number, prove that (p)2 + (−1)r is divisible by2p + 1.
Solution
Example 4
258 Wilson’s Theorem
Solution
p(p − 1) p−2
= pxp−1 + x + ... + px
1·2
= a multiple of p, if p is prime.
Hence
f (x + 1) = f (x) + a multiple of p.
f (2) = 2p − 2 = (1 + 1)p − 2,
Example 5
Prove that 52n+2 − 24n − 25 is divisible by 576.
Solution
Hence
f (n + 1) − 25f (n) = 25(24n + 25) − 24n − 49
= 576 (n + 1).
= multiple of(576).
Proof
Assume that(n − 1)! ≡ −1(modn).
so that d|1,
Theorem 3
An integer n > 1 is prime if and only if (n − 1)! ≡ −1(modn)
Exercises
6. Prove that an integer n > 1 is prime if and only (n − 2)! ≡ 1(mod n).
10. Find two odd primes p ≤ 13for which the congruence (p − 1)! ≡
−1 (mod p2 )holds.
11. Using Wilson’s theorem, prove that for any odd prime p,
13. Supply any missing details in the following proof of the irrationality
√ √
of 2: Suppose 2 = ab , with gcd(a, b) = 1. Then a2 = 2b2 , so that
a2 + b2 = 3b2 . But 3|(a2 + b2 ) implies that 3|a and 3|b, a contradiction.
14. Prove that the odd prime divisors of the integer n2 + 1 are of the
form4k + 1.
17. If p and q are distinct primes, prove that for any integer a,
pq|apq − ap − aq + a.
262 Wilson’s Theorem
Proof
The first p − 1 positive multiples of a are the integers
263
264 Fermat’s Little Theorem
Hence
ap−1 (p − 1)! ≡ (p − 1)!(mod p)
Example 1
Find the remainder obtained when 538 is divided by 11.
Solution
538 = 510·3+8 = (510 )3 (52 )4
Example 2
2p−1 −1
Find the primes p for which p is a square.
Solution
2p−1 −1
Suppose p = n2 for some positive integer n. Then 2p−1 − 1 = pn2 .
Clearly, both p and n must be odd. Let p = 2k + 1 for some positive
Fermat’s Little Theorem 265
integer k. Then 22k − 1 = pn2 ; that is, (2k − 1)(2k + 1) = pn2 . Since
2k − 1 and 2k + 1 are consecutive odd integers, they are relatively prime.
Consequently, either 2k − 1 or 2k + 1 must be a perfect square.
2k − 1 = r2
2k = r2 + 1
That is,
2p−1 = (r2 + 1)2
2k + 1 = s2
2k = s2 − 1
That is,
2p−1 = (s − 1)2 (s + 1)2
Thus, p must be 3 or 7 .
is dropped.
Corollary 1
If p is a prime, then ap ≡ a(mod p) for any integer a.
Proof
When p|a, the statement obviously holds; for, in this setting, ap ≡ 0 ≡
a(mod p).
Remark
If it could be shown that the congruence
an ≡ a(mod n)
Example 3
Take n = 117, a = 2.
we have
Example 4
Show that n7 − n is divisible by 42.
Solution
n7 ≡ n(mod7).
Also
n7 − n = n(n6 − 1) = n(n + 1)(n − 1) (n4 + n2 + 1).
Example 5
Compute the remainder of 8103 when divided by 13.
268 Fermat’s Little Theorem
Solution
We have
≡ 87 ≡ (−5)7 , as 8 = 13 − 5
3
≡ (−52 ) (−5) ≡ (−1)3 (−5), as 25 = 26 − 1
≡ 5 (mod 13).
Example 6
Show that 211213 − 1 is not divisible by 11.
Solution
By Fermat’s theorem,
≡ 8 − 1 ≡ 7 (mod 11).
Theorem 2
Let p be a prime and a any integer such that p 6 |a. Then ap−2 is an
inverse of a modulo p.
Proof
By Fermat’s little theorem, ap−1 ≡ 1(mod p). That is, aap−2 ≡ 1(mod p),
so ap−2 is an inverse of a modulo p.
Theorem 3
Let p be a prime and a any integer such that p 6 |a. Then the solution
Fermat’s Little Theorem 269
Proof
Since p 6 |a, the congruence ax ≡ b(mod p) has a unique solution. Since,
by theorem 2 ap−2 is an inverse of a modulo p, multiplying both sides
of the congruence by ap−2 , we have
Example 7
Solve the linear congruence (12x) ≡ 6(mod 7).
Solution
3(12x) ≡ 3 · 6(mod 7)
x ≡ 4(mod 7).
Example 8
Show that for any integer n, the number n 33 − n is divisible by 15.
Solution
270 Fermat’s Little Theorem
Now 15 = 3.5, and we shall use Fermat’s theorem to show that n33 − n
is divisible by both 3 and 5 for every n. Note that n33 − n = n(n32 − n).
n2 ≡ 1(mod3),
n33 − n ≡ 0(mod5)
n4 ≡ 1(mod5)
Example 9
Show that 6 is the integral root of x7 + x + 2 ≡ 0(mod7).
Solution
67 + 6 + 2 = 6 + 6 + 2 ≡ 0(mod7)
Fermat’s Little Theorem 271
Example 10
If p is a prime number, show that the difference of the p th powers of any
two numbers exceeds the difference of the numbers by a multiple of p.
Solution
Hence xp − y p − (x − y) ≡ 0(modp).;
Example 11
Prove that every square number is of the form 5n or 5n ± 1.
Solution
Lemma
If p and q are distinct primes with ap ≡ a(mod q)and aq ≡ a(mod p),
then apq ≡ a(mod pq).
Proof
By the Corollary,
(aq )p ≡ aq (mod p),
ences, we obtain
apq ≡ a (mod p)
or, equivalently,
p|apq − a.
q|apq − a.
Hence pq|apq − a.
This is equivalent to
apq ≡ a(mod pq).
Theorem 4
Let p1 , p2 , ..., pk be any distinct primes, a any positive integer, and l =
[p1 − 1, p2 − 1, ..., pk − 1]. Then al+1 ≡ a(modp1 p2 ...pk ).
Proof
By Fermat’s little theorem, api −1 ≡ 1(modpi ), where 1 ≤ i ≤ k. Since
pi − 1|l, this implies (api −1 )l/pi −1 ≡ 1(modpi ); that is, al ≡ 1(mod pi ).
Thus, al+1 ≡ a(mod pi ). Consequently, al+1 ≡ a(mod [p1 , p2 , ..., pk ]);
that is, al+1 ≡ a(modp1 p2 ...pk ).
Corollary 2
Let a be any integer and p any prime > 3. Then ap ≡ a(mod 6p).
Proof
Let p1 = 2, p2 = 3, p3 = p in theorem 4. Since 2 · 3 · p = 6p and
[p1 − 1, p2 − 1, p3 − 1] = [1, 2, p − 1] = p − 1, the result follows by the
theorem.
i.e., if an−1 ≡ 1 (mod n) for some integer a, then n need not be prime.
The following example illustrates this.
Example 12 Verify that 2340 ≡ 1(mod 341), but 341 is not a prime.
Solution
Exercises
(e) Using Fermat’s theorem, find the remainder of 347 when divided
274 Fermat’s Little Theorem
by 23.
6. (a) Find the units digit of 3100 by the use of Fermat’s theorem.
(b) For any integer a, verify that a5 and a have the same units digit.
8. Prove that
18351910 + 19862061 ≡ 0(mod 7).
(Note: The above numbers have the following peculiarity: The three
most recent appearances of Halley’s Comet were in the years 1835, 1910,
and 1986; the next occurrence will be in 2061.)
10. Assuming that a and b are integers not divisible by the prime p,
establish the following:
! integer satisfying1 ≤ k ≤
12. Prove that if p is an odd prime and k is an
p−1
p − 1, then the binomial coefficient ≡ (−1)k (mod p).
k
13. Assume that p and q are distinct odd primes such thatp − 1|q − 1.If
gcd(a, pq) = 1,show that aq−1 ≡ 1 (mod pq).
Euler phi-function
For n ≥ 1, let φ(n) denote the number of positive integers not exceeding
n that are relatively prime to n.
Example 1
φ(30) = 8; for, among the positive integers that do not exceed 30, there
are eight that are relatively prime to 30; specifically,
Example 2
φ(1) = 1, φ(2) = 1, φ(3) = 2,
276
Euler’s Theorem 277
definition.
Definition
φ(n) is the number of integers less than n and relatively prime to it. The
function φ is called Euler phi-function.
Result
φ(n) = n − 1 if and only if n is prime.
Proof
If n is a prime number, then every integer less than n is relatively prime
to it. Hence φ(n) = n − 1.
Lemma
Given integers a, b, c, gcd(a, bc) = 1 if and only if gcd(a, b) = 1 and
gcd(a, c) = 1.
Proof
First suppose that gcd(a, bc) = 1, and put d = gcd(a, b). Then d|a
and d|b, and hence d|a and d|bc. This implies that gcd(a, bc) ≥ d, which
forces d = 1. Similar reasoning leads to the statement gcd(a, c) = 1.
the fact that p|a) we have gcd(a, b) ≥ p, contradiction. In the same way,
the condition p|c leads to the equally false conclusion that gcd(a, c) ≥ p.
Thus, d1 = 1 and the lemma is proven.
φ(1) = 1 and φ(2) = 1 are not even integers, however, the next theorem
ensures that for n > 2, φ(n) is an even integer.
Theorem 1
For n > 2, φ(n) is an even integer.
Proof
First, assume that n is a power of 2, let us say that n = 2k , with k ≥ 2.
1
φ(n) = φ(2k ) = 2k 1 − = 2k−1
2
Lemma
Let m be a positive integer and a any integer with gcd(a,m)=1. Let
r1 , r2 , ..., rφ(m) be the positive integers ≤ m and relatively prime to m.
Then the least residues of the integers ar1 , ar2 , ..., arφ(m) modulo m are
a permutation of the integers r1 , r2 , ..., rφ(m) .
Proof
The proof consists of two parts. First we will show that gcd(ari , m) = 1
for every i. Then we will show that no two numbers ari and arj can be
Euler’s Theorem 279
To show that no two of the integers ari can be congruent modulo m; that
is,ari /≡ arj , where 1 ≤ i < j ≤ φ(m):
Suppose ari ≡ arj (mod m). Since gcd(a, m) = 1, ri ≡ rj (mod m). But
ri and rj are least residues modulo m, so ri = rj . Thus, if i 6= j, then
ari /≡ arj (mod m).
Thus, the least residues of ar1 , ar2 , ..., arφ(m) modulo m are distinct and
are φ(m) in number. So they are a permutation of the least residues
r1 , r2 , ..., rφ(m) modulo m.
Proof
There is no harm in taking n > 1. Let a1 , a2 , . . . , aφ(n) be the positive
integers less than n that are relatively prime ton. Because gcd(a, n) = 1,
it follows from the lemma that aa1 , a a2 , . . . , aaφ(n) are congruent, not
necessarily in order of appearance, to a1 , a2 , . . . , aφ(n) . Then
....
..
where a01 , a02 , . . . , a0φ(n) are the integers a1 , a2 , . . . , aφ(n) in some order.
On taking the product of these φ(n) congruences, we get
≡ a1 a2 . . . aφ(n) (modn)
and so
n = 17, 32, 34, 40, 48 and 60
gcd(a1 a2 . . . aφ(n) , n) = 1.
aφ(n) ≡ 1(modn).
Proof
If p is a prime, then φ(p) = p − 1. Hence Theorem 1 with n = p gives
ap−1 ≡ 1(modp).
Example 3
Euler’s Theorem 281
Solution
3φ(100) ≡ 1(mod100)
256 = 6 · 40 + 16.
Hence
3256 ≡ 36·40+16 ≡ (340 )6 316 ≡ 316 (mod 100)
and our problem reduces to one of evaluating 316 , modulo 100. The
method of successive squaring yields the congruences
32 ≡ 9 (mod100), 38 ≡ 61(mod100)
Theorem.
Example 4
Find all solutions of the congruence 12x ≡ 27(mod18).
Solution
Example 5
Find all solutions of the congruence 15x ≡ 27(mod18).
Solution
Theorerm 3
Let m be a positive integer and a any integer with gcd(a,m)=1. Then
aφ(m)−1 is an inverse of a modulo m.
Theorerm 4
Let m be a positive integer and a any integer with gcd(a,m)=1. Then
Euler’s Theorem 283
Theorem 5 (Koshy)
Let m1 , m2 , ..., mk be any positive integers and a any integer such that
gcd(a, mi ) = 1 for 1 ≤ i ≤ k. Then
Corollary 2
Let m1 , m2 , ..., mk be pairwise relatively prime integers and a any integer
such that gcd(a, mi ) = 1 for 1 ≤ i ≤ k. Then
Exercises
5. Show that there are infinitely many integers n for which φ(n) is a
perfect square.
(b) If the integer n > 1 has r distinct prime factors, then φ(n) ≥ n/2r .
√
(c) If n > 1 is a composite number, then φ(n) ≤ n − n.
7. Prove that if the integer n has r distinct odd prime factors, then
2r |φ(n).
n
(b) There are no integers n for which φ(n) = 4.
(a) There are at most a finite number of integers n for which φ(n) = k.
14. (a) Prove that the equation φ(n) = 2p, where p is a prime number
and 2p + 1 is composite is not solvable.
(b) Prove that there is no solution to the equation φ(n) = 14, and that
14 is the smallest (positive) even integer with this property.
18. If a and b are relatively prime, then prove that aφ(b) + bφ(a) ≡
1(mod ab)
(a) p = 2 , n = 3 (b) p = 3, n = 3
_______________________________________________________________
SYLLABUS
SEMESTER – I
MTS1B01 : BASIC LOGIC AND NUMBER THEORY
4 Hours/Week 4 Credits 100 Marks[Int: 20 + Ext : 80]
Logic, the study of principles of techniques and reasoning, is fundamental to every branch of
learning. Besides, being the basis of all mathematical reasoning, it is required in the field of computer
science for developing programming languages and also to check the correctness of the programmes.
Electronic engineers apply logic in the design of computer chips. The first module discusses the
fundamentals of logic, its symbols and rules. This enables one to think systematically, to express ideas
in precise and concise mathematical terms and also to make valid arguments. How to use logic to arrive
at the correct conclusion in the midst of confusing and contradictory statements is also illustrated.
The classical number theory is introduced and some of the very fundamental results are discussed
in other modules. It is hoped that the method of writing a formal proof, using proof methods discussed
in the first module, is best taught in a concrete setting, rather than as an abstract exercise in logic.
Number theory, unlike other topics such as geometry and analysis, doesn’t suffer from too much
abstraction and the consequent difficulty in conceptual understanding. Hence, it is an ideal topic for
a beginner to illustrate how mathematicians do their normal business. By the end of the course, the
students will be able to enjoy and master several techniques of problem solving such as recursion,
induction etc., the importance of pattern recognition in mathematics, the art of conjecturing and a
few applications of number theory. Enthusiastic students will have acquired knowledge to read and
enjoy on their own a few applications of number theory in the field of art, geometry and coding theory.
Successful completion of the course enables students to
• Prove results involving divisibility, greatest common divisor, least common multiple and a few
applications.
• Learn three classical theorems viz. Wilson’s theorem, Fermat’s little theorem and Euler’s theo-
rem and a few important consequences.
Syllabus
Text (1) Discrete Mathematics with Applications : Thomas Koshy, Elsever Academic
Press(2004) ISBN:0-12-421180-1
Text (2) Elementary Number Theory with Applications (2/e) : Thomas Koshy, Elsever Aca-
demic Press(2007) ISBN:978-0-12-372487-8
1.1: Propositions- definition, Boolean (logic) variables, Truth Value, Conjunction, Boolean expression,
Disjunction (inclusive and exclusive), Negation, Implication, Converse, Inverse and Contra positive,
Biconditional statement, Order of Precedence, Tautology Contradiction and Contingency [‘Switching
Networks’ omitted]
1.2 : Logical equivalences- laws of logic [‘Equivalent Switching Networks’ ‘Fuzzy logic’ & ‘Fuzzy
decisions’omitted]
1.3 : Quantifiers- universal & existential, predicate logic
1.4 : Arguments- valid and invalid arguments, inference rules
1.5: Proof Methods – vacuous proof, trivial proof, direct proof, indirect proof-contrapositive & con-
tradiction, proof by cases, Existence proof- constructive & non constructive, counter example
1.3 : Mathematical induction- well ordering principle, simple applications, weak version of principle of
mathematical induction, illustrations, strong version of induction (second principle of MI), illustration
1.4 : Recursion- recursive definition of a function, illustrations.
2.1: The division algorithm – statement and proof, div & mod operator, card dealing, The two
queens puzzle (simple applications), pigeonhole principle and division algorithm, divisibility relation,
illustration, divisibility properties, union intersection and complement-inclusion exclusion principle &
applications, even and odd integers.
2.5: Prime and Composite Numbers- definitions, infinitude of primes, [‘algorithm 2.4‘ omitted] The
sieve of Eratosthenes, a number theoretic function, prime number theorem (statement only), distri-
bution of primes (upto and including Example 2.25). [rest of the section omitted]
Module – III Text (2) (17 hrs)
3.1 : Greatest Common Divisor- gcd, symbolic definition, relatively prime integers, Duncan’s identity,
Polya’s theorem, infinitude of primes, properties of gcd, linear combination, gcd as linear combination,
an alternate definition of gcd, gcd of n positive integers, a linear combination of n positive integers,
pairwise relatively prime integers, alternate proof for infinitude of prime.
3.2: The Euclidean Algorithm- The Euclidean algorithm [algorithm 3.1 omitted], A jigsaw puzzle,
Lame’s theorem (statement only; proof omitted)
3.3: The Fundamental Theorem of Arithmetic- Euclid’s lemma on division of product by a prime,
fundamental theorem of arithmetic, Canonical Decomposition, number of trailing zeros, highest power
of a prime dividing!, [only statement of Theorem 3.14 required; proof omitted] Distribution of Primes
Revisited, Dirichlet’s Theorem (statement only)
3.4 : Least Common Multiple- definition, canonical decomposition to find lcm, relationship between
gcd and lcm, relatively prime numbers and their lcm
3.5: Linear Diophantine Equations – LDE in two variables, conditions to have a solution, Aryabhatta’s
method, number of solutions, general solution, Mahavira’s puzzle, hundred fowls puzzle, Monkey and
Coconuts Puzzle, [‘Euler’s method for solving LDE’s omitted] Fibonacci numbers and LDE, LDE in
more number of variables and their solutions- Theorem 3.20
1. Susanna S Epp: Discrete Mathematics with Applications(4/e) Brooks/ Cole Cengage Learn-
ing(2011) ISBN: 978-0-495-39132-6
3. David M. Burton : Elementary Number Theory(7/e) McGraw-Hill (2011) ISBN: 978-0- 07-
338314-9
4. Gareth A. Jones and J. Mary Jones: Elementary Number Theory, Springer Undergraduate
Mathematics Series(1998) ISBN: 978-3-540-76197-6
5. Underwood Dudley : Elementary Number Theory(2/e), Dover Publications (2008) ISBN : 978-
0-486-46931-7
6. James K Strayer : Elementary Number Theory, Waveland Press, inc. (1994), ISBN : 978-1-
57766-224-2
7. Kenneth H. Rosen: Elementary Number Theory(6/e), Pearson Education (2018), ISBN: 978-0-
13-43100-531-1