Number Theory

tMTRODUCTION
we
be discussing the theory of numbers. We shall begin our discussion
shall

of integers. But before that, we first describe an important preliminary

chapter,
n s
thist
divisibility

of asprinciple of'mathematical
n induction which is often used as a method of
t
knawn

well as a
method of proof. Many proofs in the present text make use of this result.
PRINCIPLE
OF MATHEMATICAL INDUCTION
THEE
12This prinCiples t a t e s :

statement involving natural number n, such that

fMn) is u
i.e., the statement is true for n =1, and
Pl) Ls true,
1) is true whenever P(k) is true, i.e., the truth of P(k) implies the truth of
ü) If Ph +
Ph + 1)
atall natural numnber n.
Pn) is true for
numbers, we have the
rhus in order to prove a statement Pn) to be true for all natural
Slowing working rule

1. Proue that Pl) is true;

A.t.,
Pn) is true forn=1
2. Assune Pk) tobe true:

L.e., Pn) is true forn=k

3. Prove that Ph + l)is also true;

L.e., Pn) is ulso true for n = k + 1.
induction
o, The method ofinduction Ls a very strong and useful device for provingtheorems. Aproof by
shhe elimbing a ludder with nfinite number of steps. In climbing a ladder, we have to climb the first
climbed. In the similar
1ntof steps and having climbed any one flight, the next flight can also be show it to be true for
mtriner, to prove uny staternent by muthematical induction, first we must
H=lndl that whenever it is true for n=k. it is ulso true for n=k+1.

SOLVEDEXAMPLES

Fxample I. Show by induction that the sum of first n odd natural numbers is n.
Solution. Lct P{n): 1+3 + 5+ ..... + (2n - 1) = n ...(1)
Iollows : PUSItive
thm,ifr,, -...,be the
integers a and b
is
successive remainders, we have
0<r <b the sequence
Dividig b by(Dividing a by bl
|Dividing r, by remainder r;l
(Dividing r, by remainder rl
remainder ral
0<r, <Tn-1
Since r;>>r3 .. is a. set of
0<r,1<n
a inite number of steps decreasing
i.e., we must non-negative
Thus. obtain integers,
some r,.,= this process must terminate
0.
Tus. we se have (a, b) = (b, r) = ( r)=.. =
(,
Hence. g.c.d. of a and b is rn -»)=rn
[By theorem 1]
SOLVED EXAMPLES
Example 1. Find the g.c.d. of 858 and 325
and express it in the form m. 858 +n. 325.
Solution. We have 858 =325.2 + 208 [M.D.U. July 2006]
...(1)
325 = 208.1 + 117 (Dividing 585 by 325]
...(2) [Dividing 325 by remainder 208)
208 = 117.1 + 91
...(3) (Dividing 208 by remainder 117]
117 = 91.1 + 26 ...(4) (Dividing 117 by remainder 91]
91 = 26.3 + 13 ...(5) [Dividing 91by remainder 26]
26 = 13.2
2cd. of 58and 325 is 13.
302
From (5), 13 = 91-26.3
=91-(117-91.1)3
-91.4 - i17.3
=(208- 117. 1)4-117.3
=208.4- 117.7
wmuinder 11/front23
208.4- (325 -- 208.1)7 |Putting the value nf
= 208, 1l- (325).7 remainter;
he value nf
(858- 325.2)11 -825.7 (Putting
=858. 11- 325.29
=858.11 -325(29)
1l, n 23.
Thus n.325, where m=
l3 = m,858 + linar IhrAta
of8and49. Also express il us
Example 2. Find (28, 49) ¿.e., ge.d.
these two numbers.
Solution, We have 49 =29. 1 + 21
28 = 21.1+7
21 =7.3 +0
g.c.d of 28 and 49 = (28, 49) = 7.
7= 28 - 21.1
Also,
= 28- (49 - 28)
= 28.(2)-49.(1)
=-1.
=28. n + 49.n when m= 2, n
express it in the form 252m + 595n
Example 3. Find the g.c.d. of 595 and 252 and
[M.D.U. July 2009, Jar. 8
Solution. We have 595 =2.252 +91 ...(1)
252 = 2.91 + 70 ...(2) |Dividing 252 àN r e m 9
91 =1.70 +21 .(3) |Dividing 91 br rems
70 =3.21 +7 ...(4)
21 =7.3
g.c.d. of 595 and 252 is 7.
From (4), 7=70-3.21
=70-3(91- 1.70) |Puttingthe vahc of remii
= 70-3.91+3.70
=4.70 -3.91
=4 {252-2.91] -3.91
o2
Putting the vaiuco t o i e
4.252 - 11.91
=4.252 11 |595-- 2.252!
Putting the vale of r e t
.;8ERIHEORY + 22.252
=4.252- 11.595
11.595
= 26.252 -
7=252 m + 595 n, where m
= 26, n =- 11.
and 657.
T h u s ,
Find the l.c.m of 306
Example
4.
know
that
We
Solution. = a. b
(a, b). [a, b]
a.b 1
la, b] =
(a, b)
proceed as follows
of 306 and 657, we
find g.c.d.
Now,
to 657 =306.2 + 45
306 = 45.6 + 36
45 = 36.1 + 9
36 = 9.4

of 306 andl657 =(306, 657)=9

g.c.d.
Hence 306 x 657
= 22338.
[306, 657] =
From (1),
g.c.d. of na and no isn times the
For n >0, prove that (na, nb) = nla, b), i.e.,
Example 5.
gedofa and b.
integers
Solution. Let (a, b) = d; (na, nb)
= fand x, y be any two
f= (na, nb)
Now,
= smallest positive value of x. na +y . no
f=n (smallest positive value of xa +yb)
= nla, b) = nd

Hence
(na, nb) =n(a, b).
-b is either l or 2 if (a, b) = 1.
Example 6. Show that g.c.d. of a+ b and a
Solution. Let fbe the g.c.d. of (a + b, a -b)
iLe., f= (a+b, a-b)
Then there exists integers m and n such that
f=m (a + b)+ nla -b)
= (m + n)a + (n -n
= m,a + n,6, where m, m + n, n, = m -n
But (a, b)= 1, therefore f=1
Again if a=b, then (a., a) = 1.e., a = I
Then (a +b, a-b) = (2, 0) = 2
Hence the g.c.d. is either 1 or 2.
Example 7. I(a, ) . the
Solution. Here

Let which innplies q

q°ia and qd/

qd i ia.b) ie. gd s a common tactor ofa and d
qd íd or q/lwhich is possible only when q 1.
Hence

Remark. If (a.b) =d and ife is an integer such that e/a, e/b then e/d.
Example 8. If cia, clb and
that (a, b)=c.
Solution, Since c/a, therefore there exists an integer a, such that

Again since c/d, therefore there exists an integer b, such that

b=co, .2)

Alsoit is given that

(a,, b,) = 1
Thus there exists integerst and ysuch that
a, + b,y =1
Multiplying both sides by c, we get
a,Ct + b,cy =c
ax + by =c IUsing (1) and (2)
(a,b) = C.
Example 9. Prove that there are no pairs of integers x, y satisfying
x+y = 100 and(x, y)= 3.
Solution. If possible, let there exist integers x, y satisfying
*+y = 100
and (r,y) = 3.
Then 3/x and 3/y > 3/(* +y) 3/100, which is not possible.
Thus our assumption is wrong.
Hence there exist no integers x, y satisfying
* + y=100 and (x,y)=3.
In thi8 CAse
i bi8 a iultiple of m and esch number u or b is said o bs a residue of th
oLher, ais called incongruent to b modulo m if m%(a
Por example, both 31 - b).
and 7Jeaye the same remainder 3, when divided by 4
31 =7mod 4) [: 41(31 --7
Similarly, 3 5(mod 8) (: 8143-{-5)H
33 9 (mod 4) [: 4 | (33-91
Also, 19 is not congruont to 3 (mod 5). I: 5 %(19-3)
SOLVED EXAMPLES
Example 1, Finda such. that a 7 (mod 5).
Solution. If a =7 (mod 5), then
a-7= 5k, where kis any integer.
Putting k= 0, 1, 2,3,..., - 1, -2, - 3, ... successively, we get
a-7= 0, 5, 10, 15, .., - 5, - 10, 15, ....
a=7, 12, 17, 22, ..., 2, 3, - 8,..
..1
Hence all the integers in (1) are congruent to 7 (mod 5).
Example 2. Find the least positive integer (mod 11) to which 282 is congruent
Solution. By actual division, we have
282 = 11(25)+ 7
Hence 7 is the required least positive integer such that
282 =7 (mod 11).
Example 3. Ifa is odd, show that a² = l (nod 8).
Solution. Since a is odd, thus it can be written as
a = 2k + 1, where k e Z
a² = (2k + 1) = 4k2 + 4k + 1
= 4k (k + 1) + 1
Now we know that the product of
two consecutive integers is
az = 4(2m) + divisible by 2! i.e., 2.
Or 1=8m +1
a'-1 = 8m
8/(a'1) ’ a' =1(mod 8).
Example 4. Find the remainder on
by 12. dividing the sum 1! +2!+3!+4!
+5!+...t 100
Solution. We have 4! = 24 = 2 x 12
12/ 4 ! or 4! =0 (mod 12)
Similarly, 5! = 5. 4 !is multiple of 12
5! =0 (mod 12 ) and
so on.
integer l schthat.

Bing 1
divides By def. of
diwisibility)
the remainder in the diuision of 2 by 7,
x a m p l o
B. Find
We have
2 =2(mod 7)
solution,
22 4 (mod 7)
.1)
2% 8(mod7)
g4 =1(mod 7) ...2) (: When &is divided by 7, the remainder is 1]
power 6, we get
Ruising ((2)to .3)
(2%)6 =1i (mod 7) 24 1(mod 7)
we have
Multiplying
() and (3),
220 4 (mod 7)
remainder when
220 is divided by 7.
:
is the
Thus 4 that (n- 1) ! =0(mod n).
composite and n>4, prove
Example 6.
Ifn is composite, all its
that (n -1) ! is divisible byn. Since n is
Solution.
We have to provedivisible
by n. only
1) !. Hence it is 4) because there is
lactors are
in (n congruent to0 (mod
n=4, then 3! is not factors in (n- 1)!!
tis true only for n>4. If composite numbers
will have their
After 4, allthe + d) =c (mod m.
ne factor of 4in 3!. b= d (mod m), show that lu ...1)
and
Example 7. If(u +
b)= c(mod. m)
m) ...(2)
+b} =c (mod
Solution. We have (a
b =d (mod m)
and ...(3)

congruence (2)from (1), we have

Subtracting
(modm)
a= lc-d)
of (3), we have
Adding d on both sides m).
a+d c(mod m) that ad =c(mod
b = d(mod
m), show
m) and (ab-c) ...1)
Fxample 8. If ab c(mod therefore m/
m),
Solution. Since ab =c(mod
ub-c = mh ...(2)

therefore
m/( b - d )
Also jnct h d(mod m), b=d+ lm
h-d =lm
s d m o d m)
\ample , NAe that 9-0(nod 64).
Noution. Wehave to ahow that
9 0(nnod 64)
eis divsble by 64 for all n
utmg1 )3! 8 9 64, whieh is divisible by 64
f ) 0mod 64)
fn) 0(mod 64) for n 1
Suppose fn)0(mod 64) for some n i.e., f(n) is a
multiple of 64 for
f) = 64k, where k is any integer some n
('hanging n into (n + 1)in fn), we have
fn+ 1) = 32n +1)+28 (n + 1)9
= 32n +4- 8n - 17
=32. 32 + 2 -8n- 17
=9 (32n +28n -9)
+ 64n + 64
=9 (64k) + 64n + 64
fln + 1) = 64 (9k + (n +
1)] (From (1)
64/f(n + 1)
Or
fn + 1) =0 (mod 64),
By principle of
whenever f(n)=0(mod 64)
mathematical induction, the result is
Hence, fn) =32n +2-8n -9 true for all n.
=0
(mod 64) for all n.
Example 10.
m., then prove that aIfa =b (mod m), a
=b (mod m). Also=b(mod m,) and m= m,m,] i.e.,
prove the converse. mis L.C.M. ofm, and
Solution. Since a=b (mod
m,) and a =b (mod
m)
m,lla- b) and m,l(a
.. u-b is a -b)
commonmultiple of m, and m:
But (m1 ,ml= mi.e., mis the
.:. a-b is a least common multiple of m, and my:
multiple of m.
BER T H E O R Y
BC.A. -108
m/(a -b)
a=b (mod m).
Converse. Siince a=b(mod m) and m=(m,,mal
m/(a-b) and m,lm and ml m
m, /(a - b) and m,l(a-b)
a=b(mod m) and a=b (mod m,).
Example 11. Ifa =b(mod m), then (a, m) =(b, m).
Solution. Let b =a+ m for some integer q.
Since (a, m)/a and. (a, m) /m
.From (1), (a, m) /b and hence (a, m) / (b, m)
Similarly, we can prove that (b, m) / (a, m).
Hence (a, m) = (b, m).
EXE
...(1)
congruent.
L Find the least (mod 7) to which 286is
positive integer congruent.
2 Fi n d which 335 is
Ithe least positive integer (mod 11) to 17).
satisty x =7(mod
List all integers x in the range
l s x s 1 0 0that
congruences
r=l(mod 4
pair of
4 Write to the
equivalent to remainder
a gle congruence that is
single by 6leave
the same
3. Show that divided
its cube when
solutinn
SOLVED EXAMPLES
ENampie 1. Do the following congruence p088ess a
(mod 35) (iü) 135x6(mod 10)
(a} 84* l6
We know that the congruence ax h (mod
Soution. m) has a
divides b. solution
(mod 35)
(2) The given congruence is 84x m16
Here a= 84, b 16, m = 35
d= (a, m) = (84, 35) =7
lgc.d. of 84 and
Nowd (=7)does not divides b (= 16). 35,=7
Thus the congruence is 84x =16 (mod 35) does not possess a solutien
(iü) The given congruence is 135x =6 (mod 10).
Here a= 135, b = 6, m = 10
d= (a, m) = (135, 10) = 5
lg.c.d. of (135 and 10)=3
Now d (= 5)does not divides b ( 6)
Thus congruence 135x =6(mod 10) does not possess a solution.
Example 2. Solve the following congruences :
(i) 3x +2 0(mod 7)
(ii)13x= 10 (mod 28) (iüü) 51%=32 (mod7).

Solution. (i) The given congruence is

3x + 2 =0(mod 7)
3x =-2(mod 7)
Or

Here a=3, b=-2, m=7

Now, d = (a, m) =(3, 7) =1 solution.)

(1)exists and is unique (i.e., there is only one
Thus the solution of congruence (d=1

2)
Here d(= 1) dividesb (= - ..3)

=2(mod 7)
3x tuo
adding the
Now that
RHS. so
0= 14 (mod 7) multiple of
mon
Also, suitable
on L.H.S, and a
written
Note this step. Ois
a get cancelled. D=1
since(8,
(COngruences,

we have 3,
Adding (2)and (3),
[Cancelling

(mod 7)
3x = 12
Id(imod 7)is the solution of 3r + 2a 0(mod 7)
r e q u i r e d
solution is x 4(mod 7),
Hence,
the

congruence is 13r 10 (mod 28)

given
m 28
The
10,
i) 13,
28) =1
lere
a = d = (a,m)= (13,
divides b(= 10)
) and is unique. :d1
Now
d
solution
of given congruence exists
(mod28)
13r = 10
the
Thus

Now
224 (mod 28)
0
Also,

and ((2),
1 we have
g(1) (mod 28)
A d d i n g

13x = 234 [Cancelling 13,since (13,28) =I|

28)
x= 18(mod
required solution.
x=18(mod 28) is the
(mod 7)
congruence
is 5l: 32
given
i) The m=7
32,
b = =1
Here a =51, d = (a, m)= (51,
7) [:d= 1)
incongruent solution.
one
congruence
has one and only ..(1)

given
Thusthe (mod 7) ...(2)
51x =32
Now 0 =70(mod7)
Also,
and (2), we have
Adding (1) (mod 7) (51, 7) = l]
51x = 102 [Cancelling 51 since

t =2(mod 7)
solution.
2007, July 2006]
incongruent
required
7) is the [M.D.U. Jan.
Hence x = 2(mod congruence 15x
= 12 (mod
21I).

Example 3.
Solve the ..(1)
congruence is
Solution. The given
(mod 21)
15x = l2
and 2l = 3]
m = 21 (g.c.d. of15
Here a = 15. b =12,
(15, 21)= 3 solutions
d = (a, m)=
incongruent

in allthree [ : d=3]
and there are
solution
Thus the given Congruen ce hasa
imod 21) ...(2)

By cancellation law. (1)becomes

7) all natural
m) fornumbers,
5x =4 (mod then a =b(mod x]
[::Ifax= br(mod mx),
MATTIEMATIC5 FOR HCA.
tseve

Abo, 021 (mod 7)

Adding (2) and(3), we have
Sx 25 (mod7)
x 5(mod 7)
ICancelling 5, since (6,7) 1
Putting h0, 1, 2in (4), we have x=5, 12, 19
Hence x= 5, 12, 19 (mod 21) are the three .4)
linear congruence. incongruent solutions (mod 21)
of the
Example 4. Solve the following congruence givon
222x 12 (mod 18)
Solution. The given congruence is (M.D.U. July 2009, Jun.
222x
20041
12 (mod 18)
Here a = 222, b= 12, m= 18
d = (a, m)=(222, 18) =6
Now. d (=6) divides b (= 12) Ig.c.d. of 222 und 18
=61
Thus the given congruence has a
solution and there are in all
6
incongruent solutions.
Now, 222x = 12 (mod 18) (: d=6)
Also, 222 = 18.12 + 6 ..1)
L.e., 222 --6 = 18.12
18/(222-6)
222x =6x (mod 18)
Using (2), congruence (1) reduces to6x = 12
(mod 18) ..2)
x =2(mod 3)
x-2 = 3k x=3k +2
Putting k=0, 1,2,3, 4, 5 in (3), we have ..3)

x =2,5. 8, 11, 14, 17.

Ilence x= 2,5, 8, 11, 14, 17 (mod 18) are
CORgruence. six incongruent solutions (mod 18) of the
given
Example 5. Find the least positive incongruent solution
of 7x =5 (mod 256).
Solution. The given congruence is
7x =5(mod 256) ...1)
lHere u=7, b=5, mn = 256
d =(a, m)=(7,256) = 1
Now, dl= l} divides b {=5)
Ihus the given congruence (1)has onlv one incongruent
solution.
.2
256 = 7 A - 4

7=41-3

=31-1

1 =4-31

= 4 - - 4 1 , 1

=42-71

= 2 5 6 - 7 5 5 2 - 7 1

= 2 . 2 3 6 - 7 7 2 - 7

=236.2-773

7-73
1=236.2 -
JLiplying by 3, we have -7-365
3 =235 10,
7-365 =3 od236

Tz=5 (mod 256

is given b
solution of
Thsthe
0 =512 moi25

have
i1ing 6) and7, we =14 mod 256
z
incoDgruent mod 263
solution EXERCSE 115
gives the least positive
7=147

stdee the, follouing COngruerces:

13r (mod )

00|
|AM. DU, duly
ANSWERS
. 3
( i )No
tu) No 4.
. () No

3. 6. 4
33
5. 6. 12, 19, 6i, 8. 10

7. 4, 1i, 18,26, 32 10. x2+ 6k, wherek =0, 1, 2,... 8

12. ) 18 (i)40 (i) 42 (iv) A1
x 2 0 +294, where
k 0, 1, 2, 3, 4.

11.13. CRYPTOLOGY

We know that the secret messages have been sent from ancient time to the present
time. Classically, these messages used for secret communication in military affairs, electronic
technique which make messages
banking diplomacy. It is an interesting unintelligible
everyoneand
except the intended receiver. The discipline devoted to secrecy systems is calleito
cryplology
Some Important Terms

1. Cryptography : Cryptography is the part of cryptology which deals with ds

implementation of secrecy systems.
2. Cryptanalysis : This is aimed at breaking these systems.
3. Encryption : It is the process of making a message secret.
4. Decryption : It is the process of Converting a secret message to its original form.
5. Plain text :A message which is to be converted into secret message is called plain
text.
Now, an important question arises in our mind as to how can we encrypt a message to
make the message secret.

One of the earliest known method for encryption was given by Julius Caesar which is
known as Caesur's Cipher Encryption method which is given below :
I1.13.1. Caesar's Cipher Encryption Method
In this process, a text message can be encoded into a secret message by shifting eaCn
letter to three letters forward in the alphabets. The encrypted version of the messtye
information is called cipher text and scheme used for encryption is called cipher.
Caesar's Cipher Eneryption Method :
t o r

Steps each letter by an integer 9to 25

Replace

1.
letter in the English alphabets. For ezampis, relac Abyo, Bry 1, an4 Ztboy
Step

the value of each integer pby(p +3) mÀ 24.

Replace

2. in
S t e p
Step3. Replace the integer by letter alphabet on th tasis of its praitirn, eg.0 by
Z.
and 25 by
A. 1by B
encrypted version of the mesBage"HO# ARE YOU sing the
Example1, What
is the
Cipherencryption method.

messageis "HOW ARE YOU

Solution.
The given
integers frorm Oto 25, based on íts position
Replace
the lettersinthe message by
Step 1.
e E n g l i s h .a l p h a b e t s .

becomes 714 22 0 174 24 14 20

m e s s a g e
in2 (1)
Then,
each integer p by (p
+3) mod 26.
replace
Step 2. Now, 23
Then we have
10 17 25 3207 117
message, which is :
producesthe encrypted
Translating
this back to letters
Step 3. "KRZDUH BRX
Cipher.
we learnt the method
of encryption by Caesar's
above example, message,
Remark.
In the decrypt the encrypted
our mind as to how can we
question arises in method given below:
Now, the Cipher Decryption
with the help of Caesar's
Khich can
be done Method:
Decryption
Caesar's Cipher Method :
IL13.2. Decryption
Cipher value is based on
its position of
Steps for Caesar's 25 whose
integer 0 to Z by 25.
each letter by an example, replace A
by 0, B by 1 and
Step 1. Replace For
English alphabets.
letter in the
each integer pby
(p -3) mod 26
value of position.
Step 2. Replace alphabet on the
basis of its
integer by letter in
Step 3. Replace the
by Z. Caesar's
by A, 1 by B and 25 encryptedby using
For example, 0 was
message "KRZ
DUH BRX which
Dxample 2. Decrypt
the
...(1)
Cipher encryption method. DUH BRX"
is "KRZ based on its
Solution, The encrypted message 0 to 25,
message by
an integer
the given
Step 1. Replace each letter of
Pstion of letter in the English alphabets. 23
10 17 25 3 207 117
Then, message (1) becomes
mod 26
Step 2. Now, replace each integer p by(p -3)
Then, we have 174 24 14 20
7 14 22 0
326 MATHEMATICS FOR
BCA, - 108
Example 6. Encrypt the message "HARD WORK " by using
f(p)=(3p + 7) mod 26. encryption function
Solution. The given message is HARD WORK"
Slep 1. Replace each letter by an integer 0to 25, based
on its ..1)
English alphabets. position of letter
in the
Then, message (1) becomes 7017 3 22 14 17 10
.(2)
Step 2. Now, replace each integer p by (3p + 7)
mod 26.
Then, 7 is replaced by (3.7 +7) (mod 26) =2
0 is replaced by (3.0 + 7)(mod 26)
7
17 is replaced by (3.17 + 7) (mod
26) =6
3 is replaced by (3.3 +7)
(mod 26) = 16
22 is replaced by (3.22 +7) (mod
26) =21
14 is replaced by (3.14 + 7)
(mod 26) - 23
17 is replaced by(3.17 +7)
(mod 26) =6
10 is replaced by (3.10 + 7)
(mod 26) =11
Thus, message (2) becomes 27
6 16 21 23 6 11
Step 3. Translating this
back to letters produces the encrypted message,
"CHGQ VXGL' which is:
Now, the guestion arises in
our mind is that how
encrypted by ap +b (mod 26), where we can decrypt the
(a, 26) = 1. Before message
finding this we have to find which is
aa =1 (mod 26), where
a is the inverse of a
Example 7. Find out the inverse of in mod 26.
3 in mod 26.
Solution. Let 3a =1 (mod 26)
Here ..(1)
(3, 26) =1 and 1/1
So, (1) has a solution.
Now, 26 = 8.3 + 2
and
3 = 1.2+ 1

1=3--1.2
1=3-1.(26-8.3) =9.31.26
Putting the value of 1 in
equation (1), we get
3 =9.3 -1.26 (mod 26)
a =9(mod 26).

for Affine Transformation Decryption Method,

of a (mod
F i n d
out the inverse 26) and denote it by a.
1.
Step
eplace
each letter by an integer 0to 25 whose value is
based on its of
step
2. in the English
letter
alphabets. For example,
replace Aby 0, Bby 1andposition
Z. by 25
Replace v a l u e of each integer p by a (p -b)(mod 26)

Step3.

k e p l a c e
the integer by letter in alphabet on the basis of its position. For exanple
Step
4. li by B and 25 by Z.
Oby A,
message "CHGÌ VXGL which is encrypted by using
Example
8. Decryptthe
f(p) = (3p + 7) (mod 26).
Solution. Herea = 3

case, first of. all our aim is to find inverse of 3(mod 26).
In this
Step1. ...1)
3a =1 (mod 26)
Let
(3, 26) =1 and 1/1
Here
solution.
So,.(1) has a
26 = 8.3 + 2
Now,
3 = 1.2 +1
d
1 =3-1.2

1=3-1.(26-8.3) =9.3 -1.26

equation (1), we get

Putting the value of 1in
26)
3a =9.3-1.26 (mod
a =9(mod 26)
3a =9.3 (mod 26)
7) (mod 26)
Now, decryption formula is 9 (p
=9p- 63(mod 26)
26) of
= 9p + 15 (mod position
based on its
0 to 25 whose value is
Step 2. Replace each letter by an integer
iAters in the English alphabets
Then, message "CHGQ VXGL" becomes
276 16 21 236 11

Step 3. Now, replace pby(9p +15)(mod 26).

"Then, (mnod 26) =7
2is replaced by (9.2+ 15)
é of P
for p-1) ep i8
an odd
Step 3. each prime
1 and Z numerical andcis an
for 25. Replace each P=Cd (mod p) value Cby the
Step 4.Set numerical value of formula
of
collection of all these
message into letters.
when Example
p= 101
9. Find For example
Afor 0. Bfog
ande =3 areout the original letters is the original
giuen. message of "14 17 17message.
Solution. Here 27 11 17 65
Step 1. We shall encrypted message is 14 17 17 27 76 7 76 14:
find the inverse 11 17 65 76 7 76 14
Let x be of 3(mod 100)
inverse of 3(mod
100)
Then
3x
= 1 (mod
We know that 1 = 100)
100 --33.3. Then (1) ..1)
becomes
3x = 100 -33.3 (mod
100)