Stucor Ma8551 PL
Uploaded by
Madhu MathiStucor Ma8551 PL
Uploaded by
Madhu MathiDOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
UNIT–I GROUPS AND RINGS
PART A
1 Define a subgroup and give one proper subgroup of Z 6 , . [NOV/DEC 19]
Let G be a group and H is a non empty subset of G. If H is a group under the same binary
operation of G then H is a subgroup of G.
H 0,2,4 or K 0,3 are the proper subgroups of Z 6 , .
ab
2 Find the identity element under defined by a b , for all a, b R.
2
ae
a e*a a *e e 2.
2
ab
1
3 Prove that a group is abelian if and only if a 1b1 a, b G.
By closure property a, b G ab G
Let x ab , then x(ab) e
1
By associative property ( xa)b e
post multiply by b-1 ( xa )bb eb
1 1
( xa ) b 1
post multiply by a-1 ( xa )a b a
1 1 1
x b 1a 1
Assume that G is an abelian group
ab b1a 1 a 1b1
1
( Gis abelian) `
Conversely assume that ab a b a, b G
1 1 1
To Prove : G is abelian
ab ab a b b a
1 1 1 1 1 1 1 1 1
ba .
Thus G is abelian
4 Prove that if every element of the group is its own inverse, then G is abelian.
If every element of the group is its own inverse, then a-1 = a for all aG
ab ab a, b G
1
b 1a 1 ab (ab) =b a
-1 -1 1
ba ab b =b and a =a
-1 -1
Therefore G is abelian.
5 Define a group homomorphism with an example.
Let (G, ) and ( S , ) be two groups. A mapping f: G S is said to be a group homomorphism
if for any a, b G,
f(a b) = f(a) f(b).
Example: Consider f : R ,. R, where f(x) = log10(x)
for any a, b R+ , f(ab) = log10(ab) = log10(a) + log10(b) = f(a) + f(b).
Therefore f(x) is a group homomorphism.
Page 1 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
6 Consider two groups G and G where G={Z, +} and G={zm/m=0,± 1,± 2 ,± 3,..., }. Let
: Z {z m / m is an integer} defined by m 2m where mZ. Prove that is
homomorphism.
m 2m where mZ
m r 2mr 2m 2r m r
Hence is homomorphism.
7 Let f : (G, ) (G, ) be an isomorphism. If G is an abelian group then prove that
G is also an abelian group.
Let a, b G.
Then there exists a, b G,such that f (a) = a & f (b) = b
a b f (a)+ f (b) f (a b) = f (b a) f (b) + f (a) b a
Hence G is an abelian group.
8 Let G = Z12 , 12 , Find the left cosets of H [0],[4],[8] and show that the distinct left
cosets of H forms a partition of G.
Z12 [0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11] ; H [0],[4],[8]
[0] H [0],[4],[8] H [4] H [8] H
[1] H [1],[5],[9] [5] H [9] H
[2] H [2],[6],[10] [6] H [10] H
[3] H [3],[7],[11] [7] H [11] H
G H ([1] H ) ([2] H ) ([3] H )
9 Define cyclic group.
A group (G,*) is said to be cyclic if there exists an element aG such that every element of G
can be written as some power of „a‟.
10 State any two properties of cyclic group.
1. Every subgroup of a cyclic group is cyclic.
2. Suppose that G is a finite cyclic group of order m. Let „ a‟ be a generator of G. Suppose j
∈ Z, then aj is a generator of G if and only if gcd(j, m) = 1.
11 Give an example for a cyclic group along with its generator. [NOV/DEC 19]
G 1,1, i,i is a cyclic group with generators i and i .
12 Show that every cyclic group is abelian.
Let (G,*) be a cyclic group with „a‟ as generator
x, y G x a , y a x y a a a mn anm y x
m n m n
13 Prove that the multiplicative group Z 7* {1, 2, 3, 4, 5, 6} is cyclic and find its generator.
The element 3 is a cyclic generator since
31 mod 7 3
32 mod 7 9 mod 7 2
33 mod 7 (32 3) mod 7 (2 3) mod 7 6 mod 7 6
34 mod 7 (33 3) mod 7 (6 3) mod 7 18mod 7 4
Page 2 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
35 mod 7 (34 3) mod 7 (4 3) mod 7 12mod 7 5
36 mod 7 (35 3) mod 7 (5 3) mod 7 15mod 7 1
whereas the element 4 is not a generator as only generates the cyclic subgroup {1, 2, 4} of Z 7*
since
41 mod 7 4
4 2 mod 7 16 mod 7 2
4 3 mod 7 ( 4 2 4) mod 7 ( 2 4) mod 7 1
Since every element of Z 7* {1, 2, 3, 4, 5, 6} can be written in powers of 3, Z 7* {1, 2, 3, 4, 5, 6}
is a cyclic group.
14 Define Ring.
A ring R, , is a non-empty set R with two binary operations + and normally called
addition and multiplication, defined on R such that R is closed under + and , that is for
a, b R , a b R and a b R , and where the following axioms are satisfied for all
a, b, c R :
1. R1 : R, is an abelian group, that is
a. (a b) c a (b c) (Associativity under + is satisfied)
b. For each a R , there exists an identity 0 R where
a0 0a a (R has an additive Identity)
c. For each a R , there exists an a R where
a (a) (a) a 0 (Each element in R has an additive inverse)
d. a b b a (Addition is commutative)
2. R 2 : (ab)c a(bc) (Associativity under is satisfied)
3. R3 : a(b c) ab ac (Left and Right Distributive laws are satisfied)
(a b)c ac bc
In short, An algebraic system R, , is called a ring if it satisfies the following properties
(i) R, is an abelian group
(ii) R, is a semi group
(iii) R satisfies distributive law
15 Define a Commutative ring.
A commutative ring is a ring R that satisfies ab ba for all a, b R (it is commutative under
multiplication). Note that rings are always commutative under addition.
16 Define Zero divisors of a ring with example.
A ring (R, +, ) is said to be ring with zero divisors, if there exists non zero elements a, b in
R, such that ab = 0. Such elements are called zero divisors.
Example: 0,1,2,3,4,5, , is a
6 6
ring and 2 6 3 0. However 2 0 & 3 0.
2 and 3 are zero divisors of the ring.
17 Define Subring with example.
Let (R, +, ) be a ring. A non – empty subset S of R is called a subring of R , if (S, +, ) is a
ring.
Example: The ring of rational numbers is a subring of the ring of real numbers.
18 Define Integral Domain.
A commutative ring R with a unit element is called an integral domain if R has no zero
divisors.
Page 3 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
19 Define (a) Unit of a ring (b) Division Ring.
(a) Let R be a ring with unity 1 0 . An element u R is a unit of R if it has a multiplicative
inverse in R. (i.e), for u R , there exists an element u 1 R where u u 1 u 1 u 1 R .
(b) If every non-zero element of R is a unit, then R is a division ring.
(OR)
A ring R with unit element having atleast two elements is called a division ring, if every non-
zero element of R possesses their multiplicative inverse.
20 Define field in an algebraic system with example.
A commutative ring (F, +, ) which has more than one element such that every nonzero
element of F has a multiplicative inverse in F is called a field.
(OR)
A commutative division ring is called a field.
Examples:
The set of real numbers R and set of rational numbers Q under the operations of addition + and
multiplication are fields.
However, the set of integers Z under addition + and multiplication is not a field since the only
non-zero elements that are units is -1 and 1.
For example, the integer 2 has no multiplicative inverse since ½ Z.
PART B
1i) Let G be the set of all rigid motions of a equilateral triangle. Identify the elements of G.
Show that it is a non-abelian group of order six. [NOV/DEC 19]
Solution:
Consider an equilateral triangle with vertices named as 1, 2, 3.
Let 0, 1 , 2 denote the rotations of the triangle in the counter clockwise direction about an
axis through the centre of the triangle and perpendicular to the plane of the triangle for an
angle of 120, 240, 360 respectively.
These rotations are called rigid motions of the triangle and are given by
1 2 3 1 2 3 1 2 3
0 , 1 , 2 .
1 2 3 3 1 2 2 3 1
Let r1, r2 , r3 denote the reflections of the equilateral triangle along the lines joining vertices
3,1,2 and the mid-points of the opposite sides.
Each reflection is a 3-dimensional rigid motion.
1 2 3 1 2 3 1 2 3
r1 , r2 , r3
2 1 3 1 3 2 3 2 1
Let G = {0, 1 , 2, r1, r2 , r3}.
Define binary operations on G as follows
1 2 3
1r1 = r3G
3 2 1
Page 4 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
Cayley‟s table for G is given by
0 1 2 r1 r2 r3
0 0 1 2 r1 r2 r3
1 1 2 0 r3 r1 r2
2 2 0 1 r2 r3 r1
r1 r1 r2 r3 0 1 2
r2 r2 r3 r1 2 0 1
r3 r3 r1 r2 1 2 0
From the table it is clear that G is a group.
Note that 2 r1 r2 and r1 2 r3
2 r1 r1 2 , G is not an abelian group of order six.
0 1
1ii) Show that (M , .) is an abelian group where M={A, A2, A3, A4} with A and
1 0
“.” is the ordinary matrix multiplication. Further prove that (M , .) is isomorphic to the
abelian group (G , .) where G={1, -1, i, -i} and “.” is the ordinary multiplication.
Solution:
0 1 1 0 3 0 1 1 0
A ; A2 ; A ; A4 I
1 0 0 1 1 0 0 1
For all 1≤ m, n ≤ 4,
Am. An = Am+n = Ar where 1< r < 4 and m + n r (mod 4).
Thus . is a closure operation.
Since matrix multiplication is associative so is „.‟.
1 0
A4 I is the identity.
0 1
1 0 1
A1 A3
1 1 0
1 1 1 0
A2 A2
1 0 1
1 1 0 1
A3 A
1 1 0
1 1 1 0
A4 I A4
1 0 1
For all 1≤ m, n ≤ 4, Am. An = Am+n
= An+m
= An. Am,
so „.‟ is communicative.
(M , .) is an abelian group .
Define f: M → G such that f A i, f (A 2 ) 1 i 2 , f (A3 ) i i3 , f (A 4 ) 1 i 4
f is 1-1 and onto
Since i3 = -i = f(A3) = f (A.A2) = f(A) f(A2) = i.i2 = i3 = -i
Hence f is isomorphic from M to G.
Page 5 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
2i) Let G be a group subgroups H and K. If |G|=660, |K|=66 and KHG, what are the
possible values of |H| ? [NOV/DEC 19]
Solution:
O(K) < O(H) < O(G) and O(K) divides O(H) and O(H) divides O(G).
O(K ) = |K| = 66 = 2311.
O(G) = |G| = 660 = 223511.
|K| divides |H| and |K| < |H|
|H| = x |K| = x (2311), with x > 1
|H| divides |G| and |H| < |G|
|G| = y |H| = y x (2.3.11), with y > 1
660 = y x (2.3.11)
22.3.5.11 = y x (2.3.11)
2.5= y x ,with x > 1, y > 1
x = 2 or x = 5
When x = 2 |H| = 2 (2.3.11) =132
When x = 5 |H| =5 (2.3.11) =330.
-1
2ii) Find [100] in Z1009. [NOV/DEC 19]
Solution:
gcd(100, 1009)=1,
By Euclidean Algorithm,
1009 = 10 (100) + 9 -------------------(1)
100 = 11 (9) + 1 -------------------(2)
By (2) 1 = 100 – 11(9)
= 100 – 11 [1009 – 10(100)] (by (1))
= 100 + 110 (100) – 11(1009)
= 111(100) – 11 (1009)
= (111) (100) ( mod 1009)
[1] = [111] [100] ( mod 1009)
[100]-1 is [111] in Z1009.
2iii) Prove that every subgroup of a cyclic group is cyclic.
Proof:
Let (G,*) be the cyclic group generated by an element a G and let H be the subgroup of G.
Claim: H is cyclic
Case1: H is a trivial subgroup of G (i.e) H = G or H = {e}
If H = G or {e} then trivially H is cyclic.
Case2: H is a non - trivial subgroup of G
If not the elements of H are non-zero integral powers of a.
Since if ar H, its inverse a-r H.
Let “m” be the smallest positive integer such that am H. → (1)
Let an be any arbitrary element of H. Let q be the quotient and r be the remainder when n is
divided by m.
Then n = qm + r where 0 r < m. → (2)
Now an = aqm + r = (am)q. ar
ar = (am)- q. an = an-mq.
Since am H, (am)q H by closure property, amq H
(amq)-1 H, by existence of inverse, as H is a subgroup a-mq H
Since an H and a-mq H by closure property an-mq H ar H
Page 6 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
By (1) & (2), we get r = 0, n = mq
q
a n a mq a m .
q
Thus every element of a n H is of the form a m
Hence H is a cyclic subgroup generated by a m .
3i) a 0
Let A a R (a) Show that A is a ring under matrix addition and
0 a
multiplication (b) Prove that R is isomorphic to A.
Proof:
b 0 c 0
a For any B and C , we have
0 b 0 c ,
b 0 c 0 b c 0
BC A and
0 b 0 c 0 b c
b 0 c 0 bc 0
BC A
0 b 0 c 0 bc
b 0 b 0
Also for any B , the additiveinverse B exists such that
0 b 0 b
b 0 b 0 0 0
B (B) A.
0 b 0 b 0 0
Distributive Laws:
a 0 b 0 c 0 a 0 b c 0
A. B C
b c
. .
0 a 0 b 0 c 0 a 0
a.(b c) 0 ( a.b a.c) 0
A. B C
0 a.(b c) 0 ( a.b a.c)
a.b 0 a.c 0
0 a.b 0 a.c
a 0 b 0 a 0 c 0
A.B A.C
0 a 0 b 0 a 0 c
Similarly, (B+C).A=B.A+C.A
Thus Ais a ring.
(b) To prove isomorphism, consider a one-to-one and onto function f from R onto A defined
r 0
as follows For all r R, f : R A where f (r)
0 r
i.e., for any real number we associate a 2nd order scalar matrix.
Now for any r,s R
r s 0
f (r s)
0 r s
r 0 s 0
f (r) f (s)
0 r 0 s
Page 7 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
rs 0 r 0 s 0
f (r s) f (r) f (s)
0 rs 0 r 0 s
Thus twooperations , are preserved and f is 1 1and onto.
f is an isomorphism from R to A.
3ii) Prove that every group of prime order is cyclic.
Proof:
Let O(G) = p, where p is a prime number.
Let a (≠ e) G.
Consider a subgroup generated by a.
Let H a
O H 1 H a a H & also e H O H 1
Since H is a subgroup of G, then by Lagrange‟s theorem,
O(H)/O(G) O(H)/p
O H 1 or p p is prime
But O H 1, O H 1.
Thus O H p O(G ) G H
But H is a cyclic group, G is a cyclic group.
4i) Let (G, ◦) and (H,*) be groups with respective identities eG , eH .If f :GH is a
homomorphism, then show that
(a ) f (eG ) e H
1
(b) f (a 1 ) f (a ) a G
(c ) f (a n ) f (a ) a G and all n Z
n
(d ) f (S)is a subgroup of H for each subgroup Sof G.
Proof:
(a) eH f (eG ) f (eG ) f (eG eG ) f eG f eG
eH f eG , by right cancellation law
(b) Let a G , since G is a group, a 1 G
1
Since G is a group, a * a eG
1
By homomorphism f (a * a ) f ( eG )
f (a) f (a 1 ) eH
Hence f a 1 is the inverse of f a
1
i.e., f (a 1) f (a) a G
(c) a G and all n Z
Case(i): if n=0 then a a eG
n 0
f a0 f eG eH f a
0
f (a n ) f (a)
n
Case(ii): if n is a positive integer then
Page 8 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
a n a a a a (n times )
f a n f a a a a (n times)
f a f a f a f a
f a
n
Case (iii): if n is a negative integer , then n = -r, r >0.
f a n f a r f a 1 f a 1 f a f a
r r r n
f (a n ) f (a) a G and all n Z
n
(d) If S is a subgroup of G, then S , so f S . Let x, y f(S).
Then x = f(a), y = f(b) for some a, bS.
Since S is a subgroup of G, it follows that
a b S,
f (a) f (b) f a b f S
x y f S , so f S is closed
1
Finally, x 1 f (a) f [a 1]
a S a 1 S & f [a 1 ] f S
x 1 f S
f (S)is a subgroup of H for each subgroup Sof G.
4ii) Prove that Z n is a field if and only if n is a prime. [NOV/DEC 20]
Proof:
We have Z n 0,1, 2, n 1
We know Z n , , isa commutativering withidentity 1.
Let n be a prime, and suppose that 0 < a < n then gcd (a , n)=1
there exists integers s, t such that as + tn = 1
sa – 1= (- t) n
sa-1 is divisible by n
sa 1(mod n)
s a 1
s is the multiplicative inverse of a .
Thus a is a unit of Z n, which is consequently a field
Conversely, let Z n be a field.
So Z n is a commutative ring with identity and without zero divisions of zero.
To prove n is a prime.
if n is not a prime, then n= n1 n2, where 1 < n1 ,n2 <n. So n1 0 and n 2 0
But n1 n 2 n1n 2 n 0
n1 , n 2 are divisors of zero which contradicts the fact Zn is a field.
Hence n is a prime.
Page 9 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
5i) Prove that the set R of numbers of the form a b 2 , where a and b are integers, is a
ring with respect to ordinary addition and multiplication.
Proof:
1. Closure : Let x1 a1 b1 2 , x2 a2 b2 2 R where a1 , a2 , b1 , b2 Z
x1 x2 a1 b1 2 a2 b2 2 a1 a2 b1 b2 2 R
where a1 a2 & b1 b2 Z .
R is closed under +.
2. Associative: Let x1 a1 b1 2 , x2 a2 b2 2, x3 a3 b3 2 R where
a1 , a2 , a3 , b1 , b2 , b3 Z
x1 x2 x3 a1 b1 2 a2 b2 2 a3 b3 2
a1 a2 b1 b2 2 a3 b3 2
a1 a2 a3 b1 b2 b3 2
a1 a2 a3 b1 b2 b3 2
a1 b1 2 a2 a3 b2 b3 2
a1 b1 2 a2 b2 2 a3 b3 2 x1 x2 x3
3. Identity: 0 0 2 R
a b 2 0 0 2 (a 0) (b 0) 2 ab 2
4. Inverse: a b 2, a b 2 R
a b 2 a b 2 (a a) (b b) 2 00 2
(a) (b) 2 is the identity inverse of a b 2
5. Commutative law:
x1 x2 a1 b1 2 a2 b2 2 a1 a2 b1 b2 2
a2 a1 b2 b1 2
a2 b2 2 a1 b1 2 x2 x1
Under Multiplication
6. Closure Axioms:
x1 x2 a1 b1 2 . a2 b2 2
a1a2 2b1b2 a2b1 a1b2 2
a1a2 2b1b2 , a2b1 a1b2 Z , x1 x2 R
Page 10 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
7. Associative:
x x x
1 2 3
a1 b1 2 a2 b2 2 a3 b3 2
a1a2 2b1b2 a2b1 a1b2 2 a3 b3 2
a1a2 2b1b2 a3 2 a2b1 a1b2 b3
a1a2 2b1b2 b3 a2b1 a1b2 a3 2
x1 x2 x3
8. Distributive Laws :
x1 x2 x3 a1 b1 2 a2 b2 2 a3 b3 2
a1 b1 2 a2 a3 b2 b3 2
a1 a2 a3 2 b2 b3 b1 b1 a2 a3 b2 b3 a1 2
a1 b1 2 a2 b2 2 a1 b1 2 a3 b3 2
a1a2 a1a3 2b1b2 2b1b3 2a2b1 2a3b1 2a1b2 2a1b3
a1a2 2b1b2 a1b2 a2b1 2 a1a3 2b1b3 a1b3 a3b1 2
x1 x2 x3 x1 x2 x1 x3
x 2
x3 x1 x2 x1 x3 x1
Hence the given set is a ring.
5ii) Prove that (Q,, ) is a ring on the set of rational numbers under the binary operations
x y = x + y + 7, x y = x + y + (xy/7) for x, y Q. [NOV/DEC 19]
Proof:
1. Closure : For x, y Q, x y = x + y + 7 Q
(sum of two rational numbers is always rational)
2. Associative: x,y, z Q
(x y) z= (x + y + 7) z = (x + y + 7)+ z+7= x + (y + z + 7) +7
= x (y + z + 7)
= x (y z)
3. Identity: x, e Q, x e = x + e + 7
if e is the identity then x e = x
x= x + e + 7 e = - 7
4. Inverse: For x, x - 1 Q x x - 1 = x + x - 1 + 7
If x -1 is the inverse of x then, x x - 1 = e
x + x - 1 + 7= e (e = - 7 )
x + x - 1 + 7= - 7 x - 1 = -x - 14
5. Commutative law:
For x, y Q, x y = x + y + 7 = y + x + 7= y x
Under Multiplication
6. Closure Axioms:
For x, y Q, x y = x + y + (xy/7) Q
Page 11 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
7. Associative:
x, y, z Q , (x y) z = [x + y + (xy/7)] z
=[x + y + (xy/7)]+ z+{[x + y + (xy/7)] z}/7
= x + y + z + (xy/7) +{[xz + yz + (xyz/7)] /7}
= x + y + z + (xy/7)+ (xz/7)+(zy/7)+ (xyz/49) ----------(1)
x (y z) = x [y + z + (yz/7)]
= x +[y + z + (yz/7)] +{[y + z + (yz/7)]x}/7
= x + y + z + (yz/7) +{[y + z + (yz/7)]x}/7
= x + y + z + (xy/7)+ (xz/7)+(zy/7)+ (xyz/49) -----------(2)
From (1) and (2) , (x y) z = x (y z)
8. Distributive Laws :
x (y z) = x (y + z + 7)= x +(y + z + 7) + [x (y + z + 7)]/7
= x +y + z + 7+(xy/7)+ (xz/7)+x
(x y) (x z)= [x + y + (xy/7)] [x + z + (xz/7)]
=[x + y + (xy/7)] +[x + z + (xz/7)] +7
= x +y + z + 7+(xy/7)+ (xz/7)+x
x (y z) = (x y) (x z) Hence the given set (Q, , ) is a ring.
5iii) Show that a finite integral domain is a field
Proof:
Let {D, +, } be a finite integral domain.
Then D has a finite number of distinct elements, say a1 , a 2 , a 3 , a n .
Let a( 0) be any element of D.
Then the elements a a1,a a 2 ,a a3 ,a a n D, since D is closed under multiplication.
The elements a a1,a a 2 ,a a3 ,a a n are distinct, because if
a a i a a j D, then a a i a j 0.
But a 0. Hence a i a j 0 , since D is an integral domain i.e., a i a j , which is not true
because a1,a 2 ,a3 ,a n aredistinct elements of D.
Hence the sets a a1, a a 2 , a a 3 , a a n and a1 , a 2 , a 3 , a n are the same.
Since a D is in both sets,
let a a k a,for somek → (1)
Then a k is the unityof D, detailed as follows:
Let a j a a i, a j D → (2)
Now a j a k a k a j, by commutative property
a k a a i , by(2)
a k a ai
a a k a i , by commutative property
a a i , by (1)
a j , by(2)
Since a j is an arbitrary element of D, a k is the unityof D . Let it be denoted by 1.
Since 1 D , there exists a(0) and ai D such that a ai ai a 1
a has an inverse. Hence {D, +, } be a finite integral domain.
Page 12 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
UNIT– II FINITE FIELDS AND POLYNOMIALS
PART A
1 Define Polynomial rings.
Given a ring (R, + , . ) an expression of the form f ( x) a0 a1 x an x n where
ai R, 0 i n, is called polynomial in the indeterminant x with the coefficients from R.
Then ( R[ x], ,.) is a ring called the polynomial ring over R under the operation of addition and
multiplication given by , if f ( x) a0 a1 x an x n and g ( x) b0 b1 x bn x n
ai , bi R, 0 i n, then polynomial addition f g is given in terms of its values at the
points x, i.e., by ( f g )( x) and it is given by
n
f ( x) g ( x) ci xi c0 c1 x cn x n , where ci ai bi , 0 i n
i 0
and for polynomial multiplication fg , we have
n
( fg )( x) : f ( x) g ( x) d 0 d1 x d n x n , where d n ai bn i .
i 0
2. If f ( x ) 3 x 4 7 x 3 5 x 2 2 x 4 and g( x ) 2 x 3 8 x 2 6 x 5 are the polynomial in
Q[x], then find the value of f ( x) g( x) and f ( x) g( x).
Given that f ( x) 3x4 7 x3 5x2 2 x 4 and g ( x) 2 x3 8x2 6 x 5 , then
f ( x) g ( x) (3 0) x 4 (7 2) x3 (5 8) x 2 (2 6) x (4 5) 3x 4 9 x3 13x 2 8 x 9
& f ( x) g ( x) (3 0) x 4 (7 2) x3 (5 8) x 2 (2 6) x (4 5) 3x 4 5 x3 3x 2 3x 4
3. If f ( x ) 2 x 4 2 x 3 5 x 2 and g( x ) 5 x 2 4 x 3 are the polynomial in Q[x], then find
the value of f ( x).g( x).
f ( x).g ( x) (2 x 4 2 x3 5 x 2 ).(5 x 2 4 x 3)
10 x 6 (8 10) x5 (6 8 25) x 4 (6 20) x3 15 x 2
10 x 6 2 x5 23 x 4 14 x3 15 x 2
4. If f ( x) 3 x 4 5 x 3 4 x 2 6 x 3 and g ( x ) 4 x 3 3 x 2 2 x 1 are the polynomial in
Z7 [ x], then find the value of f ( x) g( x) and g( x) f ( x).
f ( x) g ( x) (3 0) x 4 (5 4) x3 (4 3) x 2 (6 2) x (3 1) 3 x 4 9 x3 7 x 2 8 x 4
In Z 7 [ x], f ( x) g ( x) 3x 4 2 x 3 0 x 2 x 4 3x 4 2 x 3 x 4
and f ( x) g ( x) (3 0) x 4 (5 4) x3 (4 3) x 2 (6 2) x (3 1) 3x 4 x3 x 2 4 x 2.
Therefore g ( x) f ( x) 3x 4 x3 x 2 4 x 2.
In Z 7 [ x], g ( x) f ( x) 3x 4 x 3 x 2 4 x 2 4 x 4 6 x 3 6 x 2 3x 5.
5. If f ( x) x 3 2 x 2 x 2 and g( x) x 3 x 2 x 2 are the polynomial in Z3[ x], then
find f ( x).g( x)
f ( x).g ( x) ( x3 2 x 2 x 2).( x3 x 2 x 2)
x6 (2 1) x5 (1 2 1) x4 (2 1 2 2) x3 (4 1 2) x2 (2 2) x 4
x 6 x5 4 x 4 x3 7 x 2 4
In Z 7 [ x], f ( x).g( x) x 6 x5 4 x 4 x 3 7 x 2 4 x 6 6 x 5 3 x 4 x 3 3.
Page 13 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
6. Find two non-zero polynomials f ( x ) and g( x) in Z12[ x] such that f ( x ). g( x ) 0.
Let f ( x) 3 x 2 6 x 9, g ( x) 4 x 2 8 x 4
f ( x).g ( x) (3 x 2 6 x 9).(4 x 2 8 x 4) 12 x 4 48 x 3 96 x 2 96 x 36
In Z12 [ x] , f ( x).g ( x) 0 x 4 0 x3 0 x 2 0 x 0 0
7. State factor theorem and find the factors of x 2 3 x 2 Z 6 [ x ]
If and , then ( x a) is the factor when f(x) if and only if „a ‟ is a root of
f ( x).
f ( x) x 2 3x 2 , Z 6 {[0],[1],[2],[3],[4],[5]}
f (0) (0)2 3(0) 2 2
f (1) (1)2 3(1) 2 6 0
f (2) (2)2 3(2) 2 12 0
f (3) (3)2 3(3) 2 20 2
f (4) (4)2 3(4) 2 30 0
f (5) (5)2 3(5) 2 42 0
Therefore f ( x) x 2 3x 2 in Z6 [ x] has four roots x 1, 2, 4,5.
The factors are ( x 1), ( x 2), ( x 4), ( x 5)
8. Find all the roots of f ( x ) x 2 4 x in Z12 [ x ]
Given f ( x) x 2 4 x , Z12 {[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]}
f ( x) x 2 4 x Under Z12[ x]
f (0) 02 4(0) 0 f (0) 0
f (1) (1)2 4(1) 5 f (1) 5
f (2) (2)2 4(2) 12 f (2) 12(mod 12) 0
f (3) (3)2 4(3) 21 f (3) 21(mod12) 9
f (4) (4)2 4(4) 32 f (4) 32(mod12) 8
f (5) (5)2 4(5) 45 f (5) 45(mod12) 9
f (6) (6)2 4(6) 60 f (6) 60(mod12) 0
f (7) (7)2 4(7) 77 f (7) 77(mod12) 5
f (8) (8)2 4(8) 96 f (8) 96 (mod12) 0
f (9) (9)2 4(9) 117 f (9) 117 (mod12) 9
f (10) (10)2 4(10) 140 f (10) 140( mod12) 8
f (11) (11)2 4(11) 165 f (11) 165(mod12) 9
Therefore f ( x) x 2 4 x in Z12 [ x] has four roots x 0, 2,6,8.
Page 14 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
Find all the roots of f ( x ) x 3 5 x 2 2 x 6 in Z7 [ x ] and then write f ( x ) as a product
9.
of first-degree polynomials.
f ( x) x3 5 x 2 2 x 6 , Z7 {[0],[1],[2],[3],[4],[5],[6]}
f ( x) x3 5x2 2 x 6 Under Z7[ x]
f (0) 6 f (0) 0
f (1) 1 5 2 6 14 f (1) 0
f (2) 8 20 8 6 42 f (2) 0
f (3) 27 45 6 6 84 f (3) 0
f (4) 64 80 8 6 158 f (4) 158(mod 7) 4
f (5) 125 125 10 6 266 f (5) 266(mod 7) 0
f (6) 216 180 12 6 404 f (6) 404(mod 7) 5
Therefore f ( x) x3 5 x 2 2 x 6 in Z7 [ x] has four roots x 1,3,5.
The factors are ( x 1), ( x 3), ( x 5)
In Z7 [ x], f ( x) x3 5 x 2 2 x 6 ( x 6)( x 4)( x 2)
10. Show that x 2 2 has no roots in Q[x]
x 2 2 has roots 2 and -2 which are irrational numbers. Thus 2 and -2Q.
Therefore x 2 2 has no roots in Q[x]
11. State Division Algorithm
Let F be a field and let f ( x) and g ( x) be two polynomials in F ( x) with g ( x) 0.
Then there exists unique polynomials q( x) and r ( x) such that
f ( x) q( x) g ( x) r ( x) where either r ( x) 0 (or) deg r ( x) deg g ( x)
12. State remainder theorem and What is the remainder when
is divisible by ( x 1)
If & for any field F, then f(a) is the remainder when f(x) is divided by x–a.
By remainder theorem, remainder for given is f(1).
Here .
In , .
Hence remainder is 4.
Page 15 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
13. Find quotient and remainder when g( x ) x 2 5 divides f ( x ) x 5 2 x 3 3 x 2 x 1
where f ( x),g( x) Z7[x].
x3 4 x 3
x5 0 x 4 2 x3 3 x 2 x 1
x5 0 x 4 5 x3
4 x3 3 x 2
2 4 x3 0 x 2 20 x
x 5 Quotient x3 4 x 3 and Remainder 2 x 5.
3x 2 2 x 6
3 x 2 0 x 15
2x 5
If f ( x ) 2 x 4 5 x 3 7 x 2 4 x 8 and g( x ) 2 x 1 are polynomials in Q[x] ,
14.
determine q( x )and r ( x) such that f ( x ) q( x) g( x) r ( x).
x3 3 x 2 2 x 1
2 x 4 5 x3 7 x 2 4 x 8
2 x 4 x3
6 x3 7 x 2
6 x3 3 x 2
2x 1 q(x) x3 3 x 2 2 x 1 and r(x) 9
4 x2 4 x
4 x2 2 x
2x 8
2x 1
9
15. Define g.c.d of f ( x ) and g( x)
If f ( x), g ( x) F[ x] , then h( x) F[ x] is a greatest common divisor of f ( x)and g ( x)
(i) if h( x) divides each of f ( x) and g ( x)
(i) if k ( x) F[ x] and k ( x) divides each of f ( x) and g ( x) then k ( x) divides h( x).
16. Define irreducible polynomial or prime
Let f ( x) F[ x] , with F a field and deg f ( x) 2. Then f ( x) is said to be reducible over F
if there exists g ( x), h( x) F[ x] where f ( x) g ( x)h( x) and each of g ( x), h( x) has degree 1 .
If f ( x) is not reducible, then it is called irreducible polynomial or prime.
Page 16 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
17. Determine whether x 2 x 1 is reducible over Z7 [ x]
Given that f ( x) x 2 x 1 , Z7 {[0],[1],[2],[3],[4],[5],[6]}
f ( x) x 2 x 1 Under Z7[ x]
f (0) 02 0 1 1 f (0) 1
f (1) (1)2 (1) 1 3 f (1) 3
f (2) (2)2 (2) 1 7 f (2) 7(mod 7) 0
f (3) (3)2 (3) 1 13 f (3) 13(mod 7) 6
f (4) (4)2 (4) 1 21 f (4) 21(mod 7) 0
f (5) (5)2 (5) 1 31 f (5) 31(mod 7) 3
f (6) (6)2 (6) 1 43 f (6) 43(mod 7) 1
The roots of f ( x) x2 x 1 are 2, 4
f ( x) x 2 x 1 ( x 2)( x 4)
( x 5)( x 3).
Therefore f(x) is reducible over Z7[ x]
18. Give an example for an irreducible & reducible polynomials in Z2[ x] [NOV/DEC 19]
Z2 {[0],[1]}.
Irreducible polynomial Reducible polynomial
f ( x) x 2 x 1 g ( x) x 2 x
f (0) 02 0 1 1 g (0) 02 0 0
f (1) 12 1 1 3 1 (mod 2) g (1) 12 1 2 0(mod 2)
Given an example of a polynomial that is irreducible in Q[x] and reducible in C[x].
19.
[NOV/DEC 20]
Consider the polynomial f ( x) x 2 2
Solving f ( x) 0 x2 2 0
x 2 2
x i 2
Clearly x i 2 Q , therefore f ( x) x 2 2 is irreducible in Q[x].
But x i 2 C [ x] , therefore f ( x) x 2 2 is reducible in C [x].
20. Define Characteristic of a ring with example.
Let (R, +, ) be a ring. If there is a least positive integer n such that nr = z ( the zero of R) for all
r R, then we say that R has characteristic n and write char (R) = n.
When no such integer exists, R is said to have characteristic 0.
Examples:
The ring (Z3 , +, ) has characteristic 3; (Z4, +, ) has characteristic 4;
In general, (Zn, +, . ) has characteristic n.
The rings (Z, +, . ) and (Q, + , .) both have characteristic 0.
Page 17 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
PART B
1i). If R is a ring under usual addition and multiplication, show that (R[x], +, x) is a ring of
polynomials over R.
Solution:
Let f ( x), g ( x) R[ x]. Then f ( x) g ( x), f ( x) g ( x) are also polynomials over R. Therefore
R[ x] is close with respect to addition and multiplication of polynomials.
Now let f ( x) ai xi a0 a1x a2 x 2 a3 x3 ..... am x m ..
g ( x) bi xi b0 b1x b2 x 2 b3 x3 ..... bm x m ......
h( x) ci xi c0 c1x c2 x 2 c3 x3 ..... cm x m .....
Commutativity of Addition:
f ( x) g ( x) (a0 b0 ) (a1 b1) x (a2 b2 ) x 2 ...(am bm ) x m .......
(b0 a0 ) (b1 a1) x (b2 a2 ) x 2 ...(bm am ) x m .... g ( x) f ( x)
Associative of Addition
[ f ( x) g ( x)] h( x) ai xi bi xi ci xi
ai xi bi xi ci xi f ( x) [ g ( x) h( x)]
Identity element of Addition
0( x) 0 0 x 0 x 2 ...... is the additive identity element of R[ x]
Inverse Element of Addition
f ( x) a0 a1x a2 x 2 a3 x3 ..... am x m .... is the additive inverse element of R[ x]
Associativity of Multiplication
[ f ( x) g ( x)] (a0 a1x a 2 x 2 ....)(b0 b1x b2 x 2 ....)
i
2
(d0 d1x d 2 x ....) , where di ai k bk
k 0
Now
[ f ( x) g ( x)] h( x) (d0 d1x d 2 x 2 ....) (c0 c1x c 2 x 2 ....) (e0 e1x e 2 x 2 ....) ,
where en the coeff x n in[ f ( x) g ( x)] h( x) d j ck aib j ck
Similarly, we show that the coeff x n in f ( x) [ g ( x) h( x)] aib j ck
Thus [ f ( x) g ( x)] h( x) f ( x) [ g ( x) h( x)] , since corresponding coefficients in these two
polynomials are equal.
Distributive of multiplication on addition
We have
f ( x) [ g ( x) h( x)] (a0 a1x a 2 x 2 ....)[(b0 b1x b2 x 2 ....) (c0 c1x c2 x 2 ....)]
If n is the non-negative integer, the coeff x n in f ( x) [ g ( x) h( x)]
ai (b j ck ) aib j ai ck
Coeff of xn in f ( x) g(x) Coeff of x n in f ( x)h(x)
Coeff of xn in [ f ( x) g(x) f ( x) h(x)] f ( x) g ( x) f ( x) h( x)
Similarly, we can prove right distributive law for R[ x]
Hence R[ x] is a ring.
Page 18 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
1ii) Find the remainder when f ( x) is divided by g ( x) .
(a) f ( x), g ( x) Q[ x], f ( x) x8 7 x5 4 x 4 3x3 5 x 2 4; g ( x) x 3
100 90 80 50
(b) f ( x), g ( x) Z 2 [ x], f ( x) x x x x 1; g ( x ) x 1 [NOV/DEC 20]
(a) Given f ( x) x8 7 x5 4 x4 3x3 5x2 4; g ( x) x 3
By long division
x 7 3 x 6 9 x5 34 x 4 98 x3 297 x 2 896 x 2688 ( q ( x))
x8 7 x 5 4 x 4 3 x 3 5 x 2 4
x8 3 x 7
3x7 0 x6
3x7 9 x6
9 x 6 7 x5
9 x 6 27 x5
34 x5 4 x 4
34 x5 102 x 4
x3
98 x 4 3 x3
98 x 4 294 x3
297 x3 5 x 2
297 x3 891x 2
896 x 2 0 x
896 x 2 2688 x
2688 x 4
2688 x 8064
8060 r ( x)
Remainder r ( x) 8060.
Verification:
By remainder theorem, If and , for any field F then f(a) is the remainder
when f(x) is divided by (x–a).
Remainder r ( x) (3)8 7(3)5 4(3)4 3(3)3 5(3)2 4
6561 1701 324 81 45 4 8060.
Page 19 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
(a) Given f ( x) x100 x90 x80 x50 1; g ( x) x 1
x99 x98 ... 2 x89 ... 3 x80 .... 4 x50 .....4( q( x))
x100 x90 x80 x50 1
x100 x99
x99 0 x98
x99 x98
x 1
.......
4x 1
4x 4
5( r ( x))
Remainder r ( x) 5. In Z2[ x], 5 1(mod 2) Hence remainder is 1.
Verification:
By remainder theorem, If and , for any field F then f(a) is the remainder
when f(x) is divided by (x–a).
Remainder r ( x) (1)100 (1)90 (1)80 (1)50 1 5 .
In Z2[ x], r(x) = 1. Hence remainder is 1.
2i) Find the greatest common divisor of
(i) x10 x7 x5 x 3 x 2 1 & x8 x5 x 3 1 in the ring Q[x] [NOV/DEC 19]
(ii) x 3 3 x 2 3 x 1 & x 3 2 x 1 in Z5[ x]
(i) Given f ( x) x10 x7 x5 x3 x2 1 & g(x) x8 x5 x3 1
By actual division
x2
x10 x7 x5 x3 x 2 1
10 7 5 3 2
x8 x5 x3 1 x x x 0x x 0
x3 1
x10 x7 x5 x3 x2 1 x2 ( x8 x5 x3 1) ( x3 1)
x5 1
x8 x 5 x 3 1
x8 x 5
Similarly,
x3 1 x3 1
x3 1
0
( x8 x5 x3 1) ( x3 1) ( x5 1) 0 Hence required G.C.D is ( x3 1).
Page 20 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
(ii) Given f ( x) x3 3x2 3x 1 & g(x) x3 2 x 1
By actual division
x
x3 3 x 2 3 x 1
3 2
x3 2 x 1 x 0 x 2 x 1
3x 2 x
x3 3x2 3x 1 x( x3 2 x 1) (3x 2 x)
Similarly,
2x 1
x3 0 x 2 2 x 1
x3 2 x 2 0 x
3x 2 x 3x 2 2 x 1
3x2 x 0
x 1
x3 2 x 1 (3x x)(2 x 1) ( x 1)
2
Similarly,
3x
3x2 x
3
x 1 3x 3x
3x
3x2 x ( x 1)(3x) (3x)
Similarly,
2x
x 1
x
3x
1
x 1 3x(2 x) 1
Hence required G.C.D is 1.
2ii) If f ( x) F[ x] has degree n 1 , then prove that f ( x) has at most n roots in F .
[NOV/DEC 19]
Proof:
We prove this theorem by mathematical induction on the degree f(x).
If f(x) has degree 1, then f(x) = ax + b, a, b F and a 0.
f( -a-1 b) = 0
f(x) has at least one root in F
If c1 and c2 are both roots, then
Page 21 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
f(c1 ) = a c1 + b = 0 = a c2 + b = f(c2)
By cancellation law in a ring , a c1 + b = a c2 + b a c1 = a c2
Since F is a field and a ≠ 0, we have , a c1 = a c2 c1 = c2
So f(x) has only one root in F.
Now assume that the result is true for all polynomials of degree k 1 in F[x]
Consider a polynomial f(x) of degree k + 1.
If f(x) has no roots in F, the theorem follows.
Otherwise , let rF, f(r)= 0
By factor theorem, f(x) = (x – r) g(x), where g(x) has degree k.
By the induction hypothesis,
g(x) has at most k roots in F
and f(x) has at most k + 1 roots in F.
3i) If ( F , , .) is a field and Char (F) > 0, then prove that Char(F) must be prime.
[NOV/DEC 20]
Proof:
Let Char ( F ) n 0 .
If n is not prime, we write n mk where m, k Z and 1 m n, 1 k n .
By definition of Characteristic, nu z , the zero of F.
Hence (mk )u z.
But (mk )u (u u ......u ) (u u u..... u ).(u u u..... u ) (mu )( ku )
mk summation m summation k summation
With F as field, (mu)(ku) z
(mu) z or (ku) z
Assume without loss of generality, (ku) z .
Then for each r F , kr k (ur )
(ku )r
zr z ,
contradicting the choice of n as the Char ( F ) Char ( F ) n is prime.
3ii) In Z3[ x], s( x) x x 2 Show that s(x) is irreducible over Z3 and construct the field
2
Z 3[ x]
What is the order of the field? Also Find (i) [x+2][2x+2]+[x+1] (ii) [2 x 1]1
s( x)
Solution:
Here Z3 {0,1, 2}, s( x) x 2 x 2
s (0) 2 0
s (1) 1 1 2 1(mod 3) 0
s(2) 4 2 2 8(mod3) 0
Therefore s(x) has no root in Z3 . Hence s(x) is irreducible in Z3 [x].
Z 3[ x]
Therefore is a field
s( x)
Since deg s(x) = 2 , this field has 9 elements.
This field consists of 9 different equivalence classes
Let f ( x) z3[ x] then
f ( x) q( x)( x2 x 2) r ( x), where r ( x) 0 (Or) deg r ( x) deg ( x 2 x 2) 2
deg r ( x)is 0 (or) 1
Page 22 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
r ( x) ax b and [ f ( x)] [r ( x)]
Each a and b can take 3 values
S. No Values of a and b r ( x) ax b Equivalent Classes
1 a=0 , b =0 r ( x) 0 x 0 0 [0]
2 a=0 , b =1 r ( x) 0 x 1 1 [1]
3 a=0 , b =2 r ( x) 0 x 2 2 [2]
4 a=1 , b =0 r ( x) 1x 0 x [ x]
5 a=1 , b =1 r ( x) 1x 1 x 1 [ x 1]
6 a=1 , b =2 r ( x) 1x 2 x 2 [ x 2]
7 a=2 , b =0 r ( x) 2 x 0 2 x [2 x]
8 a=2 , b =1 r ( x) 2 x 1 2 x 1 [2 x 1]
9 a=2 , b =2 r ( x) 2x 2 2x 2 [2 x 2]
Z 3 [ x]
Therefore { 0 , 1 , 2 , x , x 1 , x 2 , 2 x , 2 x 1 , 2 x 2 }
x x2
2
The order of the field is 9
(i) To find x 2 2 x 2 x 1
Now x 2 2x 2 [2 x 2 6 x 4] [2 x 2 0 x 4] [2 x 2 4] [ x]
2
2 x2 4
2
x 2 x 2 2x 2 x 4
2x x
Therefore x 2 2 x 2 x 1 x x 1 2 x 1
(ii) To Find [2 x 1]1
Now consider 2x 1 2x [4 x 2 4 x]
[ x 2 x] Since 4 1(mod 3)
[2] Since x 2 x 2(mod x 2 x 2)
[1] Since 2 1(mod 3)
[2 x 1][2 x] [1]
[2 x 1]1 [2 x]
4 Prove that a finite field has order pt , where p is prime and t Z . [NOV/DEC 19]
Proof:
Let u denote the unity and z the zero element.
Given that is a finite field and Char(F) = p, p is prime
Then S0 ={u,2u,3u, …..pu = z}is a set of p distinct element in F
If not, mu = nu for 1 m n p and (n – m)u = z with 0 < n – m < p
For any xF, (n – m)x =(n – m)ux
=[(n – m)u]x
= zx =z
this is contradiction to Char(F) = p
S0 ={u,2u,3u, …..pu = z}is a set of p distinct element in F
Page 23 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
If F = S0 , then |F| = p1 and the result as follows.
If not let aF - S0, then S1 ={ma + nu/ 0 < m, n p} is a sub set of F with | S1 | p2
If | S1 | p2 ,
then m1 a + n1 u= m2 a + n2 u with 0 < m1,m2, n1,n2 p
and at least one m1 - m2 , n1 - n2 ≠ 0.
If m1 - m2 =0 , then (m1 - m2 )a = z = (n1 - n2 )u , with 0 < | n1 - n2 | < p
So, xF, |n1 - n2 |x = |n1 - n2 |(ux)
= (|n1 - n2 |u)x
= zx = z
with 0 < |n1 - n2 |< p = Char(F) A contradiction
If n1 - n2 = 0 , then ( m1 - m2 )a = z with 0 < | m1 - m2 | < p
Since F is a field and a ≠ z, we know that a-1 F
so ( m1 - m2 )a a-1 = z a-1
= z with 0 < | m1 - m2 | < p = Char(F) which is another contradiction.
Hence neither m1 - m2 ≠ 0 nor n1 - n2 ≠ 0.
Therefore ( m1 - m2 )a = (n1 - n2 )u ≠ z
Choose kZ+ such that 0 < k < p and k( m1 - m2 ) u(mod p)
[since p is prime, Zp is field multiplicative inverse exists in Zp ]
Then a = au
= a(m1 - m2 )k
= k(m1 - m2)a = k(n1 - n2 )u
[since p is prime, Zp is field and 0 < k, n1 - n2 < p
k(n1 - n2 ) Zp by closure property on multiplication Zp ]
a S0, one more contradiction.
Hence | S1 | = p2, and if F = S1 the theorem is proved.
If not, continue this process with an element bF - S1
Then S2 ={lb+ ma + nu/ 0 < l, m, n p} will have order p3
Since F is finite ,
we reach a point where F = St-1 for some tZ+ and |F| =| St-1 |= pt, where p is prime
5i) If F is a field, then prove that F[x] is an integral domain and not a field
Proof:
Given that F is a filed. Therefore, F is a commutative ring.
Therefore F[ x] is a commutative ring.
Case (1) To prove F is an integral Domain
Let ab 0, a 0 in F.
a 1(ab) a 1(0) 0
(a 1a)b 0 b 0
Therefore, F Is an integral Domain.
Case (2) To Prove F[ x] is an integral Domain
Let f ( x) a0 a1x a2 x 2 a3 x3 ...... am x m , (am 0) and
g(x) b0 b1x b2 x 2 b3 x3 ...... bn x n , (bn 0)
Be any two non-zero elements in F[ x].
Since R is integral domain and am , bn 0 , so as ambn 0 .
The product of f ( x)g(x) of f ( x) and g ( x) will contain the term ambn x m n
Therefore f ( x) g(x) 0.
Therefore f ( x) 0, g(x) 0 f ( x) g(x) 0.
Page 24 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
F[x] is an integral domain.
Case (3) To Prove F[ x] is not a filed
Let f ( x)( 0) F and deg f ( x) 1. The unit element of F is the constant polynomial „1‟.
If possible, there exists a multiplicative inverse of f ( x) exists and let it be g ( x) .
f ( x) g ( x) 1 .................(1)
g ( x) 0.
Suppose g ( x) 0 , then f ( x) g ( x) 1 f ( x)(0) 1 0 1 which is not possible.
Since F is an integral Domain, we have
deg( f ( x).g ( x)) deg( f ( x)) deg( g (x)) 1.
(1) is impossible because deg (1) =0
A non-zero element in F[ x] may not have multiplicative inverse in F[ x]
F[ x] is not field.
5ii) State and Prove Division Algorithm
Statement :
Let F be a field and let f ( x) and g ( x) be two polynomials in F ( x) with g ( x) 0. Then there
exists unique polynomials q( x) and r ( x) such that g ( x) q( x) f ( x) r ( x) where either
r ( x) 0 (or) deg r ( x) deg f ( x)
Proof:
Let S {g ( x) t ( x) f ( x) / t(x) F[x]}.
If 0 S , 0 g ( x). t (x) f ( x) , for some t(x) F[x] .
Then with q(x) t(x) and r ( x) 0 , we have g ( x) t ( x) f ( x) r (x).
If 0 S , Consider the degrees of the elements of S, and let r ( x) g (x) q( x) f ( x) be an
element in S of minimum degree.
Since r ( x) 0, the result follows if deg(r ( x)) deg(f(x)).
If not, let
r ( x) an x n an 1x n 1 ....... a2 x 2 a1x a0 , an 0
f ( x) bm x m bm 1x m 1 ....... b2 x 2 b1x b0 , bm 0 with n m.
1 n m
Define h( x) r ( x) [anbm x ] f ( x)
1 1
(an anbm bm ) x n (an 1 anbm bm 1) x n 1 ..
1
...... (an m anbm b0 ) x n m an m 1x n m 1 ....... a1x a0 .
Then h( x) has degree less than n , the degree of r ( x).
More importantly,
1 n m
h( x) [ g ( x) q( x) f ( x)] [anbm x ] f ( x)
,
1 n m
g(x) [q( x) anbm x ] f ( x)
so h( x) S and this contradicts the choice of r ( x) as having minimum degree.
Consequently deg(r ( x)) deg( f ( x)) and we have the existence part of the theorem.
For uniqueness,
let g ( x) q1( x) f ( x) r1( x) q2 ( x) f ( x) r2 ( x)
where r1( x) 0 or deg r1( x) deg f ( x) , and r2 ( x) 0 or deg r2 ( x) deg f ( x).
Then [q2 ( x) q1( x)] f ( x) r1( x) r2 ( x),
If [q2 ( x) q1( x)] 0, then deg[q2 ( x) q1( x)] f ( x) deg ( f ( x)),
Page 25 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
whereas [r1( x) r2 ( x)] 0 or deg[r1( x) r2 ( x)] max{deg r1( x),deg r2 ( x)} deg f (x).
Consequently r1( x) r2 ( x) and q1( x) q2 ( x).
UNIT-III DIVISIBILITY THEORY AND CANONICAL DECOMPOSITIONS
PART-A
1 Explain Divisibility.
Let a, b z we say „a‟ divides b if their exist c z such that b=ac. „a‟ is called divisor or factor
of „b‟. and „b‟ is called multiple of „a‟. So we write it as a / b (i.e.) b is divisible by a.
If a does not divide b, then we write a / b .
2 State the properties of divisibility.
(i). a / b a / bc for all integer c
(ii). If a / b, b/ c a / c
(iii). If a / b, a / c a / bx cy integers x & y
(iv). If a / b, b / a a b
3 If a / b, a / c prove that a / bx cy intgers x & y
since a / b b am - - - - - (1); a / c c al - - - - - (2)
(1) x bx amx - - - - - (3)
(2) y cy aly - - - - - (4)
(3) (4) bx cy amx aly a (mx ly ) , where mx ly is integer a / bx cy
4 Find the number of positive integers ≤ 2076 and divisible by neither 4 or 5
Let A x N / x 2076 and divisible by 4 ; B x N / x 2076 and divisible by 5
then A B A B A B
2076 / 4 2076 / 5 2076 / 20 519 415 103 831
Thus, among the first 2076 positive integers, there are 2076-831=1245 integers not divisible
by 4 or 5.
5. Find the number of positive integers ≤ 3076 and not divisible by 17. [NOV/DEC 19]
3076
Number of positive integers ≤ 3076 and divisible by 17 = 180
17
Therefore number of positive integers ≤ 3076 and not divisible by 17 = 3076 – 180 = 2896
6. Add two more rows to the following pattern, and write conjecture formula for the nth
row:
9 9 7 88
98 9 6 888
987 9 5 8888
9876 9 4 88888
98765 9 3 888888
Answer: The next two rows of the given pattern are,
987654 9 2 8888888
9876543 9 1 88888888
The general pattern is 98765.....(10 n) 9 (8 n) 888.....88
( n 1) Eights
7. State the Pigenhole Principle. [NOV/DEC 20]
If m pigeons are assigned to n pigenholes where m > n, then atleast two pigeons must occupy
the same pigenhole.
Page 26 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
8. Explain base-b representation.
The expression ak b k ak 1b k 1 ..... a1b a0 is the base-b representation of theinteger N.
Accordingly, we write N ak ak 1.....a1a0 b in base b.
9. Determine if 1601 is a prime number.
We know that if n has no prime factors ≤ n, then n is a prime
consider prime nos ≤ 1601
prime nos ≤ 40 (approx)
2,3,5,7,11,13,17,19,23,29,31 and 37 and which are not factors of 1601
Therefore, 1601 is a prime.
10. Find the GCD of 1819 & 3587.
(3587,1819) 11819 1768
(1819,1768) 11768 51
(1768,51) 34 51 34
(51,34) 1 34 17
(34,17) 2 17 0
gcd of 1819,3587 is 17
11 Find the GCD of a b, a 2 b2 .
GCD a b, a 2 b 2 GCD a b, a b a b a b
12 Find a positive integer „a‟ , if a, a 1 132
We know that a, b
ab
(1)
a, b
Since LCM of a, a 1 132 & GCD of a, a 1 1
a a 1
(1) 132 a 2 a 132 0 a 12,11
1
Since a is positive integer, a = 11
13 Using (252, 360) compute [252, 360].
Since GCD of 252 and 360 = 252,360 36
252 360
a, b ab
252, 360 2520
a, b 36
14 If a, 4 2 & b, 4 2 show that a b, 4 2
a, 4 2 gcd of a, 4 2 2 / a but 4 / a a 2k , and k is odd
b, 4 2 gcd of b, 4 2 2 / b but 4 / b b 2l, and l is odd
a b 2k 2l 2 k l 2(even) 2 2m 4m
4 / a b gcd a b, 4 4
15 If x and y are odd integers show that x 2 y 2 cannot be perfect square.
Since x and y are odd integers x 2 y 2 is even 2/x 2 y 2
To prove:
x 2 y 2 cannot be perfect square, it is enough to show that x 2 y 2 , 4 2
Let x 2k 1, y 2l 1
x2 y 2 4 k 2 l 2 k l 2
Page 27 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
x 2 y 2 , 4 4 k 2 l 2 k l 2, 4 2, 4
hence x 2 y 2 cannot be perfect square.
16 Prove that any prime of the form 3k+1 is of the form 6k+1.
Let the prime p =3k+1, then k must be even.
[if k is odd, then 3k is odd 3k+1 is even 3k+1 is not prime]
k=2k, then p =3(2k)+1=6k+1.
Hence any prime of the form 3k+1 is of the form 6k+1.
17. Using canonical decomposition of 1050 and 2574 find their LCM. [NOV/DEC 19]
1050 2 3 52.7 2574 2 32 11.13
LCM 1050, 2574 2 32 52 7.11.13 450
18. Find the canonical decomposition of 29 1
29 1 23 13 23 1 26 23 1 a3 b3 a b a 2 ab b 2
3
7 73
19. If d = a,b and d' is any common divisor of a and b, then d'/d.
Since d = a, b , α and β such that d a b.
also since d' is common divisor of a & b. d'/ a & d'/ b
d'/ αa+βb ; so d'/d.
20. Prove that n2 +n is an even integer, where n is arbitrary integer.
To prove: p(n) n2 n is an even integer
p(1) 12 1 2is an even number
We assume that the result is true for all k, k be the arbitrary number.
p(k) k 2 k is an even integer
consider p(k+1) k 1 k 1
2
k 2 2k 1 k 1
k 2 k 2k 2 Even number
hence p(n)=n 2 n is even integer n.
PART-B
1i) Find the number of positive integers in the range 1976 through 3776 that are divisible
by13.
Solution:
1976
The number of positiveintegers 1976 that are divisible by 13
13
152
3776
The number of positiveintegers 3776 that are divisible by 13
13
290
The number of positiveintegers1976 to3776 that are divisible by 13
290 152 1
139 [ 1976 is included in the list of numbers divisible by 13]
Page 28 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
1ii) Prove that a, a b 1 if and only if a, b 1
Proof:
Let a, a b 1
Then there exist integer l and m such that
la mb 1
la ma mb ma 1
(l m)a m(a b) 1
(l m)a ( m)( a b) 1
a, a b 1
Conversely, let a, a b 1. To prove : a, b 1
Then there exist integer and such that
a ( a b) 1
a a b 1
a ( )b 1 a, b 1
1iii) Obtain six consecutive integers that are composite. [NOV/DEC 20]
Solution:
By theorem, for every integer n, there are n consecutive integers that are composite numbers.
Then the six consecutive composite numbers are
n 1! 2, n 1! 3, n 1! 4, n 1! 5, n 1! 6, n 1! 7
put n 6
The six consecutive composite numbers are5042, 5043,5044,5045,5046, and 5047
2i) Apply Euclidean Algorithm and express (4076, 1024) as a linear combination of 4076,
1024.
Solution:
By successive application of division algorithm, we get:
4076 3 1024 1004
1024 1 1004 20
1004 50 20 4
20 5 4 0
Since the last nonzero remainder is 4 4076,1024 4
4076,1024 4 1004 50 20
1004 50 1024 11004
511004 50 1024
51 4076 3 1024 50 1024
51 4076 203 1024
2ii) Prove that there are infinitely many primes. [NOV/DEC 19,20]
Proof:
We prove by contradiction method.
Assume that there are only n primes p1 , p2 ,..., pn where n is prime.
Now consider the integer
m p1 p2 p3 ..., pn
Page 29 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
Since m 1, by theorm, every integer n 2 has a prime factor. m has a prime factor p.
But none of the primes p1 , p2 , p3 ,..., pn divide m
For,if pi / m and since pi / p1 p2 p 3 ..., pn
we get pi / m p1 p2 p3 ..., pn pi /1, which is not true and hence a contradiction.
pi / m
So, we have a prime p which is not in the list of n primes.
Thus, we have n+1 primes p1 , p2 , p3 ,..., pn , pn 1
which contradicts theassumption there areonly n primes.
So, our assumption of finiteness is wrong. Hence the number of primes is infinite.
3i) Prove that the GCD of the positive integers a &b is linear combination of a and b.
[NOV/DEC 19]
Proof:
Let S be the set of positive linear combination of a and b; that is
S ma nb / ma nb 0, m, n Z
To show that S has a least element:
Since a 0, a 1 a 0 b S , So S is non empty.
So, by the well-ordering principle, S has a least positive element d.
To show that d a, b :
Since d belongs to S, d a b for some integer and .
1.First we will show that d / a and d / b :
By the division algorithm,
there exist integers q and r such that a dq r , where 0 r d .
r a dq
a a b q substituting for d.
1 q a q b \
This shows r is a linear combination of a and b.
If r 0, then r S . Since r d , r is less than the smallest element in S.
Which is a contrdiction . So r 0; thus, a dq, so d / a.
Similarly, d/b. Thus d is common divisor of a and b.
2.To show that any positive common divisior d ' of a and b is d :
Since d '/ a, and d '/ b d '/ a b
that is d '/ d . So d ' d .
Thus, by parts (1) and (2), d a, b
3ii) Show that for any integer n, n 2 - n is divisible by 2 and n 5 - n is divisible by 30.
Solution:
n 2 - n n (n -1) , product of two consecutive natural numbers is always divisible by2
To Prove : n 5 - n is divisible by 6
n 5 - n n (n4 1) n (n2 1)(n2 1) n(n 1)(n 1)(n 2 1) (n 1)n(n 1)(n 2 1)
Now, as we know that product of 3 consecutive natural numbers is always divisible by3 and
that of 2 consecutive natural numbers is always divisible by2 so this expression is always
divisible by6.
Page 30 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
Now to prove divisibility by 5, First we write the factorization as under
n (n 1) (n 1) (n 2 1) n (n 1) (n 1) n 2 4 5
n (n 1) (n 1) n 2 n 2 5
(n 2)(n 1)n(n 1)(n 2) 5 n (n 1) (n 1)
We see that second term is divisible by 5 and first term is also divisible by 5 as it is product of
5 consecutive natural numbers. Hence the given expression is divisible by 5×6=30.
Hence the proof.
4i) Using recursion, evaluate (18, 30, 60, 75, 132).
Solution.:
18,30, 60, 75,132 18,30, 60, 75 ,132
18,30, 60 , 75 ,132
18,30 , 60 , 75 ,132
6, 60 , 75 ,132
6, 75 ,132 3,132 3
4ii) Find the number of positive integers ≤ 3000 and divisible by 3, 5, or 7. [NOV/DEC 20]
Solution:
Let A,B,C be the set of numbers ≤ 3000 and divisible by 3, 5,7 respectively.
Required A B C
By inclusion and exclusion principle, we get
A B C S1 S 2 S3
Now
3000
A 1000 1000
3
3000
B 600 600
5
3000
C 428.57 428
7
S1 A B C 1000 600 428 2028
3000
AB 200 200
3 5
3000
A C 142.85 142
3 7
3000
B C 85.71 85
5 7
S2 A B A C B C 200 142 85 427
3000
Now S3 A B C 28.57 28
3 5 7
A B C S1 S2 S3 2028 427 28 1629
Page 31 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
4iii) Show that product of k consecutive integers is divisible by k!
Proof:
Let n 1 , n 2 , , n k be the 'k' consecutive integer.
Product of 'k' consecutive integer = n 1 n 2 n k
n! n k !
n 1 n 2 n k
n! n!
k! n k !
Product of 'k' consecutive integer= k! n rCr Integer
k! n !
Hence the product of k consecutive integers is divisible by k!
5i) State and prove fundamental theorem of arithmetic. [NOV/DEC 20]
Statement:
Every integer n 2 either is a prime or can be expressed as a product of primes. The
factorization into primes is unique except for the order of the factors.
Proof:
First, we will show by strong induction that n either is a prime or can be expressed as a
product of primes. Then we will establish the uniqueness of such a factorization.
Let P(n) denote the statement that n is a prime or can be expressed as a product of primes.
To show that P n is true for every integer n 2 :
since 2 is a prime, clearly P(2) is true.
Now assume P(2), P(3),…..P(k) are true; that is every integer 2 through k either is a prime or
can be expressed as a product of primes.
If k+1 is a prime, then P(k+1) is true. So suppose k+1 is composite.
Then k+1 = ab for some integers a and b, where 1 < a, b < k+1.
By the inductive hypothesis, a and b either are primes or can be expressed as products of
primes; in any event, k+1=ab can be expressed as products of primes.
Thus, P(k+1) is also true.
Thus by strong induction, the result holds for every integer n 2
To Establish the Uniqueness of the Factorization:
Let n be a composite number with two factorization into primes; n p1 p2 pr q1q2 qs
we will show that r = s and every pi equals some q j ,where 1 i, j r;
that is, the primes q1 , q2 ,.....qs are a permutation of the primes p1 p2 pr
Assume, for convenience that r s
since p1 p2 pr q1q2 qs , p1 / q1q2 qs ,
p1 qi for some i.
Dividing both sides p1 , we get: p2 ..... pr q1q2 ...qi 1q i qi 1...qs
Now, p2 divides the RHS , so p2 q j for some j. cancel p2 form both sides :
p3 .....p r q1q2 ...qi 1q i qi 1...q j 1q j q j 1qs
Since r s, continuing like this, we can cancel pt with some qk .
This yields a 1 on the LHS at the end.
Then the RHS cannot be left with any primes, since a product of primes can never yield a 1;
thus, we must have exhausted all qk ' s by now.
therefore, r = s and hence the primes q1 , q2 ,.....qs are the same as the primes p1 p2 pr in
some order.
Thus, the factorization of n is unique, except for the order in which the primes as written.
Page 32 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
5ii) Prove that the product of gcd and lcm of any two positive integers a and b is equal to
their products. [NOV/DEC 19]
Proof:
Let a p1a1 p2a2 .....pnan , b=p1b1 pb22 .....pbnn be the canonical decomposition of a and b. Then
a, b p p maxa1 ,b1
1
maxa2 ,b2
2
.....p max an ,bn
n
a, b p p 1
mina1 ,b1 mina2 ,b2
2
.....p minan ,bn
n
a, b a, b p maxa1 ,b1 mina1 ,b1
1
p maxa2 ,b2 min a2 ,b2
2
.....p maxan ,bn minan ,bn
n
p a1 b1
1
p a2 b2
2
.....p an bn
n
p1a1 p 2a2 .....p nan p1b1 pb22 .....pbnn
ab
ab
Hence a,b
a,b
UNIT – IV DIOPHANTINE EQUATIONS AND CONGRUENCES
PART- A
1 Define congruence modulo m.
If an integer m ( 0) divides the difference a b , we say that a is congruent to b modulo m.
(i.e) a b(mod m).
2 Define linear congruence.
A congruence of the form ax b(mod m) is called a linear congruence. An integer x1 is said to
be a solution or root of this congruence, if ax1 b(mod m) (i.e) m | ax1 b .
3 Solve the congruence 4 x 5(mod 6).
4 x 5(mod 6)
Here a 4, b 5, m 6
(a, m) (4, 6) 2 2 / 5 (i.e) ( a, m) / b
The congruence has no solution.
4 What is digital root of a positive integer? What are the digital roots of square numbers?
Is 16151613924 a square?
Let N = (anan-1...a1a0)ten and d be its digital root, then d (an +an-1+....+a1+a0 ) (mod9).
(i.e) the digital root of N is the remainder when N is divided by 9 with one exception: it is 9 if
the remainder is 0.
The digital roots of square numbers are 1, 4, 7, or 9.
1+6+1+5+1+6+1+3+9+2+4=39 remainder is 3 when divided by 9
Therefore digital root of 16151613924 is 3.
Hence 16151613924 is not a square.
Page 33 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
5 Solve x 7 1 0(mod 7)
The complete residuesystem(CRS ) is {0,1, 2,3, 4,5,6}
But 4 3 (mod 7)
5 2 (mod 7)
6 1 (mod 7)
The CRS is {0, 1, 2, 3}
The CRS does not satisfy the congruence x 2 1 0 (mod 7)
The given congruence has no solution.
6 State Chinese remainder theorem.
Let m1 , m2 ,...., mr denote r positive integers that are relatively prime in pairs and let
a1 , a2 ,...., ar be any r integers. Then the congruence x ai (mod mi ), i 1, 2,...., r have
common solution.
7 Determine whether the LDEs 12x + 18y = 30, 2x + 3y = 4, and 6x + 8y = 25 are
solvable.
(12,18) 6 and 6 | 30, so the LDE 12 x 18 y 30 has a solution.
(2,3) 1, so the LDE has a solution.
(6,8) 2, but 2 / 5, so the LDE 6 x 8 y 25 is not solvable.
8 Prove that a b (mod m) if and only if a b km for some integer k.
Suppose a b (mod m).
Then m / ( a - b), so a b km for some integer k. (i.e) a b km.
Conversely, suppose a b km.
Then a b km, so m / (a b ) and consequently, a b(mod m).
9 Find the remainder when 1! 2! ...... 100! is divided by 15.
Notice that when k 5, k ! 0 (mod 15)
1! 2! ..... 100! 1! 2! 3! 4! 0 ..... 0(mod 15)
1 2 6 24 (mod15)
1 2 0 ( mod15)
3(mod15)
Thus, when the given sum is divided by 15, the remainder is 3.
10 Let a b (mod m) and c d (mod m), then prove that a c b d (mod m).
Since a b (mod m) and c d (mod m),
a b lm and c d km for some inegers l and m.
Then a c (b lm) (d km)
(b d ) (l k )m
b d (mod m)
11 Let a b (mod m) and c d (mod m), then prove that ac bd (mod m).
Since a b (mod m) and c d (mod m),
a b lm and c d km for some inegers l and m.
Then ac bd (ac bc) (bc bd )
c ( a b ) b (c d )
clm bkm
(cl bk )m ac bd (mod m)
Page 34 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
12 Find the remainder when 1653 is divided by 7.
16 2(mod 7).
If a b (mod m), then a n bn (mod m) for any positiveinteger n 16n 2n (mod 7).
1653 253 (mod 7)
23 1 (mod 7)
253 23(17) 2
(23 )17 .22
117.4(mod 7) 4(mod 7)
So1653 4(mod 7), by the transitive property.
Thus, when1653 is divided by 7, the remainder is 4
13 Find the remainder when 331 is divided by 7. [NOV/DEC 19]
32 2 (mod 7)
(32 )3 23 (mod 7) 1(mod 7) 36 1(mod 7)
331 (36 )5 .3 15.3 (mod 7)
3(mod 7) Thus the remainder is 3.
14 Determine whether the LDE 2 x 3 y 4 z 5 is solvable? [NOV/DEC 19]
Thegcd (2,3, 4) 1 i.e.,(2,3, 4) 1 and 1/ 5 The given LDE is Solvable.
15 Define 2X2 linear system
A 2 2 linear system is a system of linear congruences of the form,
ax by e( mod m); cx dy f ( mod m)
Asolution of the linear system is a pair x x0 (mod m), y y0 (mod m) that satisfies both congruences.
16 Show that x 12(mod 13)and y 2(mod13)is a solution of the 2 2 linear system
2 x 3 y 4(mod13)
3 x 4 y 5(mod13).
When x 12(mod13)and y 2(mod13),
2 x 3 y 2(12) 3(2) 4(mod13)
3 x 4 y 3(12) 4(2) 5(mod13)
Therefore, every pair x 12(mod13), y 2(mod13)is a solution of the system.
17 Verify that the linear system 2x+3y4(mod13) and 3x +4y 5 (mod 13) has a unique
solution modulo 13.
We know that the system has a unique solution modulo m if and only if (, m) 1
23
ad bc 1 12(mod 13).
34
Since (12,13)=1 Therefore the system has a unique solution modulo 13.
18 Prove that no prime of the form 4n + 3 can be expressed as the sum of two squares.
[NOV/DEC 20]
Let N be a prime of the form 4n + 3.
Then N 3(mod 4).
Suppose N A2 B 2 for some integers A and B.
Since N is odd, one of the squares
(say A2 ) must be odd and hence B2 must be even.
Then A must be odd and B even.
Page 35 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
Let A 2a 1 and B 2b for some integers a and b .
Then N (2a 1) 2 (2b) 2
4(a 2 b 2 a ) 1
1(mod 4)
which is a contradiction,since N 3(mod 4)
19 Show that a palindrome with an even number of digits is divisible by 11.
Let be n n2 k 1n2 k 2 ......n1n0 palindrome with an even number of digits
n (n0 n 2 ..... n 2 k 2 ) ( n1 n 3 ..... n 2 k 1 )(mod11)
0 (mod11)
because n is palindrome with an even number of digits Thus, 11| n.
20 Define complete residue system.
A set x1 , x2 ,...., xm is a complete residue system mod m if for integer y , there is one and only
one x j such that y x j (mod m) .
PART B
1i) Show that n + n 0(mod 2) for any positive integer n.
2
Proof:
a b (mod k ) a b km, m z
a b is divisible by k
n even 2m
n 2 n (2m) 2 (2m) 4m 2 2m 2(2m 2 m)
n2 n is divisible by 2
n odd 2m 1
n 2 n (2m 1) 2 (2m 1)
4m 2 4m 1 2m 1
4m 2 6m 2
2(2m 2 3m 1)
n2 n is divisible by 2 n2 n 0(mod 2)
1ii) Prove that p is a prime iff (p – 1)! +1 0(mod p).
Proof:
Suppose p is not a prime then p p1 p2 where 1 p1 , p2 p 1
since 1 p1 p 1, we find p1 is a factor of ( p 1)!
(ie) p1 ( p 1)! Also p1 p
we are given ( p 1)! 1 0 (mod p)
p ( p 1)! 1
p1 ( p 1)! 1
Thus p1 ( p 1)! 1 & p1 ( p 1)! p1 ( p 1)! 1 ( p 1)!
p1 1 which is not possible p1 1 Hence p must be prime.
Page 36 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
2 State and prove Chinese remainder theorem. Using it find the least positive integer that
leaves the remainder 1 when divided by 3, 2 when divided by 4 and 3 when divided by 5.
[NOV/DEC 19]
Statement:
Let m1 , m2 ,...., mr denote r positive integers that are relatively prime in pairs and let
a1 , a2 ,...., ar be any r integers. Then the congruence x ai (mod mi ), i 1, 2,...., r have
common solution.
Proof:
Part1: Existence of the solution
n
Let n m1. m2 .m3. ...mk & ni , i 1, 2,3,...., k .
mi
Since m1. m2 .m3. ...mk are pairwise relatively prime ( ni , mi ) 1, i 1, 2,3,...., k
Also ni 0 (mod m j ), i j
Since (ni , mi ) 1, the congruence ni yi 1(mod mi ) has a unique solution yi , i 1, 2,3,...., k
Let x a1 n1 y1 a2 n2 y2 ....... ak nk yk
Now, we will show that x is a solution of the system of congrunces.
Since ni 0 (mod mk ) for i k , all terms except the k th term in this are
congruent to 0 modulo mk
Since nk yk 1(mod mk ), we see that x ak nk yk ak (mod mk ),for k 1, 2,3,..., n
Thus x satisfies every congruence in the system.
Hence x is a solution of the linear system.
Part 2 : Uniquness of the solution
Solution is unique in modulo n m1.m2 .....mk .
Let x1 , x2 be two solutions of the system
To prove x1 x2 (mod n)
Since x1 a j (mod m j ) and x2 a j (mod m j ), j 1, 2,3,...., k
we have x1 x2 0 (mod m j ) m j | x1 x2 for every j
Since m1 , m2 ,..., mk are pairwise ralatively prime,
LCM [ m1 , m2 ,..., mk ] m1 , m2 ,..., mk | x1 x2
n | x1 x2 x1 x2 (mod n)
Hence the solution is unique mod m1m2 ...mk .
Given system is x 1(mod 3); x 2(mod 4); x 3(mod 5)
Here a1 1, a2 2, a3 3; m1 3, m2 4, m3 5
We find m1 , m2 , m3 are pairwiserelatively prime
Let n m1m2 m3 3.4.5 60
n 3.4.5 n 3.4.5 n 3.4.5
and n1 20 ; n2 15 ; n3 12
m1 3 m2 4 m3 5
1.Wefind y1 , y2 , y3 from the congrunces
n1 y1 1(mod m1 )
n2 y2 1(mod m2 )
n3 y3 1(mod m3 )
Page 37 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
We have n1 y1 1(mod m1 ),
20 y1 1(mod 3),
Since 20.2 40 1(mod 3), we see y1 2 is a solution
We have n2 y2 1(mod m2 ),
15 y2 1(mod 4),
Since 15.3 45 1(mod 4) , we see y2 3 is a solution
We have n3 y3 1(mod m3 ),
12 y3 1(mod 5),
Since 12.3 36 1(mod 5), we see y3 3 is a solution
2. Then solution is x a1n1 y1 a2 n2 y2 a3 n3 y3 (mod n)
x 1.20.2 2.15.3 3.12.3 (mod 60)
x 40 90 72 (mod 60)
x 238(mod 60)
x 58(mod 60)
58is the unique solution (mod 60)
thesolution of the system is x 58(mod 60) and it is the uniquesolution.
3i) Solve the congruence x 1(mod 4), x 0(mod3), x 5(mod 7).
Solution:
Here a1 1, a2 0, a3 5; m1 4, m2 3, m3 7
m m1 . m2 . m3 4.8.7 84
m 84 m 84 m 84
21; 28; 12
m1 4 m2 3 m3 7
m m m
, m1 (21, 4) 1 ; , m2 (28,3) 1 ; , m3 (12, 7) 1
m1 m2 m3
m
we know that b j 1(mod m j )
m
j
m
For m1 b1 1(mod m1 )
m1
(21)b1 1(mod 4) 4 / 21b1 1
21b1 1 4k , k is an integer
21b1 1 4k
1 4k
b1
21
put k 5, b1 1
m
For m2 b2 1(mod m2 )
m2
(28)b2 1(mod 3) 3 / 28b2 1
Page 38 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
28b2 1 3k , k is an integer
28b 2 1 3k
1 3k
b2
28
put k 9, b2 1
m
For m3 b3 1(mod m3 )
m3
(12)b3 1(mod 7) 7 /12b3 1
12b3 1 7k2 , k2 is an integer
12b3 1 7k2
1 7 k2
b3
12
put k2 5, b3 3
By chinese remainder theorem,
3
m
x ai bi (mod m)
i 1 mi
m m m
a1b1 a2b2 a3b3 (mod m)
m1 m2 m3
(2111) (28 0 1) (12 5 3) (mod 84)
(21 180) (mod 84)
201(mod 84)
3ii) Determine whether the system
x 3(mod10); x 8(mod15); x 5(mod84) has a solution and find themall if it exists.
Solution:
The first congruence x 3(mod10) is equivalent to the simultaneous congruences
x 3(mod 2) -------(1)
x 3(mod 5) --------(2)
The congruence x 8(mod15)is equivalent to,
x 8(mod 3) (3)
x 8(mod 5) (4)
The congruence x 5(mod 84) is equivalent to,
x 5(mod 3) (5)
x 5(mod 4) (6)
x 5(mod 7) (7)
The congruence (1) & (6)
x 3(mod 2)
x 5(mod 4) reduces to x 1(mod 4) (8)
The congruence (3) & (5)
x 8(mod 3)
x 5(mod 3) reduces to x 2 (mod 3) (9)
Page 39 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
The congruence (2) & (4)
x 3(mod 5)
x 8(mod 5) reduces to x 3(mod 5) (10)
From (7) x 2 (mod 7) (11)
we have solve thecongruence of (8),(9),(10)&(11)
Here a1 1, a2 2, a3 3, a4 5; m1 4, m2 3, m3 5, m4 7
m m1 . m2 . m3 . m4 4.3.5.7 420
m m m m
105, 140, 84, 60
m1 m2 m3 m4
m
we know that b j 1(mod m j )
m
j
m
For m1 b1 1(mod m1 )
m1
(105)b1 1(mod 4) 4 /105b1 1
105b1 1 4k1 , k1 is an integer
105b1 1 4k1
1 4k1
b1
105
put k1 26, b1 1
m
For m2 b2 1(mod m2 )
m2
(140)b2 1(mod 3) 3 /140b2 1
140b2 1 3k2 , k2 is an integer
140b 2 1 3k2
1 3k2
b2
140
put k2 93, b2 2
m
For m3 b3 1(mod m3 )
m3
(84)b3 1(mod 5) 5 / 84b3 1
84b3 1 5k3 , k3 is an integer
84b3 1 5k3
1 5k3
b3
84
Page 40 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
m
For m4 b4 1(mod m4 )
m4
(60)b4 1(mod 7) 7 / 60b4 1
60b4 1 7k4 , k4 is an integer
84b 4 1 7k4
1 7 k4
b4
84
put k4 17, b3 2
By chinese remainder theorem,
4
m
x ai bi (mod m)
i 1 mi
m m m m
a1b1 a2b2 a3b3 a4b4 (mod m)
m1 m2 m3 m4
(105 11) (140 2 2) (84 3 4) (60 5 2) (mod 420)
(105 560 1008 600) (mod 420)
2273(mod 420) 173(mod 420)
4i) Prove that 42n + 10n 1(mod 25).
Proof :
42 n 10n 1(mod 25)
proof by mathematicalinduction
n 0
(40 0) 1 1 1 0
0 is divisible by 25
statement is true for n 0.
n 1, (42 10) 1 25
25 is divisible by 25
statement is true for n 1.
Assume that the statement is true for n k
(ie), 42 k 10k 1 25l
Consider 42 k 2 10(k 1) 1
42 k .16 10k 10 1
16 (25l 10k 1) 10k 9
16(25l ) 160k 16 10k 9
16(25l ) 150k 25
25(16l 6k 1)
25( y)
4 10(k 1) 1 is divisible by 25
2k 2
Statement is true for n k 1
By principle of mathematical induction, statement is true for all n.
Page 41 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
4ii) Find the remainder when (n2 n 41)2 is divisible by 12.
Solution:
First notice that product of four consecutive integers is divisible by12,
(ie), (n 1)n(n 1)(n 2) 0 (mod12)
(n 2 n 41) 2 (n 2 n 5) 2 (mod12)
(n 4 2n3 11n 2 10n 25) (mod12)
n(n3 2n 2 n 2) 1 (mod12)
n n 2 (n 2) (n 2) 1 (mod12)
n((n 2)(n2 1) 1 (mod12)
(n 1)n(n 1)(n 2) 1 (mod12)
1 (mod12)
Thus when (n 2 n 41) 2 is divided by12, the remainder is 1.
5i) Find the general solution of the LDE 6 x 8 y 12 z 10 [NOV/DEC 20]
Solution:
Given the LDE is 6 x 8 y 12 z 10 (1)
Here a1 6, a2 8, a3 12, c 10
(a1 .a2 , a3 ) (6,8,12) 2 and c 10
d (a1 .a2 , a3 ) 2
Since 2 |10, d | c
So, the given LDE is solvable.
Since 8 y 12 z is a linear combination of 8and 12, it must bea multiple of (8,12) 4
8 y 12z 4u (2)
(1) 6x 4u 10 (3)
First we solve the LDE (3) in two variables x and u
Here a 6, b 4, c 10
(a, b) (6, 4) 2
d (a, b) 2 and c 10
Since 2 |10, d | c
So, the given LDE (3) is solvable.
We find x0 1, u0 1 is a solution of (3) is
b a
x x0 t and u u0 t , t Z
d d
4 6
x 1 t and u 1 t , t Z
2 2
x 1 2t and u 1 3t , t Z
Substituting for u in (2), we get
8 y 12 z 4(1 3t )
a b
Since d= 4 and 4 2.8 (1).12 is a linear combination of 8 and 12.
8, 12
Multiplying by (1 3t ), we get
4(1 3t ) 2(1 3t ).8 (1)(1 3t ).12
(2 6t ).8 (1 3t ).12
Page 42 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
a solution of (2) is
y0 2 6t and z0 1 3t , t Z
So, the generalsolution of (2) is
b a
y y0 t ' and z z0 t ', t ' Z
d d
12 8
y 2 6t t ' and z 1 3t t ', t ' Z
4 4
y 2 6t 3t ' and z 1 3t 2t ', t ' Z
Thus the general solution of (1) is
x 1 2t , y 2 6t 3t ', z 1 3t 2t ', t ' Z
5ii) Find the general solution of the LDE 15x 21y 39 [NOV/DEC 19]
Solution:
15 x 21 y 39 a 15, b 21, c 39.
d (15, 21) and d / 39 d 3
So, the given LDE is solvable.
15 x 21y 39 5 x 7 y 13 (1)
then (5, 7) d 1 d /13
a 5, b 7, d 1
We find x0 3, y0 4 is a solution of (1) is
b a
x x0 t and y y0 t , t Z
d d
7 5
x 3 t and y 4 t , t Z
1 1
x 3 7t and y 4 5t , t Z
6i) Solve the linear system 5x 6 y 10(mod13); 6 x 7 y 2(mod13). [NOV/DEC 19]
Solution:
5 x 6 y 10 (mod13)
6 x 7 y 2 (mod13)
a 5, b 6, c 6, d 7, e 10, f 2.
m 13, ad bc 35 36 71(mod13) 7(mod13)
(, m) (13,1) 1.
Hence unique solution .
10 6
x0 1 (mod13) (1)
2 7
5 10
y0 1 (mod13) (2)
6 2
1 1(mod13)
7 1 1(mod13)
1 2(mod13)
(1) x0 1 (70 12)(mod13) 2(70 12)(mod13)
8(mod13)
5(mod13)
Page 43 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
(2) y0 1 (10 60)(mod13) 2(50)(mod13)
2.2(mod13)
4(mod13)
x 5(mod13); y 4(mod13).
6ii) Compute the remainder when 3247 is divisible by 25.
Solution:
We have to find the remainder when 3247 is divisible by 25.
We have 32 9(mod 25)
34 92 81 6 (mod 25)
38 62 36 11 (mod 25)
316 112 121 21 (mod 25)
332 212 16 (mod 25)
364 162 6 (mod 25)
3128 62 11 (mod 25)
3247 3128643216421
3128.364 .332 .316.34 .32 .3
3247 11.6.16.21.6.9.3 (mod 25)
11 (96) (21) (54)3 (mod 25)
11 (4) (4) (4) 3 (mod 25)
44.48 (mod 25)
(6) (2) (mod 25)
12 (mod 25)
the remainder is 12 when 3247 is divisible by 25.
UNIT – V CLASSICAL THEOREMS AND MULTIPLICATIVE FUNCTIONS
PART A
1 State Wilson‟s Theorem. [NOV/DEC 20]
If p is prime , then p 1 ! 1 mod p
2 Find the remainder when 100! is divided by 101.
We know that, By Wilson theorem “If p is prime , then p 1 ! 1 mod p ”
p = 101 is a prime, by Wilson‟s theorem, (101-1)! -1 (mod 101).
Therefore, Reminder when 100! Is divided by 101 is 101-1=100
3 What is the remainder when 100! is divided by 97 ?
2
100! Mod 972 = 97*(100*99*98*96! Mod 97)
97 is prime. So, 96!( mod 97) = 96
100*99*98*96!( mod 97) = 3*2*1*96(mod 97)
= 3*2*1*(-1) (mod 97)
= -6 (mod 97)
= 91 (mod 97)
So, required remainder = 91*97
= 8827
4 State Fermat‟s Little Theorem. [NOV/DEC 19]
p1
Let p be a prime and „a‟ any integer such that p a , then a 1 mod p
Page 44 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
5 Using Fermat‟s theorem, find the last digit of 3100 when divided by 10.
We know that 32 9 1 mod 10
3 1 mod 10
2n n
3
250
1 mod 10
50
Therefore last digit = 1
6 What is the remainder when 109 divides 17325?
By Fermat‟s theorem,
remainder when 109 divides 17(109-1) is 1 as109 is prime & 109 does not divide 17.
Remainder when 109 divides 173(109-1) is 1
remainder when 109 divides [173(108) ]x17 is 1 x17
remainder when 109 divides 17(324+1) is 17
7 Define Multiplicative function
A number-theoretic function f is multiplicative if f(mn) = f(m) f(n) whenever m and n are
relatively prime.
8 State Fundamental theorem for multiplicative function
Let f be a multiplicative function and n a positive integer with canonical decompositions
n p1e1 p2e2 ...pk ek then f (n) f (p1e1 ) f (p2e2 )...f (pk ek )
9 Define Euler phi function or totient function or Indicator function.
Euler phi function represent as n gives for a number „n‟ the number of co-primes in the
[1,2,…,n] , in other words, the quantity number in the range [1,2,…,n] whose greatest common
divisor with n is the unity.
10 Find all positive integers n such that ϕ(n)=6.
We know that ϕ(7)=6, ϕ(32)=6, and ϕ(2)=1 and ϕ is multiplicative
Therefore, the numbers should be 7, 7⋅2=14, 32=9, and 32⋅2=18
11 Find (221)
(221) (13.17) (13). (17) the function is multiplicative
= 12. 16 A positive integer p is prime iff (p) p 1
= 192
12 Find (8) , (81) and (15625)
We know that (pe ) pe pe1 , p be prime and e be any positive int eger
(8) (23 ) 23 22 8 4 4
(81) (34 ) 34 33 81 27 54
(15625) (56 ) 56 55 12500
n
13 , then show that the value of Euler‟s phi function (n) [NOV/DEC 19]
2
We know that (pe ) pe pe1 , p be prime and e be any positive int eger
Given
(n) (2k )
2k 2k 1
k
1 2 n
2 1
k
2 2 2
Page 45 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
14 State Euler‟s Theorem.
Let m be a positive integer and a be any integer with (a, m)=1 then a(m) 1 mod m
15 Verify that (d) 18
d /18
The positive divisors of 18 are 1,2,3,6,9,18
(d) (1) (2) (3) (6) (9) (18) = 1+1+2+2+6+6=18
d/18
16 Define Tau function
Let n be a positive integer then
(n) denotes the number of positive factors of n that is (n) 1
d/n
17 Define sigma function.
Let n be a positive integer then (n) denotes the sum of the positive factors of n that is
(n) d
d /n
18 Evaluate (18) and (23)
The positive divisors of 18 are 1,2,3,6,9,18 so that (18) 6
23 being a prime , has exactly two positive divisors so (23) 2
19 Evaluate (12) and (28)
The positive divisors of 12 are 1,2,3,4,6,12 so that (12) 1 2 3 4 6 12 28
The positive divisors of 28 are 1,2,4,7,14,28 so that (28) 1 2 4 7 14 28 56
20 Find the number of divisors and the sum of the divisors of 600.
Decomposition of 600 in canonical form
600 23 3 52 where p1 2, p2 3, p3 5, 1 3, 2 1, 3 2
If decomposition of N by canonical form = p11 p22 p33 .....
Number of divisor 1 1 2 1 3 1 ..... n 1
3 11 1 2 1 24
p1 1 1 p2 2 1 1 24 1 32 1 53 1
Sum of divisor 1 ..... 2 1 3 1 5 1 1860
p1 1 p 2 1
PART-B
1i) State and prove Wilson‟s Theorem [NOV/DEC 19]
Statement:
If p is prime, then (p 1)! ≡ 1 (mod p).
Proof :
We have to prove (p 1)! ≡ 1 (mod p)
When p = 2, (p 1)! = (2 1)! = 1 ≡l (mod 2).
So, the theorem is true when p = 2.
Now let p > 2 and let a be a positive integer such that 1 ≤ a ≤ p 1.
Since p is a prime and a < p, (a, p) = 1.
Then the congruence ax ≡ 1 (mod p) has a solution a’ congruence modulo p.
.∙. aa’ ≡ l(mod p), where 1 ≤ a’ <p 1
.∙. a, a’ are inverses of each other modulo p.
If a’ = a, then a .a ≡ 1 (mod p)
a2 1 ≡ 0∙(mod p)
.∙. .p ∣ a2 l p ∣ (a 1) (a+ 1)
Page 46 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
p ∣ a l or p ∣ a + 1
Since a < p, if p ∣ a +1 then a=p 1.
If p ∣ a 1, then a 1 = 0 => a = 1∙
a =1 or p-1 if a = a’
i.e., 1 and p 1 are their own inverses.
If a’ ≠ a, excluding 1 and p 1, the remaining p 3 residues 2, 3, 4, …, (p 3), (p 2) can
be grouped into p 3 pairs of the type a, a’ such that aa’ ≡ 1 (mod p)
2
Multiplying all these pairs together we get, 2∙3∙4...(p3)(p2)≡l (mod p )
1.2 ∙ 3 ∙ 4 ... (p2) (p1)≡ p 1mod p )
(p1) ! ≡ 1 (mod p ) ( Since p – 1 ≡-1 (mod p))
Hence the theorem.
This can be rewritten as (p 1)! + 1 ≡ 0 (mod p)
p ∣ (p l)! + l,
which is the result suggested by Wilson.
1ii) np !
1 mod p
n
Let p be a prime and n any positive integer. Prove that n
n !p
Proof:
First, we can make an observation. Let a be any positive integer congruent to 1 modulo p.
Then by Wilson‟s theorem , a(a 1)...(a (p 2)) (p 1)! 1(mod p)
In other words, the product of the p-1 integers between any two consecutive multiples of p is
congruent to -1 mod p.
(np)! (np)!
Then
n!pn p.2p.3p...(np)
n
r 1 p 1 ... r 1 p (p 1)
r 1
n
(p 1)!(mod p)
r 1
n
(1)(mod p)
r 1
(1) n (mod p)
2i) State and prove Fermat‟s little theorem. [NOV/DEC 20]
Statement:
If p is a prime and a is any integer not divisible by p, then a 1(mod p)
p 1
Proof:
Given p is a prime and a is any integer not divisible by p
When an integer is divided by p, the set of possible remainders are 0, 1, 2, 3, ...,p 1
Consider the set of integers 1 a, 2 a,3 a,....( p 1) a --------------(1)
Suppose ia ≡ 0(mod p), then p ia.
But p a .∙. p i, which is impossible, since i < p.
Ia 0(mod p) for i = 1, 2, ...,p 1.
So, no term of (1) is zero.
Next we prove they are all distinct
Suppose ia ≡ ja(mod p), where 1≤ i,j≤ p1.
Then (i j)a ≡ 0(mod p) p (i j) a
Since pa, pij and i, j < p i j < p.
Page 47 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
i – j = 0 i ≡ j(mod p)
.∙. i≠ j ia ≠ ja.
This means, no two of the integers in (1) are congruent modulo p.
.∙. The least residues (or remainders) of the integers a, 2a, 3a, ...,(p l)a modulo p are the
same as the integers 1, 2, 3, ...,p 1 in some order.
So, their products are congruent modulo p.
A . 2 a ∙ 3 a ... (p l) a ≡ 1 ∙2 ∙ 3 ... (p 1) (mod p)
l∙2∙3...(p l)∙ a p-1 ≡ (p l)!(mod p)
(p l)! ap-1 ≡ (p-l)!(mod p)
a p-1 ≡l(mod p) (since p (p-l))
The result ap-1 ≡ l(mod p) is equivalent to a p ≡ a (mod p).
2ii) 1947
Find the remainder when 24 is divided by 17
Solution.
We have to find the remainder when 241947 is divided by 17.
Here a = 24, p = 17
We know 17 is a prime & 17∣24
.∙. By Fermat‟s theorem, 24l7-1 ≡ 1(mod 17)
2416 ≡1(mod 17)
.∙. (2416)121 ≡1121(mod 17)
241936 ≡ 1(mod 17)
Now
241947 = 241936+11= 241936 .2411
242 = 576≡ -2(mod 17)
.∙. (242)2 ≡ (2)2(mod 17)
244 ≡4(mod 17)
(244)2 ≡42(mod 17)
8
24 ≡ 16(mod 17)
≡l(mod 17)
24 = 24 .242.24 ≡ (l)( 2). 7(mod 17)
11 8
≡ 14(mod 17)
.∙. 241947 ≡ 14(mod 17)
≡ 14(mod 17)
.∙. the remainder is 14 when 241947 is divided by 17.
3i) State and prove Euler‟s theorem.
Statement:
Let m be a positive integer and a be any integer such that (a, m) = 1. Then a Φ (m) ≡ 1(mod m).
Proof :
Given m is a positive integer and a is any integer such that (a, m) = 1.
Let r1, r2, ...,r Φ(m) be all the positive integers < m and relatively prime to m.
Since ri rj < m, clearly ri ≠ rj (mod m) if i ≠ j
Consider the products ar1, ar2, ...,ar Φ(m)
Since (a, m) = 1,ari ≠ arj (mod m) if i ≠ j
we find ar1, ar2, ...,ar Φ(m) mod m are distinct.
We now prove (ari, m) = 1
For, suppose (ari, m)> 1, then let p be a prime factor of (ari, m) = d.
.∙. p ari and p m
p a or p ri and p m.
If p ri and p m then, (ri,m) ≠ 1, a contradiction.
If p a and p m, then p (a, m) (a,m) 1, which is again a contradiction.
.∙. (ari∙,m) = l, i = 1,2,3, ...,Φ(m)
Page 48 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
.∙. Φ(m) least residues ar1, ar2, ...,ar Φ(m) modulo m are distinct and relatively prime to m.
So, they are the same as integers r1, r2, ...,r Φ(m), in some order modulo m.
.∙. their product ar1 ar2 ... ar Φ(m) r1 r2 ... r Φ(m) (mod m)
a Φ(m) r1 . r2,, rΦ(m) ≡ r1r2.. r Φ(m) (mod m)
Since each ri is relatively prime to m, (r1r2.. r Φ(m), m) = 1
We get a Φ(m) ≡ 1(mod m)
3ii) Using Euler‟s theorem, find the remainder when2451040 is divided by 18. [NOV/DEC 19]
Solution.
We have to find the remainder when 2451040 is divided by 18.
Here a = 245 = 5 ∙ 72 and m = 18 = 32 ∙ 2 , (a, m) = 1
Hence by Euler‟s theorem, a (m) ≡ 1(mod m)
245 (m) ≡ 1(mod m)
(18) (32 .2)
(3 2 ). (2)
2
1
3 1 .1 6
3
245 1(mod18)
6
(2456 )173 1173 (mod18)
2451038 1(mod18)
2451040 2451038 2
2451038 2452
But 245 11(mod18)
2452 ≡ 112 (mod 18)
≡121 (mod 18)
≡ 13 (mod 18)
l040
245 ≡ 1 ∙ 13 (mod 18)
≡ 13 (mod 18)
.∙. the remainder is 13 when 2451040 is divided by 18.
4i) If n p1e1 p2e2 ...pk ek is the canonical decomposition of a positive integer n then derive the
formula for the phi function ( n) and use it to find (6860)& (6125)
[NOV/DEC 19, 20]
Proof:
To prove :
If p is prime and e any positive integer then ( p e ) p e p e 1 p e (1 1p )
( pe ) number of positive integers pe and relatively prime to it
= {number of positive integers pe }-{ number of positive integers pe
and not relatively prime to it}
The number of positive integers pe is pe (because they are 1, 2, 3, ..., pe )
The number of positive integers pe and not prime to it are the various multiples of p.
They are p, 2 p, 3 p, .....,( pe1 ) p
The number of such numbers pe1
Hence ( p e ) p e p e 1 p e (1 1p )
Page 49 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
Since ( p e ) p e p e 1 p e (1 1p ) is a multiplicative function,
(n) ( p1e p2e ... pke ) ( p1e ) ( p2e )... ( pke )
p1e (1 p11 ) p2e (1 p12 )... pke (1 1
pk )
p1e p2e ... pke (1 p11 )(1 p12 )...(1 1
pk )
n(1 p11 )(1 p12 )...(1 1
pk )
To find (6860) :
(6860) (22 ). (5). (73 )
1 1
22 1 4.73 1 252
2 7
To find (6125) :
(6125) (53 ). (7 2 )
1 1
53 1 .7 2 1 4200
5 7
4ii) Prove that and are multiplicative functions.
Proof:
We know that is multiplicative if f is multiplicative.
(i) To prove is multiplicative
If f(d) = , is constant for each d/n
If are two divisors ( ) = 1, then f ( ) = 1,
;
f( )=
So, constant function is multiplicative.
Then
If (m,n)=1, then F(mn) = F(m) F(n)
So is multiplicative.
(ii) To prove is multiplicative
Take f(d)=d, identity function
If are two divisors and , then f ( )= =
f is multiplicative
Hence
For (m,n)=1 , F(mn)=F(m) F(n)
Then
So is multiplicative.
and are multiplicative functions.
5 Define Euler phi function and prove that it is multiplicative.
Solution:
Euler phi function:
Let : N N be a function defined by
(1)= 1 and
for n>1 (n)=the number of positive integer ≤ n and relative prime to n.
Page 50 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
To prove that it is multiplicative:
Let m and n be positive integers such that (m, n) = 1.
To prove (mn) = (m) (n)
Arrange the mn integers 1, 2, 3, ..., mn in m rows of n numbers each.
1 m 1 2m 1 3m 1 ... (n 1)m 1
2 m 2 2m 2 3m 2 ... (n 1)m 2
3 m 3 2m 3 3m 3 ... (n 1)m 3
: : : : : :
: : : : : :
r row r m r 2m r 3m r ... (n 1)m r
th
: : : : : :
: : : : : :
m 2m 3m 4m ... nm
Let r be a positive integer ≤ m such that (r, m) > 1.
We will now show that no element of the rth row in the array is relatively prime to mn.
Let d = (r, m). Then d r and d m d km + r for any integer k
This means d is a factor of every element in the rth row.
Thus, no element in the rth row is relatively prime to m and hence to mn if (r, m ) > 1.
In other words,
the elements in the array relatively prime to mn come from the rth row only if (r, m) = 1.
Since r < m and relatively prime to m, we find there are φ(m) such integers r and have φ(m)
such rows.
Now let us consider the rth row where (r, m) = 1.
The elements in the rth row are r, m + r, 2m + r, ..., (n-1)m + r.
When they are divided by n, the remainders are 0, 1, 2, ..., n - 1 in some order of which φ(n)
are relatively prime to n.
Therefore, exactly φ(n) elements in the rth row are relatively prime to n and hence to mn.
Thus there are φ(m) rows containing positive integers relatively prime to mn and each row
contain φ(n) elements relatively prime to it.
Hence the array contains φ(m) φ(n) positive integers ≤ mn and relatively prime to mn.
That is φ(mn) = φ(m) φ(n).
Hence φ is multiplicative function.
6i)
If p is prime and e any positive integer then prove that pe pe pe1 . Also show that
n
n when n 2k
2
Proof:
( pe ) number of positive integers pe and relatively prime to it
= {number of positive integers pe }-{ number of positive integers pe
and not relatively prime to it}
The number of positive integers pe is pe (because they are 1, 2, 3, ..., pe )
The number of positive integers pe and not prime to it are the various multiples of p.
They are p, 2 p, 3 p, .....,( pe1 ) p
The number of such numbers pe1
Page 51 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
DOWNLOADED FROM
MA8551 – Algebra STUCOR
and Number Theory APP Department of CSE / IT 2021-2022
Hence pe pe pe1
n
To prove that n when n 2k
2
Given n 2 k
1
(n) (2k ) 2k 1
2
1 n
2k .
2 2
2p 1 1
6ii) Find the primes p for which is a square.
p
Solution:
2 p 1 1 2
Suppose n for some positive integer n. Then 2 p1 1 p n2
p
Clearly both p and n must be odd.
Let p=2k+1 for some positive integer k.
Then 22k 1 p n2 (2k 1)(2k 1) pn2
Suppose (2k 1) is a perfect square, (2k 1) r 2 2k r 2 1
2
2 p 1 22k (2k )2 r 2 1
Since r≥1 and is odd, r = 2i + 1 for some integer i ≥ 0.
Then r2 = (2i + 1)2 has to be an odd number.
But r2 + 1= 2k r2 + 1 has to divide 2.
r2 + 1 = 1 or 2.
r =0 or 1
p 1
r 0, 2 (02 1)2 1 p=0 which is not possible
r 1, 2 p1 (12 1)2 4 p=3
Suppose (2k 1) is a perfect square
(2k 1) s 2 2k s 2 1
2 p 1 s 1 s 1
2 2
Then both s -1 and s+1 both must be the factors of 2
s 1 1 or 2, & s 1 1 or 2 s 0, 1, 2 or 3
If s 0; 2 p 1 0 1 0 1 1 p 1 which is not possible
2 2
If s 1; 2 p 1 1 1 1 1 0 which is not possible
2 2
If s 2; 2 p 1 2 1 2 1 9 which is not possible
2 2
If s 3; 2 p 1 3 1 3 1 26 p 7 . Thus p must be 3 or 7
2 2
Page 52 of 52
ALSO REFER LAST YEAR QUESTION PAPERS IN STUCOR APP
You might also like
- Abstract Algebra BSC Detailed Answers FinalNo ratings yetAbstract Algebra BSC Detailed Answers Final8 pages
- 4 - 03-02-2021 - 11-50-12 - Abstract Algebra - Paper Code - 20MAT21C1No ratings yet4 - 03-02-2021 - 11-50-12 - Abstract Algebra - Paper Code - 20MAT21C1142 pages
- Unit 4 QB (22-23) Part - B With AnswersNo ratings yetUnit 4 QB (22-23) Part - B With Answers13 pages
- Discrete Mathematics: Submitted by Komal Applied ScienceNo ratings yetDiscrete Mathematics: Submitted by Komal Applied Science29 pages
- Ma8551 - Ant Question Bank For Unit - I With SolutionNo ratings yetMa8551 - Ant Question Bank For Unit - I With Solution17 pages
- Ma3354 DM Unit 4 Part A, B Question and AnswerNo ratings yetMa3354 DM Unit 4 Part A, B Question and Answer8 pages
- General Wiring Price List - June 01st 2021No ratings yetGeneral Wiring Price List - June 01st 20211 page
- Skye Howard - TRUE KETO - Smoothies & ShakesNo ratings yetSkye Howard - TRUE KETO - Smoothies & Shakes67 pages
- Incident Lessons Learned - Compressor Static Fire April 2018No ratings yetIncident Lessons Learned - Compressor Static Fire April 20185 pages
- 3 Phase Wiring Guide for Multi-Story Buildings100% (1)3 Phase Wiring Guide for Multi-Story Buildings5 pages
- PHP Web Security: XSS, SQLi, File UploadsNo ratings yetPHP Web Security: XSS, SQLi, File Uploads13 pages
- Presentation Puna Ptipk Mapin 20151028 EnglishNo ratings yetPresentation Puna Ptipk Mapin 20151028 English34 pages
- Cognitive Stimulation Using Non-Immersive Virtual Reality Tasks in Children With Learning Disabilities.No ratings yetCognitive Stimulation Using Non-Immersive Virtual Reality Tasks in Children With Learning Disabilities.159 pages
- B.bachelor of Science in Real Estate Management100% (1)B.bachelor of Science in Real Estate Management11 pages