G. C.

D
The g.c.d ofof Ay of Int
any n
gcd(a
a a
#0,
ag, ...., a,)
nuber of
i=1, ....,
2,
given
the or is denoven by
positive integer d,simply (a, a ., a,)
ed\a;,
If i=l, 2, sat
.., is
nfyin g the
follo win
and
g
is
defi ned as
c\a,; =1,2,
, i
2.4 Euclid's Algorithmthen ...,n condi tio ns :

The g.c.d. of
two
. cd.
efficientlydescribedrecurring
which is by a integers a
process
and can be
b
as
follows. known as determined
Theorem
positive 2.7.
(Euclid' s Euclid's al gorithm
assumne integers.
that
assume that a> anda>0 Since Alg
ged(a, orith
b). mn)
= Let a and be b
two
By b>0.
b>0.
Division algorithm, there With gcdab),
out loss can
generality of we
we
a= bg, +r exist integers q, and r
If ,=0 where 0 sr
<b. such that
then ba
If r0 gcd(a, b) = b and the
... (1)
then by division process stops.
b, = rq, t algorithm,
If r, = 0 where 0Sr, <r. ...(2)
then gcd(a, b) = , and
If r, * the process
0, then by stops.
Division algorithm
rË =, Q3 + T3
where 0s <, .(3)
If r, =0 then gcd
(a, b) = r, and the
process stops.
THEORY
O) NUMBERS
151

then by Division algorithm

where 0s,<Is
... (4)

Continuingthis process we get

Ig =I; q, + ; where ... (5)

I-3=!h-24n-1 th- where

0Sr,-Ih-2 ... (n - l)
Ih-2='n-14n +h where (n)
Ifr =0 for some positive integer n, the process stops and

god(a, b) =h-1:
Proof. From (1), (2), ..., (n) we observe that

which is a decreasing sequence of non-negative integers.

It follows that r,’0 as n ’ D.

Uonsequently, , =0 for some integer n.

This confirms the termination of the process.
Let us now prove the main part of the theorem.
We have a set of n recurrence relation (1) (n). We apply
backward substitution starting from the relation (n).
From relation (n), we get
Tn-2 ='n-1 4, + 0
As q, e .. (e,)
Z,it follows that r-l-2
Again, Tn-3 n-2n-1 t n-1
*n-1, 9n-1+n-1 [by (e)]
 152 DISCRETE MATHEA
followsthat r,l.
, e Z ,it
As
Again
le.9.ta3 t9.) [by (e) and
,9.9g 9e,itfollows that r,..,
As
Continuing in this way we finally arrive at the rea

laand b.
relations (1) and (2) as r=r, =0 ultimately )
(See
common divisor of aand b.
Thus , isa
condition of being the g.c.d. of a
So it satisfies the first
and.i
Now let c be a common divisor of aand b, i.e, cla
Then cl(a -bq,) by Theorem 2.2 (vi)]
clr, l: from (1) a =bq, +rl
Again from (2) b = ra, +, we get

cl, clb and cln » cl(o-;g) »cl¡

Thus c divides a, b, r, r, .
Proceeding in this way we finally arrive at the result that:
divides r-1
Thus cla and clb c :
Scdof
Thus ,-1 satisfies the second condition of being the,
and b.

Hence gcd(a, b) = n-: (Proved)

Illustration//
Let us find ged(486, 330).
We have 486 = 330 × 1 + 156
330= 156 x 2 + 18
THEORY OF NUMBERS
153

156 = 18x 8+ 12
18 =12 xI+6
12=6x 2 +-0
The last non-;zero remainder is 6. Hence gcd(486, 330) =6.
Theorem 2.8. (Existence and
Ifa and b are
Uniquences
two integers not both
Theorem)
zero, then gcd (a, b)
oists and is unique.
Proof.
Existen ce
As gcd(a, b) is not affected by the signs of a
and b, we,
therefore, assume that a>0, b>0.
Without loss of generality, we also assume that azb.
By Division algorithm, there exist
integers q, and r such that
a= bq + , 0s <b ... (1)
Case 1: If r =0 then bla and gcd(a, b)
=b. Thus gcd (a, b)
exists in this case.
Case 2: If r0,
then by Division algorithm, there exist
integers 42: such that
b= rg2 t , 0ST, <} (2)
Case 3: If ,=0 then
; b and so from (1),
a =(g42)+}
Or, a = (q,
42+1)
1.9,e Z, it
Now let s\a and follows
that r;la.Thus r, la and r, lb.
slb for some positive integers.
"Then sla and slb’ s\(a-bg,) | by Theorem 2.2 (vi) ]
slr fromn (1)
gcd(a,
"Thus in b) = :
this case also gcd(a, b)
exists.
172
DISCRETE MATUEMATI
Solution. We know that any integor is of the
3k +l or 3k+2 for Nome integer k. Sinco p
is
prime n
so it is either of the form 3k+l or 3k+2.
Also p2b.
number
If p 3k +l,then p 2-(3k +1)+2
-9k +6k +3
-
If p
3(3k+2k+1), which is a composite number.
3k +2, then p+2 =(3k+ 2)° +2
= 9k +6k +6

-3(3k +3k +2) which is a

composite number.
Thus p +2 is a
composite number for all primes p25.
(Proved)
Problem(jnd the total number of positive divisors of
444720375.
Solution. We have 444720375 = 3 x 5
Theorem 2.19, the total number of x11'. Then by
444720375 is (5 + 1)(3 + 1)(4 + 1) = 120. positive
(Ans.)
divisors of
Short Test 3
1. If p and p +8
are both primes then show that p=3.
2. If p is a prime
number greater than 3, then show that
2p+l and 4p+1 are prime
3. If p and qare
numbers simultaneously.
perfect square.
twin primes then show that
(po+1) is a
[ Hints::Since p and q are
twin
primes, therefore,
4. Ifp and q are twin primes then show
9=p+2, etc.)
that
whenever p>3.
12\(p+)
 OFN
NUMBERS 191

5-1) x 4 x (-2)} (mod

( 13)
32(mod 13)
6(mod 13) | 326(mod 13) ]
Henceproved.

Problem8 Find the remainderwhen 240 is divided by

341.
Solution. We have 341 = 11 x 31 and 340 = 68 × 5
Now 2 = 32 = -1 (mod 11),
g0 =(29)68 = 3268'=(-1)68 (mod 11)
: a=b(mod m) o= b" (mod m)
Thus 240 1(mod 11)
Similarly 25 = 1.(mod.31) .
’ (2)68 = (1)$8 (mod 31)
2210 = 1 (mod 31)
Now, g10 =1(mod 11),
’11|(240 -1)
2340 =
l(mod 31) ’ 31(2840 1)
Again gcd (31, 11) =1
(11x 31) l(20- 1)
’
341.|(2340 1).
2340 = 1(mod 341)
Hence the remainder when 2340 is divided by 341 is 1! (Ans.)
Diem Find the remainder when 387 is divided by
23.
Solution. We have 3287 =3256 xgl6 x3 x3 x3* (1)
4(mod 23) and g' = -11(mod 23)
(mod 23) :a b(moû ))’
a'=b'" (mod
192
DISCRETE M
MATHEMATICS

6(mod 23) -11 =121w 6(mod 23) |

: 316 = (3*)° = 6 (mod 23)
or, 316 -10(mod 23)
|:6= 36 =-10 (mod 23))
.. 32= (316)² = (-10)°
(mod 23)
= 8(mod 23)
3$1 = (3*y² = 8 (mod 23)
::-10)= 100 = 8 (mod 23))
=(-5) (mod 23) |
8= 36 = (- 5) (mod 23))
3128 = (36ry² =(- 5)°
(mod 23)
= 2 (mod 23)
3256 = 2 (mod 23) ::(-5)°= 25 = 2 (mod 23)]
or, 3256 = 4(mod 23)
We know that
a
=b(mod m) and c= d(mod m) ’ ac =
Using this property bd(mod m)
g287 =(4x
repeatedly we get from (1)
(-10) x6 x (-11) x 4)(mod 23)
=((-40) x (-66) x 4)(mod 23)
=(6x3 x4)(mod 23)
[: -40 = 6 (mod
23) and --66 = 3(
=(24 x3)(mod 23) mod 23)|
=(1x3)(mod 23) |:: 24 = 1
3287 = 3 (mod 23) (mod 23)]
Hence3287 leaves a remainder 3 when it is
Problem 5. What is the remainder when divided
gl2 + 5
by 23. (Ans.)
is
by 13 ?
divided
 LASSMATCH
Exclusie

QuenBI MAKE
CHESS
mowes
MATH

m
1ngNoteBook
 "Thus for x, yeS, x covers y
>y<x(rszsy(x =z)v(z=y)).
Illustration 6, 12, 24,
Consider the poset (S,I) where S=(2, 3, 36 an
Tis the relation on S defined by
yeS.
"rly if and only ifx divides y" for x,
Then 6 covers 2 as 2|6, 6 covers 3 as 3|6 but 12 does
cover 2though 2| 12 because there is an
element 6 in
between
2 and 12 such that 2|6, 6| 12. Similarly 24 and 36 both en
12 as 12|24 and 12|36 but none of them covers 6 or 38 or
because in between 3 and 24 there are elements 6. 12 suni
hat 3|6,3|12, 6|12, although 3|24. Similar are the cases ir
2 and 6., Note that 6 is the immediate successor of 2 and 3
while 12 is the immediate predecessor of 24 and 36.
Hasse Diagram
The pictorial or diagrammatical representation of a partia
order relation < on set S is known Hasse diagram. Inthis
diagram the elements of S are represented by small circles. à
line segment is drawn to join the elements a and b of Sif the
are related by the covering relation <. If b covers a theni
the diagram, b will be placed above a."
Illustration
/1. Consider the poset (S, |) where S={12, 3, 4, 6, 12)an
divid
1' is the relation on S defined by x\y if oand only ifx
y" for x, y eS.
The Hasse diagram of this poset is shown in Fig. 3.1.
s
ofl,
Since 1|2, 1|3 and 2, 3 are immediate successor doesno
place 3, 2above l and they are joined with 1. Now 2
divide 3. So 3 and 2 remain on the same level.
 L47
AND LATTICES

12

of the poset
(S,|) where
diagramm
Pig. 3.1Hasse S={1,2,3,4, 6,12}
above 3, 2 and is connected
2 divide 6. So 6 is kept and is kept above 2.
Both 3, with 2
and 2.2|4, so4 is connected kept on the same
with 3 and6 are
does not divide 6, So 4 above 6 and 4 and
is
Again 4 is kept
Both 6, 4 divide 12. So 12
level.
4.
Connected with 6 and power
(P(S), ) where P(S) is the
2Consider the poset relation on PS) defined by
S= {a, b, c}and c is the B", A,Be PS). The
set of ifA is a subset of
"Ac Bif and only Fig 3.2. Here
this poset is shown in since the
Hasse diagram of c}, {b, c} b, c} point of the
{a,lowest
RS)={0. fa}, {o}, fc}.fa, b}, {a,
subset of all sets, it is the
hullset is the the superset of all sets in P(S)
isc}
diagram. Again S = fa, b,
the diagram.
It is the highest point in
{a, b; c}

{a, bi a, c} {b, c

Die. 3.2. Hasse diagramm of the poset (P(S), )

where S={a, b, c}
POSET'SAND LATTICES 255

(dis a lower bound of tlhe pair a, b) and (p is a lower

Thus, b)
ofthe paira,
ound

Consequently, d=aab.
that glb of every pair of elements a, be S is
follows
gcdla,b)
9 =1, 3 A8 =1, 6A 72 = 72, 9A 12 = 3
For example, 2
etc.
and l= lcm(a,b). Then all and
Let a, be S be arbitrary
common multiple of a and b then lg
bll. If q be any other every common multiple of a, b).
(since lcmfa,b) divides
q)lsq.
.(axl,bsl) and (a <q, b< pair a, b) and (g is an
( lis an upper bound of the
Thus,
b) ’lKq.
upper bound of thepair a,
Consquently, l= avb. of elements a, beS is
lub of every pair
If follows that
lem(a,b) - 2v9=18,
v9= 36,
For example, 4
=72, etc.
3v 24.24 v 36 following set S with
Determine whether the
Problem 2 the corresponding Hasse
draw
relation p is a poset. Ifyes, least, maximal and minimal
the greatest,
diagram and find the
elements of the poset.
(1,1).,(1,2).(2,2).(2,4),(1,3),
(a) s={1,2,3,4}. p= (3,3).(3.4).(1,4).(4,4)
{(a,a).(6.b).(e.c).(a,c).(e.d),
(6) s={a,6,c,d), p=
(c.e).(a.d). (a,d).(a,e).(b.c). (b.d). (0.e).(e,e))
256
DISCRETE MATHEMATICA
Solution.
(a) Here S={1.2 3,4}. Since (1,1), (2,2).(3,3),(4.4).
therefore, p is reflexive on S.
For a, be S, we observe that if (a, b) ep, then
that (a, b) epa(b, a) ep»a=b.
p is antisymmetric on S.
(1.2) ep and (2, 2) ¬p»(12) p
(1 1) ep and (1, 2) ¬p»(1,2) ¬p
(12) ep and (2, 4) ep’(14) ¬p
(1 1) ep and (1, 3) ¬p»(1,3)ep
(2, 2) ep and (2, 4) ep» (2, 4) ep
(1,1) ep and (1, 4) ep»(1,4) ¬p
(1,3) ep and (3, 3) ¬p»(1,3) ep
(13)ep and (3, 4) ep’(14) ep
(2, 4) ep and (4, 4) ep>{2,4) ep
(1,4) ep and (4, 4) ep»(1,4) ep
(3, 4) ep and (4, 4) ep»(3,4) ep.
Hence p is transitive on S.
Thus pis reflexive, antisymmetric and transitive. Therefore
p is a partial order relation on S. Consequently, S,p)a poset.
(Ans.)
Hasse diagram of this poset is shown 1s 4
Fig 3.4.
1is the
minimal as well as the least
element of the poset (S, p). 20
4is the
maximal as well as the greatest
element of the poset (S, p).
Fig3.4
AASETSAND LATTICES 257

=a, b, c, d, e. We observe that.

A) Here S
VreS, (*, x)ep.
on S.
..p is reflexive
observe that if (x, y) ep then (y, x) p.
Eor x, ye S, we
Thus, for(x, y)e S,
(, y)ep and (y, *) ep’*= y.
antisynmetric on S.
..p is a
y, ze S, (x, y)ep
Also we observe that, for x,
da
and (y. z)ep » (x, z)ep.
S.
..p is transitive on
antisymmetric
Since p is reflexive,
a partial order
and transitive, it is
p) 18 a
ob
relation on S. Consequently (S, Fig. 3.5
a poset.
of the poset
The Hasse diagram
(S, p) is shown is Fig 3.5. maximal elements
are a, b and its
Minimalelement of (S,p) element nor
p) has neither greatest
are d, e. The poset (S,
least element. 5 94
the poset 64
Problem 3. Determine given in
is as
Whose Hasse diagramn 3
Fig. 3.6.
poset is
Solution, The reguired
(S.s) where 2 1
S={12, 3, 4, 5, 6} and Fig. 3.6
 258 DISCRETE MATHEMAT
<=(1 1),(2, 2).(3, 3),(4, 4),(5. 5). (6, 6). (1 3).(2, 3)
(3,4),(3.5),(3.6),(1,4). (1.5), (1.6),(2,4),(25),(2.6)
Note that, nodes 1 and 4 are connected via node 3. He.
along with the pairs (1, 3) and (3, 4), the pair (l4) must be
<. With similar arguments (1 5), (1 6),(2, 4),(2, 5),(2, 6) a:
included in s.
Problem 4. Show that if A be a finite non-empty set axt
< be a partial order defined on A, then the
poset (4,)hzs
at least minimal eleme:
at least one maximal element and has
Solution. Let a be any element of the finite nonempty
(A, 3), then :
A. If a is not a maximal element of the poset
can find an element a, eA such that a<a,.
find g
we can
If a, is not a maximal element of (A, ),
element a, EA such that a, a,
continued indefinitely, since.*
This argument cannot be
a finite chain
a finite set. Thus we eventually obtain

have a,
which cannot be extended. Hence we cannot
element of (A, )
for any beA. So a, is the maximal non-emp
finite elemen!
Again let b be an arbitrary element of the find an
set A. If b is not a minimal element, we can
element,N
minimal
b. eA such that b <b. If b, is not a argumer

that b h. This Thus

can find an element b, EA such Set.
indefinitely as Ais a finite
cannot be continued
have the chain
ASETSAND LATTICES 259

cannot be extended. Thus we cannot find ceA such

shich
c b . Hence b, is the minimal element of the poset
that

element
Thus the poset (A, ) has at least one maximal
least one minimal elemnent. (Proved).
and has at
diagram of the poset
Problemn 5. Determine the Hasse
the relation is given by
A ) where A=(1, 2, 3, 4, 5} and
the matrix

[1 0 1 1 1]
0 1 1 1 1

M =0 0 1 1 1
0 0 0 1 0
|0 0 0 0 1

Solution. Here A ={1 2, 3, 4, 5}. The 5

fromn the
relation on A is obtained
given matrix M as follows.

a={(1.1). (1,3). (1, 4).(1. 5),(2, 2).(2, 3).(2. 4).

(2,5). (3, 3), (3, 4), (3, 5). (4, 4). (5, 5)} Fig. 3.7
3 is a
It can be easily verified that
partial order relation, (See solution of
Problem 2.)
is (4, ) shownin Fig. 3.7.
The Hasse diagram of the poset
the matrix of the partial order
Problem 6. Determine Fig .8.
relation whose Hasse diogram is as shown in
Solution. Here the poset is (A, ) where
on A
14,6, c, d, e, f} and < the partial order relation
260 DISCRETE M
MATHEMATIC

which is determined from the given graph as followe

f
*=((o.a). (6, b). (c. c). (d. d). (e. e).
(.).(a.b).(a. c).(a. d)}
(6.e).(0. f).(c. e).(c. f).
(dhe). (d. f).(a. e).(a. f)} Fig. 3.8
Matrix for this relation /s

1 1 1 1 11
0 1 0 0 11
0 0. 1 0 1 1
M -
00 0 1 1.1
(Ans.)
0 0 0 01 0
0 0 0 0 0 1|

Remarks. Due to antisymmetry, M is an upper triangu

matrix.

Problem 7. Let (S,<) be a poset. Prove that

unique
(i) if a, beS have aleast upper bound then that is
(ii) if a, beS have a greatest lower bound thenthatis
unique.
Solution.
i) Let u, be the luo of a, b eS. Then uË eS anda
b :
Let, if possible, u, be another lub of a,b. Then
W;
a< uy, b u,. Since u, is ofa, band
lub of a, b, an upper bound
therefore, u, u
Since u, is an upper bound of a, b and u, is aleast
bound of a, b therefore, u uy.
 uell-ordered set and Bis aset lell-oradered.
Bis also well-ordered. isomorphic
to A.
finite linearly
ordered sets each having same
of elements are
iOrphic to each other.
well-ordered and are all
Sisa urell-ordered set then every
element aeS has
immediate successor provided a is not the
iement of S. greatest
Illustrative Examples 2
Problem 1. Let S be the set of all positive
divisors of 72.
nt a relation on S by <yifand only if xis adivisor
or x yeS. Prove that (S, ) is a poset. Draw the Hasse
ETSm of this poset. Also find maximal and minimal
ents greatest and least elements ofthe poset and lub and
g ot every pair of elements of S.
Solution. Here S={12, 3. 4, 6; 8, 9, 12, 18, 24, 36, 72}.
let us first show that the divisibility relation < is a partial
eT relation on S.

"TES, r < (": x is a divisor of itself).

1 is reflexive on S.
" For x, y
<S, x<y and y <x
is a divisor of v) and (v is'a divisor of x)
(= mx for some positive integer m) and (x = ny for SOme
positive integer n) ( , y are positive integers]
y= mny
mn =1(
y# 0)
m=1and n=1(:: m, n are positive integers).
254
DISCRETE MATHIEMATICS

I=y
Thus for x, ye S,x <y and y
..Kis antisymmetric on S.
For , y, ze S,

(r is adivisor of y) and (y is a divisor of 2)

(y= k,x for some positive integer k)a(z= k,y for some
positive integer k,)

I s a divisor of z

.. x is transitive on S.
transitive on S. Hence
Thus K is reflexive, antisymmetric and
S.
< is a partial order relation on
Consequently (S, 3) is a poset.
72
Hasse diagram of the poset
(S, <) is shown in Fig 3.3. 24
lis the minimal element 12
maximal
and 72 is the 36a 180
element of the poset (S, )
(Ans.)
Let a, be S be arbitrary.
1

Let d = gcd(a,b).Then d | a Fig 3.3

o
and d|b. divisor
Common
Ifp be any other common
since every
divisor of a and b, then pld
a, b divides ged (a, b))
’p
(:d a, d <b) and (psa, p<b)
214
DISCRETE MATHEMAT

r-36_ y-24 =l,where t is an integer.

-8 5

N=36 - 8 and y =24 +5t where t =0,

±1, 2,.
This the required general solution. (Ans.)
Problem D. Find the missing digit in the number
8630480*874 if it is
(i) divisible by 9.
(ii) divisible by 7.
(iii)divisible 11.
(iv) divisible 13.
T
Solution. Let d be the missing digit in the given numb: 6.
N. Thus N:
8630480d874
(i) Sum of the digits = 48 + d, (i

Now 9|N 9l(48+d).

ar

Since d is a decimal digit i.e., de {0, 1,2, 3, 4,

5, 6,7, 8, 3}' Al
it follows that d=6.
Thus Nis divisible by 9 if the
missing digit is 6. (Ans.
(ii) Expressing Nin terms of triplets of 3-digit numbers wege
N: (086) (304) (80d)
Now the decimal representation of the (874)
number having digita an
form '80d' is 8 x 10 +0x 10 +
dx10 = 800+d.
Now, 874 - (800+d) + 304 do
-86 = 292 -d.
Thus, 7|N7\(292-d). He
Since dis a
decimal digit, and 292 =7x 41 +5, itfollows
d= 5. Thus in this case the
missing digit is 5.' (Ans.)