Please visit our website for 1.

latest edition of books & updated information. Integers

www.vislonpune.com
Please review us on Multi le Choice Questions 1 Mark Questions .

1. If a I b we say that a is a
a. divisor of b b. multiple of b
divisor of a d. none of these

2. If (a, m) = 1 = (b, m), then

Available Books a. (ab, m) = 0 b. (ab, m) = 1
+ Computer Science + General Science Biotechnology Management (ab, m) 0 d. none of these

+ Engineering + Junior College + Entrance Guide Diploma 3. If a, b, c are Integers such that a I bc and (a, b) = 1, then
a. cla b. bc I a
c. alc d. none of these
4. GCD of 243 and 198 is
Molecular Biology
a. 8 b. 1

d.
Business Intelligence
5. The value of 15 mod 3 is?
a. 1 b.
c. 3 d. 2

Advanced Relatiorul 6. If a I b and a I c then

J)atgbgse Managentetg
a. a I bc b. cla
wan
c. d. bla
7. The quotient of —144and -12 Is
Innovaion Throughout a. -12 b. 12
c. 16 d. —16
VISION PUBLICATIONS
39/1, Budhwar Peth, Appa BarwantChowk, Pune-411002. Ph. No. 8830238610
[email protected] [email protected] ww•w.visionpune.com S.Y. Mel Groups and Coding Theory Integers
uston
E.) B.Sc. I BCA I BBA (Compuor ApplJcün) I M.8c. Comp. Sol.) I MCA I MCMI Diploma I Engineering
S.Y. "-l •nd Coding Theory Integers
VISION
8. Determine the partitions of the set {3, 4, 5, 6, 7} from the following subsets. S.Y. M-I Groups and Coding Theory Integers
a. (3.5). {3.6, 7). (4.5.6) Answer the followin 1 Mark Questions
Marks for these Questions may vary from 1 to 2.

c. (3.4, 6), {7) I. Give an exampleof a relationon a set A = {1, 2, 3} which Is reflexive,
(5.6). (5.7) symmetric but not transltlve. (Apri12017)
Solution
9. The linear comblnatlon of gcd(243, 198)= 9 can be written as
Since A = ( I, 2, 3} then the relation
a. (243) (9) + (198) (-11)
b. (243) + (198) (11) is both reflexive and symmetric, but not transitive.
c. (243) (11) + (198) (9)
d. (198) + (243) (-11) but (1, 3) e R.

10. The inverse of 7 modulo 26 is? R is not transitive.

a. 12 b. 14
2. If a, b and c are integers such that a I b, b I c, then prove that a I c.
d. 20
(April2017)
11. The linear combination of gcd(10, 11) = 1 can be written as Solution
a. Since a, be Z and a I b, b lc
b. (10) + (1) (11) .•.3 kl, k2E Z such that
c. (10) + (2) (11) b = aki, c = bk2

d. (1) (10) + c = bk2

(11)
= (akD k2
12. Euclid's algorithm Is used for finding
.c=ak : k = kik2e Z
a. LCM of two numbers
. a Ic by definition of divisibility.
b. GCD of two numbers
3. Which elements of (Z, •) satisfy x2= x? (April2017)
c. LCM of more than two numbers
Solution
d. GCD of more than two numbers
Since (Z, •) is a group with multiplication.
13. If GCD of two numbers Is 1, then the two numbers are said to be wherez, = {i, i, S, a, S)

a. Co-prime numbers
=9 (mod6)
b. Prine
? = 16 —a(mod 6)
c. Rational numbers
Convosite numbers . x = T, S, satisfies x
S.Y. Theory• Integers
VISION
O.
S.Y. Mel Groups and Coding Theory Integers
4. addition table for Z modulo 4. (October 2015)
—bc = a (mc)
f« Z = (ö. i. . }nndulo4 is
.,öiää %al bcV c EZ
(April2015)
8. Write addition table for (Z3, +3).
Solution
Z3 = {6, i, i} and +3 addition modulo 3.

5. Show thatno two Integersexist satisfying: (October 2015)

x + y = 200 and (x,y)=7.
Answer the followin 5 Marks Questions .
Sirre x + y = 200 (1) Marks for these Questions may vary from 4 to 5.

—7/x.7/y 1. Let Z be the set of all Integers. Given a, b Z, define a b If a— b is an even

Integer. Then prove that is an equivalence relation. (April2017)
by &finition of divisibility 3 integers kl, k2 such that
Solution
2
If a, b e Z then the relation is defined by
equation ( I ) gives 7 kl + 7 k: = 200
a b iff a —b is an even integer.
a—a=Oiseven V ae Z
200
—
3 two integers whose sum is a rational number Hence there are no two integers such . a —a V aeZ is reflexive.
Now,-a —b a—b is an even integer.
tha x + y = 200 and (x, y) = 7.
b —a = —(a—b) is also even integer.
6. If c I a •b and (b, c) = 1, then prove c I a. (October2015)
—is symmetric.
gcd (b. c)= 1 .•.3 integers m and n such that bm+ I
Lastly, if a b and b c
abm + acn
a b is even integer and b —c is even integer.
Since c ab c I abrn, also c I acn
a —c = (a —b) + (b —c) = even + even = even integer.
c f abm + acn— c I a
. a—c
7. If a I b prove that a I bc for any Integer c. (April2015)
Solution is transitive.
Hence is an equivalence relation on Z.
If alb then by definition of divisibility.
3 m e Z such that b = am
—bc = (am)c for c EZ
S.Y. Groups and Coding Theory • • Integers S.Y. M.I Groups and Coding Theory Integers "8ton
U1810N

2. Show that 4999 and 1109are relativelyprime. Also find m and n such that
4999m + 1109n 1. (April2017)
axbs =
Here a -4999 and b = 1109
(ab) (xs) + I
First we find g.c.d. of a and b by using Euclidean algorithm.
Applying division algorithm successively. till we get zero remainder as gcd (ab,c)
4999 = 1109x4+563 (1) 4. Find the greatest common dlvlsor d of 7677 and 4647. Hence find integers m
1109= 563x1+546 (11) and n such that:d = 7677m + 4647m (October2016)
563 = 546x1+ 17 Solution
546=17x32+2 We have,
17= 2x8+1 7677 = 4647 x 1 + 3030
(9)

2 4647 = I + 1617 (8)

The last non-zero remainderis I. .(7)
3030= 1413
b) = 1 i.e. gcd (4999. 1109) = I = d (6)
1617= +204
a and b are relatively prime.
(5)
Now d —I = 1413= 189
(4)
= 17-(546-17x32Jx8 by(1V) 204 =
= -8x546+257x17 (3)
189= 12+9
= -8 x 546+ 257 [563-546] by (2)
15 =
= 257x (1)
= 257x 563-265 by (11)
= -265x 563
4647) = 3
= -265 x 1109+522[4999- 1109x 4]
Now from (l)
= 522 + (-2353) x 1109
=4999
(By using (2))
where m = 522 and n = —2353

Let a, b, c e Z
(October2016)
3.
If gcd(a, c) = gcd(b, c) = 1, then prove that gcd(ab, c) = 1.
(By using (3))

Solution
(1)
gcd(a,c) = 1sax +cy = l, x,yeZ
(2)
gcd(b, c) = bs+ct = 1.s,teZ = 189x2-[204- (By using (4))

From (1) and (2)

ax = I—cy,
On multiplication, ax • bs = (1 —cy) (1 —ct)
S.Y. "-l Groups and Coding Theory Integers

[1413-204 x 6) x 27-204 x 25 (By using (5)) S.Y. Groups and Coding Theory • 1-9 Integers

1413x 27-204 x 162- 204x 25 42 x 16-222 x 3

187 = (708-222x 3) x 16-222x3 (Using(3))
1413x 27-(1617- 1413* 187 (By using (6)) 708 x 16 - 222 x 51
1413 x 27 - 1617 x 187 + 1413 x 187 = 708 x (Using (4))
1413x 214- 187
(3030- 187 (By using (7)) (7260- 1638x 4) x 118- 1638 (Using
= 3030x214- 1617 x 187 = 7260 (118) + 1638(-523)

(By using (8)) 6. Find the greatest common dlvlsor d of 6162 and 1213. Hence find Integers m
4647 x 401 + 3030 x 401 and n such that: d = 6162 m + 1213 n (October2015)
3030x 615- Solutlon
[7677-4647 x x 615- 4647x 401 (By using (9)) First, we find g.c.d. 'd' of
3 7677x 615-4647 x 615-4647 x 401 a = 6162 and b = 1213 by using Euclidean algorithm
Apply Division Algorithm, to 6162 and 1213. we have
3 7677x 615-4647 x 1016
6162 = (1213) (5) + 97
3 7677 x 615 +4647 x (-1016)
Here remainder = r = 97 0,
Here m z 615 and n = —1016
apply Division algorithm to 1213 and 97
5. Find greatest common dlvlsor (gcd) of 7260 and 1638. Express It In the form we get 1213 97 (12) +49 (2)
7260 m + 1638 n where m and n are Integers. (Apr//2016) Again apply Division algorithm to 97 and 49, we have
SolutJon 97 49 (J) + 48 (3)
Using Euclidean Algorithm. Apply Division algorithm to 49 and 48. we get
7260 z 1638x 4+ 708 (5) 49 = 48 (J) +1 (4)
1638z 7002+222 Lastly 48 = 1 (48) +0 (5)
(4)
.•.g.c.d. 'd' of 6162 and 1213 is L
708* 2220+42 (3)
d = I = (6162, 1213) i.e. these integers are relatively prime. Now, we find mand n.
222 12 (2)
for
42. 12x 3+6 (1) d = J z 49-48 by (4)
12 -49 - (97-491 by (3)
% (72"), 1638) 6 -97+2 (49)
To find integers m and n we consider --97 +211213-9702))by (2)
6 42-02>0) 20213) + (-25) 97
(Using (J))
42 - (222-42 x (Using (2))
- by (1)
6162 (-25) + 1213 (127)
O,
Integers "8101
S.Y. u-l Groups and Coding Theory
t.to S.Y. WI Groups and Coding Theory
Integers
and only If 3x + 4y Is
= 6162 m + 1213 n. 9. Let R be relatlondeflnedon set of Integers.xRy If (April2015)
dlvlslble by 7. Show that R Is an equivalence relatlon.
m = —25.n 127
Solution
7. If a b(mod m) Since R is relation on set of integers Z defined as
(October 2015)
c d(mod m) xRye 3x + 4y is divisible by 7.
then prove: i.e. 3x +4y = 7k, k e Z or 7 1(3x +4y)
ax + cy = bx + dy(mod m) R is reflecxive: Since 3x + 4x = 7x is divisible by 7
Solution • xRx R is reflexive.
If a z b m) and c E d (mod m) R is symmetric: If xRy 3x + 4y = 7k
m I (a b) and m I (c —d) Consider 3y + 4x
. a —b = rnkl. c —d= mk2for kl, Z = 7 (x + y)—7kby(i)
(1)
Consider (ax + cy) —(bx + dy) = 7 (x + y—k)
= (a —b)x + (c d)y
. 7 1(3y + 4x) —yRx
= mklX+ mkzv by (l) R is symmetric.
= + k2Y)
R is transitive: Let xRy and yRz
= mk k = klx + Z —3x+4y = 7kand
m I [(ax + cy) —(bx + dy)J
•.3X+4z = (7k—4y)+(7m—3y)
. ax + cy bx + dy (mod m).
8. Find g.c.d. (greatest common divisor) of 2210 and 357. Express g.c.d. In the 7 1(3x + 4z) —xRz
form 2210 m + 357 n. (Apri/2015) R is transitive.
Solution
Hence R is an equivalence relation on Z
Using Euclidean Algorithm
2210 =
10. Prove that a = b (mod n) If and only If a and b have same remainder r,
(2)
O r < n when dlvlded by n. (April2015)
357 = 17 (1) Solution
68= Let a = b (mod n)
. (2210, 357) By definition, a b is divisible by n.
To find integers m and n we consider. i.e., a—b = knforsome integerk (1)
17 357-68 x 5 (From Suppose r is the remainder left after dividing b by n.
= (From Then by division algorithm,
b = nq+r,OSr<n
(2)
From a = b + kn = nq + r + kn = n (q + k) + r
m
S.Y. "-l Groups and Coding Theory 1-12 Integers

By division algorithm, r is the remainder left after dividing a by n as q + k e Z.

So. both a and b have the sarne remainder. Groups

Conversely. let a and b have the same remainder r when divided by n.

By division algorithm,
Multi le Choice Questions 1 Mark Questions .
a = nql + r
OSr < n
b = nqz+r
Is not a blnary operatlon on the set of natural numbers.
• a —b= n (q —O s n la—b a = b (mod n)
a. addition b. product
11. Show that Nß Is Irrational for any prime p. (April 2015)
Solution c. difference d. algorithm
If p is prime and suppose that '{p is rational number 2. Is not a binary operation on Z.
(1) a. b.
2
c. d.
p= a2= pb2 (2)
3. If a * (b * c) = (a * b) V a, b, ce S then * Is said to be on S.
pla2 by definition of divisibility
a. closed b. commutative
ph.a
c. associative d. distributive
pla by Euclid's Lemma
4. (S, t) Is said to be seml-group If
2 2
a2 = p k a. * is binary operation on S b. * is associative on S

pb2 = p2k2 by (l) c. both a and b d. S has an identity element with respect to *

b2 = pk 2 5. For any set S thereexlst e e S such thata * e = e * a = a, Va e S then e Is

p I b.b pib called
. pla and plb pl(a, b) (a, b) 2 p > I (p is prime) a. an unique element b. an identity element
Which contradicts to (a, b) = I c. an inverse element d. a proper element
Hence •Cp is an irrational number. 6. For any set S If a = b * a, Va, be S then * Is sald to be on S.
a. closed b. associative
c. distributive d. commutative

S.Y. Groups and Coding Theory 2-1 Groups

UISION
UISION
018101
S.Y. Groups and Coding Theory 2-2 Groups 2-3 Groups
S.Y. Groups and Coding Theory
Let • be a binary operation on R denned by a • b a + b + 2ab thon 7 •(1/2)=
iii. a*
a. 133 b. 14.s —existence of identity element.
element e
d. 163 Example: (Z, e) is a monoid with identity (Apri/2016)
—l}
o. Let G —1,l, —l}Is group under multlpllcatlon then the Inverse of I Is 2. Consider the set A = {1, —l, 1,
of each element.
with usual multlpllcatlon. Write Inverse
b. -1 Solution

d. -i The multiplication table for set

ab i} is
9. Let G = and a • b V a, b e C. The Inverse of a Is

a- lla b. 2.1a
c. Ya d. 41a
10. Which sentence Is true?
a. Set of all matrices forms a group under multiplication
b. Set of all rational negative numbers forms a group under multiplication Since I is multiplicative identity in A
c. Set of all non-singular matrices forms a group under multiplication Element Its Inverse
1
1

d. Both (b) and (c)

i
11. What Is the Identity element In the group G = {2, 4, 6, 8) under multlpllcatlon
modulo 10? set of all positive rational numbers. Define operation * as:
3. Let Q* be (October2015)
b. 9
ab
d. 12
3
Find Identity element for this operation.
Solution
Answer the followin 1 Mark Questions . ab
Marks for these Ouestions may vary from 1 tö 2. Since Q* = set of all positive rational numbers and a * b
(Apri/2017)
1. Define monold. Give an example. Let e be identity element w.r.t. * then
Solution
to be monoid if,
A non-empty set G with binary operation * is said ae
a 1 s e = 3 is identity element.
i. a *be G Va. be G i.e.*is closure.
ii.
i.e. * is associative.
S.Y. "-I Groups and Coding Theory
Groups
V18ton S.Y. Groups and Coding Theory Groups
4. Define: Semlgroup. Give one example.
(April2015)
Solution Existence of identity element
A semigroup is a non-empty set G together V a e Z, we have to find e e Z such that
with an associative binary operation * defined on G.
i.e., G is a non-empty set with binary operation
* satisfying
i. a GVa,beG a +e—2=a
ii.

e.g., (Q, +) is a semigoup. e = 2 is an identity element of G.

Existence of inverse element

Answer the followin 5 Marks Questions . For a e Z, we have to find b e Z such that a * b = e
Marks for these Ouestions may vary from4 to 5.
•.a+b-2=2
1. Let G = Z, the set of Integers. Definethe binary operation as, a * b = a + b —
2, a, b E Z. Show that is an abellan group. (Apri12017)
Solution 4 a is an inverse of a in Z.

Binary operation * defined on Z = G is By definition of a group; (Z, *) is a group.

Commutativeproperty

Closure property For a, be Z, a = a +b—2

Let a, b E Z, then • + is commutative in Z.

. closure property hold.

. Commutative property hold.
Associativeproperty
. (G, *) (Z, *) is an abelian group.
For a, b. cc Z
Consider a * (b * c)= a * (b + c—2)
2. Let G = Q —{1}, set of all rational numbers excludlng 1. Define the binary
operatlonon G as, for any a, b e G, a * b = a + b—ab. Show that <G, Is an
= a +(b+c—2)—2 abellan group. (October 2016)
-2 Solution
= (a * b) + c—2 Since G = Q —{ I } and binary operation * is
a* b = a + b —ab for a, be G.
i. Let a, b e G, then a * b = a + b —ab e G
Associativity holds.
a, be G 4 l, I Then a + b —ab* I
G is closed under *
Groups
Theory
S.Y. MAGroups and Coding Theory 2-6 Groups S.Y. Mel Groups and Coding
associative.
ii. Let a. b. ce G, then a • (b • c) = Associative: Matrix multiplication is
e O,e e R
a + (b + c —bc)- + c- bc) Identity: Suppose E = e G be an identity element,
iii.
(a + b -ab) + c + (a + b- ab)c
e G, we have AE = A EA
Then for a matrix A =
(a + b- ab) * c

is associative
iii. Let e e G be identity element of G; e e G 1

2xe = x 2e

1 1

. OE G is identify. Thus, identity element is E = 1 1

iv. Let b G be inverse of a e G then

=
Inverse: Suppose B = e G is the inverse of A, so that, AB

1 1

b G is inverse of 'a' in G.
1

Thus, (G, is a group.

1 1
For a. be G, a *b = a +b—ab
r 2xy 2xyl =
= b + a—ba=b*a 2xyJ 1 1
ä ä
(G, is an abelian group.
1
3. Show that the set: 2xy —
(Apri12016)
Is an abellan group under usual matrlx 1 1

multlpllcatlon. 1 1
e G is inverse of
Solution 4x 4x

i. Closure: Let A = are the elements of G, x, y O,x, y e R

2xy 2xy
Then AB = . (G, is a group. It is easy to verify that AB = BA so that G is abelian.
2xy 2xy
because 2xy O, 2xy e R as x, y O, x, y e R
. G is closed under multiplication.
S.Y. Mel Groups
Ond COdlng Theory
4. Lot z bo 0,
of Integers. Define
an operation S,Y. WI Groups and Coding Theory • Groups
a •b a + b —6. Show on Z
that Z Is an abellan (October2015)
Solution %(10 a) is an inverse of a in Z.
group w.r.t.
Operation defined on . (Z. *) ig a group.
Z as
a Commutative law: For any a, b e Z
a + b —5 for a,
be Z
c. Closure property:
Let a. b e Z
. a • b •a + b —5
e Z C.i a + b —5 is an
integer)
. closure property hold.
* is commutative
Associative property: Let
a. b, c e Z (Z, *) is an abelian group.
Consider a (b c) a (b + 5. Let QI = Q —{1}. Define on QI as a b = a + b— ab Y a, b e 01. Prove that
c —5)
(QI, In an abellan group. (April2015)
Solution
Let Q = Q— (l) and * is defined as a * b = a + b —abV a, be QI

i. Let a, be QI thena b = a+ b —abe QI

because a, be Q, a * l, I
. Associativity holds,
then a + 1 a *be QI
Existence of identity element:
QI is closed under *
For a e Z. we have to find ee Z such that a *
e=a ii. Consider a * (b + c) = a * (b + c —bc)
Consider.a e a = a + (b + c —bc) —a (b + c —bc)
adding —aon both sides = (a + b —ab) + c —c (a + b —ab)
wc get. e —5
.e 5 is identity element of G.
Existence of inverse element: t. * is associative.

iii. Let e e QI be identity e* I

Va Z, we have to find b e Z such that a * b = e

a +e—ae=a

be 10 —a
0 e Qt is identity.
La bE Q eQ H APTER 3
Finite Groups and Subgroups
Multi le Choice Questions 1 Mark Questions .
. (Q, isa
I. Let (H, be a subgroup of (G, then whlch of the following Is Incorrect?
a. Ha and aH both are subsets of G for a E G.

= b •a Va.bE Q b. HiffaH=H.
c. If G is non Abelian then every subgroup of G is non abelian.
* is in QI
d. None.
(Q • ) is abeliangoup.
2. If H = (O,3} and G = (Z, +6)then how many dlstrlct left cosets of H In G?
a. 1

3. Whlch of the following Is Incorrect?

a. Let (H, *) be a subgroupof (G, *) then for a E G, aH = (a * Wh E H) is called left
coset of H in G.
b. No left or right coset can be empty,
c. a and b both
d. None
4. If G = (Z, +5),how many generators of the cycllc group G?
a. 2 b. 3

5. Every cyclic group Is

VISION a. a group with finite order b. a group with prime order
c. a non Abelian group d. an Abelian group

S.Y. M.I Groups and Codlng

Theory • • Finite Groups and
Sub...
vrtlon
and Sub...
3-3 Flnltø Groups
Theory • (Apri/2016)
S.Y. Groups and Coding 3.
S.Y. Groups and Coding Theory • • Finite Groups and Sub...
of a cyclic group of order
6. Which of the following Is not subgroup of (R, 4)? 3. Find the numberof generators
Solution
b. Then G
cyclic group of order 3.
Let G = <a > be a

.O(G)= n = 3
of order n,
7.
23 =<a> be a cyclic group
But we know that G
G iff (m, n) —l.
b. (1 34 5) Then amis generator of
c. (1 234 5)
Since (1,3) = 1, (2,3)
4 2
8. 1 S, thon f can be written as The generators are a, a
G = 2.
a. (1 23 4) b. (1 34 2) The number of generators of
Questions •
d. (432 1) Answer the followin 5 Marks
4 to 5. vary from
Marks for these Questions may
find the order
Answer the followln 1 Mark Questions : given permutationIs even or odd. Also
Marks for these Questions may vary trom 1 to 2. 1. Determinewhetherthe 123456789 (April2017)
1.
ofcando-l.o= 2 3 4 5 1 6 7 9 8
Consider tho group G (o, a, a2, as) with usual multlpllcatlon. Wrlto order of
each element In G. Solution
(October2016) as
product of transportation
Solution first we express permutation o as
Since G (e, a. a 2. a)) is a group with usual multiplication. (1 23456789 h
• ' G is cyclic
group generated by 'at with a4 e.
34516798)
= (1 2345) (6) (7) (8 9) — product of disjoint cycles
Element Order of element number of transportations)
= (15) (1 3) (12) (8 9) — product of 5 (odd
4 •.0 is odd permutation.
a 2 l, by interchanging ISt and IIDdrows and then rearranging as
Now we find c
a 4 (23451679
234567 8 9)
2. Find order of tho followlng permutatlon:o (1 2) (3 4 5) (6 7 8) In So.
(October 2016) = 1 23 4 67 9
Solution
2. If G = (4+4) and H ä}. (April2017)
Since given pennutatjon is
Wrlteall leftcosets of subgroup H In group G. Show that G/H Is a group.
Solutlon
which is a product of disjoint cycles of lengths 2, 3, 3 respectively.
Given G = (Z, +4)is a group and
. order of o lcm (lengths of disjoint cycles)
(ö, i) is a subset ofZ4
•lcm (2.3, 3) —6
8.7.

S.Y. and Coding Theory F'mi&

10
. 5 geærates a subgoup of 3 = 2 elenznts.

. subgroups of ZIOare
(0. 5}, (0. 2.4, 6, 8}. zt+

G = sa Eft(r ä+Handä+H 4. Let G = (Z4,+)and H Write all the cosets of G related to its
of H in G
2016)
Solution
of in G•'H is. The coets of H in G are as follows:

Ö+H=ä+H
Gerve an e.Jaæms in thS table a19
lies in G / H- There are two distinct coset of H in G and thee are H +
. G 'Hisagoup. H + or H + H + S.
5. Let a and ß are permutations In Ss:
3. FIM an of (ZIO, +).
(October 2016)
(1 234 (1 234 (October 2015)

Siæe +) is a cyclic groupwith geæratorI. find:

Now, 2 E 7-10, (2, 10)= 2 l. aoß
2 gærates a subgroup of i10 = 5 eleænts ßoc

IV. Check whethera Is even or odd.

Also, gcd(4, 10)= gcd(6, 10)= gcd(8, 10)= 2 Solution
Since
a = k3 1 4
5 2)' ߯k2 4 1 3 5) are permutationsin S*
3E gcd(3,10)= I
i. aoß=u 2
. 3 generatesa subgoup of 10 = 10 3 5 4)

ii. (1234
10) = ZIO
and gcd (5, 10) = 5
2 413 $ (1 234 $
1234 5) = k 3 142 5)ess.
We write a as a product
of transpositions.
HAPTER
3-6 • Groups end Sub...
Theory
and Coding
(1 3 4 5 2) -4 Proåjctofdisjointcycle. Groups

(13) (14) (15) (t 2) -4 Productof transpositions.

Questions •
Product of an even number (i.e. 4) le Choice Questions 1 Mark
Multi
is even pamutation.
1. Hamming distance betweenx and Y is
6. o Is on A y 1010001
(1, 2, 3, 4, 5, 6) defined by (April2015) x 1100010,
b. 3
62)
d. 5
Write o as product of transpositions. Find order of o. Find
2. Hamming weight of the 1001101 Is
(1 23456', a. 2 b. 3

c. 1
.•.o •(1 34) (25 6B pro&ctofdisjoint cycles.... ..... ..... ..
3. Consider (2, 6) encoding function e
(I. 3). (l. 4). (2.5). (2.6) of transpositions
0) = 000000
Now. oret ofo = o(c) = I c m of lengths of disjoint cycles
e(10) = 101010
• l.c.m. (3.3.) by (i)
-3 e(ll) = 111000
...I(3 5416 (1 2345 6) what will be minimum distance of e?
2345 6)=k4 61325)
a. 2 b. 3
1

4. In theRSA system,takep = 3, q = 11 and d = 7 then public key (e, n) Is

a. (e, n) = (33.3) b. (e, n) (3, 33)

c. (e, n) = (3, 21)
5. Which letter replaces the letter N when the transformation
f(x) = 7x + 5(mod 26) Is used for encryption.
UISION a. b. s
d.

S.Y. GroupsandCodingTheory •
• Groups and Coding Theory
Theory 018101
Groups and Coding
S.Y. and Coding Theory • Groups and Coding Theory Groups and Coding Theory •
S.Y.
minimum distance 3, then how many
with
If •e'Is a (2,5) encoding function
6. If the encrypted letter is P under transformation f(x) = 5x + 7 (mod 26), what (Apri120f7)
Is the original letter?
3.
detect? How many errors can It correct?
errors can this code
Solution
3
function with minimum distance
Since 'e' is a (2,5) encoding
error.
7. In RSA algorithm, = In terms of p and q. %e can detects k = 3 or fewer
k + 1.
iff its minimum distance is atleast
that
error if it is necessary
code e will detect 2 or fewer error and e can correct 3 or fewer
Thus
codeword is 3 2 2k + l.
Answer the followin 1 Mark Questions : the minimum distance between any two
Mans fot thæe Questons may vary from 7 to 2.

1. If etc.B2 BS is the encoding function defined by parity check matrix H as. . it can correct single error.
distance between the words
4. Define weight of a word. Find the Hamming (Apri12017)
H=
010
1

001
0 0 then find eH(10)and eH(11). (April2019)
Solution
is defined as the number of 1's in
Solution Let x e Bnthen hammingweight is denoted as w(x) or IXIand
Here. nrssage length = m = 2 x.
n
Also, if x, y e B , then the hamming distance between x and y is
codeword length = n = 5
ö (x, y) = The number of positions were the codeword x and y differs
parity bits = p = n —m
=5-2

eH(lO) = 10 Xl 5. Statewhetherthe followingstatementIs true or false and justify. "The parity

check matrlx(nx r) defines a group code: Bm-4 Bn, If m + r = n".
= 10110 Solutlon
and = 11
True.
= 11101 If there is a parity check matrix of order n x r where r = n —m i.e. n = m + r
2. Find hamming distance betweenthe words x = 10011011and y = 11001110. then 3 an encoding function (i.e. group code)
(October 2018) : as
Solution
eH(b) : bib2 ... bmXIX2... xr
1001 101 1
e 11001 1 10 V b = bb
1 bme Bm
01010101 6. If 'e' Is (2, 6) encoding function with minimum
errors can 'e' detect? How many errors can
distance 4, then how many
The hamming distance is the weight w(x e y) be corrected?
Solution (April 2016)
so, w(x O y) = 4
Since e is (2, 6) encoding function
with minimum distance 4.
Coding Theory
Groups and
and Coding Theory
S.Y. M-IGroups
=0
S.Y. M-l Groups and Coding Theory • Groups and Coding Theory Xl = ().l + 0.0+0.1
But An (m. n) encoding function e: Bm-9 BOcan detect k or fewer enor iff its minimum distance X2=o.0+o.1+0.1=0
is atleast k+l. = 0.0+0.1+0.1=0
Since the minimum distance is 4. e(000) = 000000
x2 x3
So we have 4 k+l or k S I Now e(001) = 001
Thus the code will detect one or fewer errors. where = 0.1 +0.0+ 1.1 —I
+0.1 + 1.1=1
Answer the followin 5 Marks Questions . X3=o.o+0.1 + 1.1= 1
Marks tor these Questions may vary from 4 to 5.
1 1
1 Similarly, we can find
1. Let H = 1 be a parity check matrix. Determine(2, 4) code e(010) = 010011
1
e(100) = 100100
(October 2018)
Solution
e(101) = 101011

m = message length = 2, n = codeword length = 4

— n —m= parity bits = B3--.-.-.->B 6
is a group code of ew.
"BE", where p = 23, q =
We have set of messages = {00, 01, 10, 11} 41 and
methodto encode the message
3. Apply RSA (April2018)
e(b) s = 41.
Solution
e(00) = 0000
Since p = 23, q = 41 and s = 41
= 0101
Let m = pq
1011
= 23x 41 = 943
e(ll) = 1110
and n = (p- 1) (q-
These are required codewords.
Now we find t such that
2. Find group code eH•.B3 B6 corresponding to parity check matrix H:
1 st = I (mod n)
1
1
1 Given that s = 41
1 1
(April2018) Using Euclidean algorithm, we compute
1 O O
880=41 +19
1
1
Solution
we have {000, 001, 010, 100. 110, 101, 011, 111) Also
e(000) = 000 X2X3
Theory
SS. o, Groups and Coding Theory •
• Groups and Cuing
Coetg Theory •nd Coding Theory S.Y.
= 19x 13 + x 41
x 41 + (880—41 x 21) (13)

is closest to x' so here

1 (—279)x 41 (tmd SSO) Minö(x0).xo = i.e. we now choose the codeword which
. t —279 , xo is mimmum.
(mod 880). x(2) is closest to Xt since distance of x and
Now to emode nrssage BE. Maximum likelihood decoding function d(x0 = 01
& = 10011
4. Let +4: BS be the encoding function defined as: (April2018)
e(00) 00000, e(01) = 01110, e(10) = 10101, e(ll) = 11011. 10011 1

Decode the following words relative to maximum likelihood decoding

function where: 100111
11101 1

To show that C is a goup code where C = {00000.

We need to show that
C is a subgroup i.e., it is sufficient to show the closure -1001101
property.
We prepare a table
e 00000 01110 10101 11011 xo =
00000 00000 01110 10101 11011
01110 01110 00000 11011 10101 = I OIOOOI
10101 10101 11011 00000 01110
11011 11011 10101 01110
so here x(4) IS closest to xt, since dist ance of
00000
Since closure property is satisfied therefore C is subgroup Choosethe codewordwhich is closest to and
and hence it is a group code. is minimum.
Now, Let = 00000, = 01110, = 11011 Maximum likelihood decoding function d(xt) = 11.

We compute xo for IS i' 4 5. Use RSA methodwlth pairs of letters and p = 19,q = 23,s = 41 to encode the
ö(xfl) message word "GO". (April2017)
Solution
Here p = 19, q = 23, s = 41.
6(xC), xo = I x(2) x, I = 19 x 23 = 437
100001 p, q are primes

ö(xf3), xo = I O x, I =
-1010111 = 396
s=41
• • Groups and Coding Theory S.Y. M-I Groups and CodJngTheory • and
S.Y. &oup•
Now. the tt*ssage GO'
E
x2=O.l+ =I
-26xG+O
14 e(01) = 01011
-170 Next e(10) = 10 x,
So •GO' is number 170.
form of integer, where = 1.1 + 0.0 = O
Now we to calculate ( 170)'i (mod 437), get the encoded message in the
1.1+ 1.0=1
We have.
437) 1.0+0.1
(170)2
381(mod437) . e(10) = 10110
(170)'
437) Similarly verify e(11) -11101
z 248 (mod 437) The composition table for in BSfor given 4 elements
e 00000 01011 10110 11101
96 (mod 437) 00000 00000 01011 10110 11101
01011 01011 00000 11101 10110
E96x 170 10110 10110 11101 00000 01011
E 16320E 151 (mod 437) 11101 11101 10110 01011
Observe that every element in this composition table is again an elenrnt of the set
The encoded nrssage received is 151.
10 Set {00000, is a subgroup of BS.
011 It is a group code.
6. If: H = 1 0 0 Is a paritycheck matrix, determinethe (April2017)
010 Now the minimum weight of non—zerocode word is 3.
01 The minimum distance of group code is 3.
group code eH : B2 -+ B5. Show that It Is a group code. Find the minimum 7. Use RSA methodtripletsof lettersto encode the message 'RUN', wrere
distance. p = 17, q = 41, s = 19 with usual notation. (October 2016)
Solution Solutlon
Wehave (00, 01, 10, 11} Given p = 17, q = 41 ands = 19
Then e(OO)= 00 x2 x3 m=pq= 17 x 41 = 697
where —0.1+0.0=0 then n = = •(pq) = p. q are
= 0.1+0.1 -o

Now, the message 'RUN' = RU + N

eco = 00000
= (R x 26 + U) + N
Now e(Ol) = 01 x2 x3
where = 0.1 + 1.0 = O = 475
S.Y. M-tGroups and Coding Theory • 4-10 Groups and Coding Theory
so. RUN is number 475
Now, we need to calculate 475' = 475 19(mod 697)
Notes
475 2 = 225625 494 (mod 697)
. (475)4 4942 86 (mod 697)

(475)8 862 z 7396 E 426 (mod 697)

. (475) i6 4262 256 (mod 697)
E 256 X 494 X 475
z 152 (mod 697)
The encoded message received is 152.
8. In RSA cryptosystem, take p = 79, q =89 and d = 119, Determinethe publlc
key (e, n). (April2016)
Solution
n =pq
n = 79 x 89 = 7031
Q(n) = (p-l) (q —l)
= 78 x 88 = 6864
Since d and é(n) are co-prime.
i.e. de = I mod (+ (n))
(1)
119 e = I mod (6864)
that
We can solve (1) by using Euclid algorithm, there exist an integer a and b such
119a+6864b=1.
Using algorithm we get, e = a = 2711 and b = —47
Hence the public key (e, n) = (2711, 7031)

UISION