Mid-I and Mid-II Question Bank with BLOOM’s

Code: C0B23 MR 22(2022-23)

MALLA REDDY ENGINEERING COLLEGE (AUTONOMOUS)
II B.Tech. IV Semester (MR 22-2022-23 Admitted Students)
I Mid Examination Question Bank

Subject: NUMBER THEORY (B0B23) Branch: CSE (Cyber Security)

Q. Questions Marks BT C
No. Level O
Module-I
1. Explain state and prove Euclidean Algorithm? 5 L3 1
2. By using the Euclidean Algorithm find the G.C.D of 1769 & 2378 and also find x and y 5 L3 1
such that (1769, 2378)=1769x+2378y.
3. Explain state and prove Division Algorithm? 5 L4 1
4. Explain state and prove Fundamental theorem of Arithmetic ? 5 L3 1
5. Find the general solution of the equation (i) 70x+112y =168 5 L3 1
(ii) 39x – 56y=11.
6. Solve the Linear Diophantine equation 858x+253y=33 . 5 L3 1
7. Prove that if a=qb+r, where a,b,q and r are integers, then gcd(a,b)=gcd(b,r) 5 L4 1
8. If x0,y0 is any particular solution of this equation ,then all other solutions are 5 L3 1
given by x=x0+(b/d)t, y=y0-(a/d)t,
where t is an arbitrary integer.
Module-II

1. Write the definition and properties of congruence? 5 L3 2

2. i)prove that if C>0 then a  b(mod m) iff ac bc(modmc). 2 L3 2
89
ii) show that 2440 −1 3

3. Prove that a  b(mod m) ⟺ a & b give the same remainder when divided by m. 5 L3 2
4. i)Prove that if a  b(mod m) and 0≤ |𝑏 − 𝑎|<m then a=b. 2 L4 2
 ii) find the remainder when the sum 1!+2!+3!+4!+.............+100! Is divided by 12. 3
5. find the remainder when (4444)4444 is divided by 9? 5 L4 2

6. Explain state and prove Euler –Fermat theorem ? 5 L4 2

7. Find the solution of the given linear congruences.14x 12(mod 18). 5 L4 2
8. Solve the system of linear congruences by using chinese remainder theorem x 2(mod3) 5 L4 2
x 3(mod5), x 2(mod7).
Module-III

1. 1 1 𝑖𝑓 𝑛 = 1 5 L3 3
Prove that if n≥ 1 we have ∑𝑑/𝑛 𝜇(𝑑) =[𝑛] = {
0 𝑖𝑓 𝑛 > 1
𝑛
2. Prove that if n≥ 1 𝑤𝑒 ℎ𝑎𝑣𝑒 𝜙(𝑛) = ∑𝑑/𝑛 𝜇(𝑑). (𝑑) 5 L3 3

3. 1 5 L3 3
Prove that if n≥ 1 𝑤𝑒 ℎ𝑎𝑣𝑒 𝜙(𝑛) = 𝑛 ∏𝑝/𝑛 [1 − 𝑝]

4. Find (630) 𝑎𝑛𝑑 𝜎(630) . 5 L3 3

Signature of the faculty Signature of HoD

MALLA REDDY ENGINEERING COLLEGE (AUTONOMOUS)

II B.Tech. II Semester (MR-20) I Mid Question Bank 2021-22(Objective)

Subject: Number Theory (A0B23) Branch: CSE (CS)

Name of the Faculty: Dr. K. Malleswari
 MULTIPLE CHOICE QUESTIONS

S.N QUESTION ANSWER

o.
The linear combination of gcd(252, 198) = 18 is? A
1 a) 252*4 – 198*5 b) 252*5 – 198*4 c) 252*5 – 198*2 d) 252*4 – 198*4
2 The inverse of 3 modulo 7 is? B
a) -1 b) -2 c) -3 d)-4

3 The linear combination of gcd(10, 11) = 1 can be written as _________ A

a) (-1)*10 + 1*11 b) (-2)*10 + 2*11 c) 1*10 + (-1)*11 d) (-1)*10 + 2*11
4 The solution of the linear congruence 4x = 5(mod 9) is? B
a) 6(mod 9) b) 8(mod 9) c) 9(mod 9) d) 10(mod 9)

5 The linear combination of gcd(117, 213) = 3 can be written as _________ A

a) 11*213 + (-20)*117 b) 10*213 + (-20)*117c) 11*117 + (-20)*213d) 20*213 +
(-25)*117

6 . The inverse of 7 modulo 26 is? C

a) 12 b) 14 c) 15 d) 20
7 For some number b, (1⁄b)-n is equal to _________ C
a) -bn b) nb c) bn d) none of the mentioned
8 If ab = 1, where a and b are real numbers then? A
a) a = b-1 b) b = a c) a = b = 2 d) none of the mentioned
9 If a is a real number than a is defined as _________
0 A
a) 0 b) a c) 1 d) -1
10 For some number a, b and c, ca x cb is equal to _________ B
a) ca-b b) ca+b c) c d) none of the mentioned
11 For some number a, b and c, c x cb is equal to _________
a A
a) ca-b b) ca+b c) c d) none of the mentioned
If 0 is not equal to zero then which of the values a cannot take _________
a

12 a) 1 b) 2 c) -1 d)0 D

13 For some number a, b and c, ac x bc is equal to _________ A

a) (ab)c b) (ac)b c) (cb)a d) None of the mentioned

14 If 2a-b = 1 then the value of a-b is equal to _________

a) 1 b) 0 c) 2 d) none of the mentioned B
15 The prime factorization of 1001 is________ C

a)73.11.13 b) 72.11.13 c)7.11.13 d)7.113.13

16 Which positive integer less than 21 are relatively prime to 21? B

a)18 b) 19 c) 21 d) 24
17 The greatest common divisor of 0 and 5 is________ B
a)0 b)1 c)2 d)5

18 The greatest common divisor of 313.517 and 212.35 is____ D

a)30 b) 31 c) 33 d) 35

19 The greatest common divisor of 0 and 5 is____ B

a) 0 b)1 c)2 d)5

20 The LCM of 3 and 21 is_____if gcd(3,21)=3. C

a)3 b)12 c)21 d)42

21 The least common multiple of 41.42 and 42.41 is_______ D

a)42 b)41 c)84 d)41.42

22 ℚ is the set of rational numbers of the form m/n such that A

(a)m, n ∈ ℤ, n ≠ 0 (b)m, n ∈ 𝕎, n ≠ 0 (c)m, n ∈ ℤ, n = 0 (d)m, n ∈ ℕ, n ≠ 0

23 For a real number x, |x| denotes the absolute value of x such that D
(a)|x| = x if x ≥ 0 (b)|x| = -x if x < 0 (c)|x| = x if x ≤ 0 (d)Both a and b

24 The number of elements in a set S is denoted by A

(a)# S (b)S # (c)* S (d)S *

25 The real part and imaginary parts of S are denoted by A

(a)Re(S);Im(S) (b)Real(S);Imaginary(S) (c)R(S);I(S) (d)Rea(S);Imag(S)

26 Both addition and multiplication in ℤ are _________. D

(a)Commutative (b)Associative (c)Distributive (d)All of these

27 If 𝑎 = 𝑞𝑏 for some integers q and 𝑎, 𝑏 ≠ 0 then we say that D

(a)b divides a (b)b is a factor of a (c)a is a multiple of b (d)All of these

28 If b ≠ 0 ∈ ℤ ,then which statement is correct? A

(a)b|0 (b)b∤0 (c)0|b (d)None of these

29 For any integer a ∈ ℤ, mark the correct statement. B

(a)a|1 (b)1|a (c)0|a (d)None of these

30 If S is a non-empty set of non-empty integers, then S has a least element c ∈ S, s.t. A

(a)c ≤ x, ∀ x ∈ S (b)c < x, ∀ x ∈ S (c)x ≤ c, ∀ x ∈ S (d)None of the above

31 k+1∈ S, thenBy Principle of Induction, a set S of positive integers s.t. 1∈ S and k∈ S B

(a)S = 𝕎 (b)S = ℕ (c)S = ℚ (d)S = ℤ
32 If a, b∈ ℤ and b≠ 0, then ∃ a unique pair of integers q and r, s.t. a = bq + r where ______. D
(a)0 ≤ r ≤ |b| (b)0 ≤ r < |b| (c)0 > r > |b| (d)0 ≤ r ≤ b

33 If n, k∈ ℤ s.t. n is the square of an odd integer, then perfect square must be of the form A
______. (a)8k + 1 (b)7k + 1 (c)6k + 1 (d)9k + 1
34 Any _______ has a unique decimal expansion. B
(a)Integer (b)Positive Integer (c)Real number (d)Negative Integer

35 Which one can be written as a linear combination of any 2 integers involved? A

(a)GCD (b)Decimal expansion (c)LCM (d)None of these
36 Any positive integer n can be written uniquely as 𝑛 = 𝑐𝑘. 𝑏 𝑘 + 𝑐𝑘−1. 𝑏 𝑘−1 + ⋯ + 𝑐1. 𝑏 + D
𝑐0, if we’ve the following conditions satisfied
(a)b > 1 (b)0 ≤ ci < b (c)ck ≠ 0 (d)All of these

37 If a and b are two integers, then ∃ some integers x and y such that A
(a) gcd(a, b) = ax + by (b) gcd(a, b) = ax – by (c) gcd(a, b) = axn + byn (d) gcd(a, b) =
(ax + by)n

38 Which one of the statements is equal to 8? D

(a) gcd(1, 8) (b) gcd(-32, 44) (c) gcd(12, 42) (d) gcd(-32, 96)

39 The greatest common divisor of 2 integers a and b is the unique positive integer d if D
(a)d | a (b)d | b (c)If c | a ∧ c | b then c ≤ d (d)All of these

40 If c | a, c | b and d = gcd(a, b) C
(a)c ≤ d (b)c | d (c)Both a and b (d)None of these

41 If a| b and b| c, then A
(a) a| c (b) ac| bd (c) ma| mb (d) |d| ≤ |a|

42 If a| b and c| d, then B
(a) a| c (b) ac| bd (c) ma| mb (d) |d| ≤ |a|

43 If m ≠ 0 ∈ ℤ, then a| b iff C
(a) a| c (b) ac| bd (c) ma| mb (d) |d| ≤ |a|

44 If d ≠ 0 ∈ ℤ s.t. d| a and a ≠ 0, then D

(a) a| c (b) ac| bd (c) ma| mb (d) |d| ≤ |a|

45 If a| x and a| y, then D
(a) a| c (b) ac| bd (c) ma| mb (d) a| (cx + dy)

46 a| b and b| a iff D
(a) a| c (b) ac| bd (c) ma| mb (d) a = ±b.

47 An efficient way of obtaining the gcd is known as ________. C

 (a)Well ordering principle (b)Division Algorithm (c)Euclid’s Algorithm (d)None of
above

48 If 𝑎 = 𝑞𝑏 + 𝑟, then B
(a)gcd(a, b) ≠ gcd(b, r) (b)gcd(a, b) = gcd(b, r) (c)gcd(a, b) = gcd (q, r) (d)None of
these

49 Two consecutive terms of a Fibonacci sequence are ______. A

(a)Coprime (b)Composite (c)Inverses (d)None of these

50 The nth term of Fibonacci sequence is given by 𝐹𝑛 = __________. B

(a)𝐹𝑛−1 + 𝐹𝑛−2 ∀ 𝑛 > 2 (b)𝑭𝒏−𝟏 + 𝑭𝒏−𝟐 ∀ 𝒏 ≥ 𝟐 (c)𝐹𝑛−1 − 𝐹𝑛−2 ∀ 𝑛 ≥ 2
(d)None of these

51 Which of the following is a Fibonacci sequence? D

(a)1, 1, 2, 3, 4, … (b)1, 2, 3, 5, … (c)1, 2, 3, 3, 8, … (d)1, 1, 2, 3, 5, 8, …

52 In Fibonacci sequence, the gcd(𝐹𝑛+1, 𝐹𝑛) = __________ A

(a)1 (b)2 (c)3 (d)0

53 If gcd(a, b) = 1 for any two integers a and b, then a and b are _________. D
(a)Relatively Prime (b)Co-prime (c)Multiples of each other (d)Both a and b

54 Which of the following are coprime? D

(a)13, 26 (b)4, 29 (c)5, 12 (d)Both b and c

55 If d = gcd(a, b), then _______ are coprime. A

(a)a/d and b/d (b)ad and bd (c)d/a and d/b (d)All of these

56 If a and b are coprime then D

(a) a | ca | bc (b)a | c (a)a | bc (c)lcm(a, b) = ab (d)All of these

57 What is the formula for fermat number----- D

𝑛
a)2n b) 22 c)22n d)22

58 Diophantine equations are named after a Greek mathematician ________. A

(a)Diophantus (b)Diophantine (c)Diophanticus (d)None of these

59 The linear Diophantine equation ax + by = c with d = gcd(a, b) has a solution in integers D

iff
(a)d | c (b)c | d (c)d | (ax + by) (d)Both a and c

60 Let d = gcd(a, b) and n∈ ℕ. If d| c and (𝑥0, 𝑦0) is a solution of linear Diophantine A

 equation i.e. 𝑎𝑥 + 𝑏𝑦 = 𝑐, then all integral solutions are given by
(a) (𝒙, 𝒚) = (𝒙𝟎 + 𝒃𝒏 𝒅 , 𝒚𝟎 − 𝒂𝒏 𝒅 ) (b) (𝑥, 𝑦) = (𝑥0 − 𝑏𝑛 𝑑 , 𝑦0 + 𝑎𝑛 𝑑 )
(c) (𝑥, 𝑦) = (𝑥0 + 𝑎𝑛 𝑑 , 𝑦0 − 𝑏𝑛 𝑑 ) (d) (𝑥, 𝑦) = (𝑥0 − 𝑎𝑛 𝑑 , 𝑦0 + 𝑏𝑛 𝑑 )

61 Diophantine equation is an equation that seeks its solution from the set of ______. A
(a)Integers (b)Rational Numbers (c)Complex Numbers (d)Real Numbers
62 Which one is true for the Diophantine equation 5x + 7y = 10? B
(a)(5, 10)| 10 (b)(5, 7)| 10 (c)(5, 7)∤ 10 (d)None of these

63 A valid solution for the Diophantine linear equation 3x + 7y = 10 is ______. D

(a)(1, 2) (b)(2, 1) (c)(0, 3) (d)(1, 1)

64 If d = (a, b) s.t. d| c for ax + by = c, then by Extended Euclidean Algorithm, we’ve A

(a)d = a(s) + b(t) (b)d = 2a(s) + b(t) (c)d = a(s) + 2b(t) (d)None of these

65* If acbc(mod mc) and if d=(m,c) then A

a) ab(mod (m/d) b) ba(mod (m/d) c) ab(mod (m/a) d) None of these
66 Which of the following Diophantine equations has no solution in integers? B
(a)3x + 7y = 10 (b)8x – 12y = 5 (c)6x + 12y = 96 (d)5x + 10y = 25

67 If a and b are coprime, then the solution of Diophantine equation ax + by = c _____ A

exist(s). (a)Always (b)May or may not (c)Never (d)Partially
68 If (a, b)=1 and a, b, c > 0, then no. of positive solutions of ax + by = c is the no. of t such A
that
(a)− 𝒙 ∗ 𝒃 < 𝒕 < 𝒚 ∗ 𝒂 (b)− 𝑥 ∗ 𝑏 > 𝑡 > 𝑦 ∗ 𝑎 (c)− 𝑥 ∗ 𝑎 < 𝑡 < 𝑦 ∗ 𝑎 (d)− 𝑥 ∗ 𝑎 < 𝑡 < 𝑦 ∗ 𝑏

69 Let m be a positive integer. Two integers a and b are congruent modulo m iff ______. A
(a)m|(a – b) (b)m|(a + b) (c)m|(a × b) (d)Both b and c

70 If a positive integer m divides the difference of 2 integers a and b i.e. m|(a-b), then A
(a) a  b(mod m) (b) a = b(mod m) (c) a  m(mod b) (d) Both a and b

71 Which of the congruence statements is false? A

(a) 25  15(mod 5) (b) 13  10(mod 3) c) 25  9(mod 4) (d) 10  3(mod 2)

72 If a  b(mod m) the we have A

(a)m as the modulus (b)b as the residue (c)a as the modulus (d)Both a and b

73 If 2 integers are congruent modulo m then the residue r from the set {0, 1, 2, …, m-1} is B
called ___
(a)Least residue (b)Least positive residue (c)Last positive residue (d)Capital
residue

74 If S modulo m is a complete residue system(CRS), then if x ∈ S, a ∈ ℤ and m is the D

modulus, we’ve
 (a) a  x(mod m) (b) x  a (mod m) (c) m  a (mod b) (d) Both a and b

75 Congruence is not ________. D

(a)Symmetric (b)Reflexive (c)Transitive (d)Antisymmetric

76 If a  b(mod m) and c  d (mod m) ,then D

(a) (a + c)  (b + d )(mod m) (b) (a − c)  (b − d )(mod m) (c) (ac )  (bd )(mod m)
(d)All of these

77 For any common divisor of a, b and m, i.e. c| a, b, m ; then a  b(mod m) iff D

a b m b a m m b a
(a)   mod  (b)   mod  (c)   mod  (d)Both (a) and (b)
c c c c c c c c c

78 If a  b(mod m) then for any c  Z , A

a b m
(a) ca  cb(mod m) (b) c + a  c + b(mod m) (c)  (mod ) (d)
c c c
a c  b c (mod m)

79 The necessary condition for Diophantine equation ax + by = c to have integral solutions A

is that (a)gcd(a, b)| c (b)c| gcd(a, b) (c)Both a and b (d)None of these

80 Which of the following Diophantine equations cannot be solved? A

(a)6x + 51y = 22 (b)33x + 14y = 115 (c)7x + 28y = 77 (d)54x + 18y = 36

81 The smallest positive integer that is the multiple of 2 numbers a and b is called _____. B
(a)HCF (b)LCM (c)GCD (d)None of these

82 The LCM of any two integers a and b is denoted by C

(a)(a, b) (b)[a, b) (c)[a, b] (d){a, b}

83 The least common multiple of 2 and 3 is B

(a)2 (b)6 (c)3 (d)23

84 For any two positive integers a and b, the LCM and GCD are related as D
(a)(a, b)[a, b] = a/b (b)(a, b)[a, b] = a + b (c)(a, b)[a, b] = a – b (d)(a, b)[a, b] = ab

85 A prime number is an integer p > 1, which has no positive divisors other than _____. C
(a)1 (b)0 (c)1 and itself (d)None of these

86 If p is a prime and p| ab, then D

(a)p| a (b)p| a but p∤ b (c)p| b (d)p| a or p| b

87 Any integer n can be written as the product of ______. D

 (a)Naturals (b)Composites (c)Complex Numbers (d)Primes

88 The representation of a number into product of primes is _______. B

(a)Separate (b)Unique up to the order of factors (c)Not unique (d)Infinite
Number

89 The sequence of composite numbers is given by A

(a)n!+2, n!+3, … ,n!+n (b)n!+2, n!+3, … ,n!+n+1 (c)n!+1, n!+2, … ,n!+n (d)None of
these

90 Let a and b be two integers, then a divides b if D

(a)b is a multiple of a (b)a is a multiple of b (c)a is a divisor of b (d)Both a and c

91 If c>0 then a=b(mod m) iff B

a) a=b(mod m) b) ac=bc(mod mc) c) b=a(mod m) d)None of these
92 The value of 52003 mod 7 is? A
a) 3 b) 4 c)8 d) 9

93 Let a, b, and c be integers, then C

a)a/b and b/aa/c (b)a | b and b | c a | (sb + tc), ∀ s, t ∈ ℤ
(c)Both a and b (d)None of these
94 Let a and b be positive integers, then ∃ unique integers q and r such that B
(a) b = aq - r with 0 ≤ r < a (b) b = aq + r with 0 ≤ r < a
(c)a = bq + r with 0 ≤ r < a (d)b = aq + r with 0 > r ≥ a
95 The greatest common divisor of a and b is the ______ linear combination of a and b. A
(a)Smallest positive (b)Smallest negative (c)Largest positive (d)Only positive
96 If a|c, b/c and (a, b) = 1, then D
a)c|ab (b) bc|a (c) a|bc (d) ab|c
97 If (a, b) = (a, c) = 1, then B
(a)(ab, c) = 1 (b) (a, bc) = 1 (c)(a, b + c) = 1 (d)(a, b – c) = 1
98 Which name matches the statement if a|bc and (a, b) = 1, then a|c ? C
(a) Division Algorithm (b)Fermat’s Theorem (c) Euclid’s Lemma (d)Euclidean Algorithm

99 Every integer n is product of primes such that B

(a)n > 2 (b)n > 1 (c)n < 1 (d)n > 0
100 According to Euclid, there exist how many primes? C
(a)A few (b)Finite (c)Infinite (d)None of these
101 The set of integers such that every integer is congruent modulo m to exactly one B
integer of the set is called ______ modulo m.
(a)Reduced Residue System(RRS) (b)Complete Residue System(CRS)
(c)Elementary Residue System(ERS) (d)None of these
102 Which set of integers forms a complete residue system for modulus 5? B
(a)1, 2, 3, 4, 5 (b)6, 7, 8, 9, 10 (c)0, 1, 2, 3, 6 (d)None of these
103 A reduced residue system modulo m is a set of integers 𝑟𝑖 s.t A
(a)(𝑟i , 𝑚)= 1 (b)[ri , m]= 1 (c)(𝑟i , 𝑚) ≠ 1 (d)None of these
104 The RRS modulo 6 contains the set of integers _____. C
(a){0, 5} (b){1, 2,3} (c){1, 5} (d){1, 3, 6}
105 Let 𝑎𝑘10𝑘 + 𝑎(𝑘−1)10𝑘−1 + ⋯ + 𝑎0 is the decimal expansion of the integer n, then n is B
divisible by 2r , iff
(a)number has 2r digits (b) 2r | no. consisting of last r digits
(c)n is divisible by r (d) 2r| no. consisting of last 2r digits

106 Which number is not divisible by 8 = 23 ? B

(a)223317888 (b)12345678 (c)234789120 (d)976
107 Which number is divisible by 9? A
(a)12345678 (b)1234567 (c)123456 (d)12345
108 Linear congruence is of the form ______ . B
a)ax=b(mod m) (b)ax  b(mod m) (c)ax2 + bx = c(mod m) (d)Both a and b
109 Two integers s and t that are not congruent to each other w.r.t. mod m are said to be B
_____.
(a)Equivalent (b)Incongruent (c)Coprime (d)None of these
110 Let d = (a, m), then the congruence ax  b(mod m) has a solution iff C
(a)b| d (b)m| d (c)d| b (d)a| d
111 The solution of linear congruence 2x 1(mod 3) is---- A
(a)x  2(mod 3) (b)x 1(mod 3) (c)x 0(mod 3) (d)None of these
112 The solution of linear congruence 4x 1(mod 6) is ______ D
a) x 2(mod 6) b) x 3(mod 6) c) x 4(mod 6) (mod 6) d)None of these
113 The number of mutually incongruent solutions of linear congruence 42x90(mod 156) is D
(a)3 (b)2 (c)5 (d)6
114 A congruence of the form axb(mod m) is called ________. A
(a)Linear congruence (b)Coefficient congruence (c)Integral congruence (d)None of these
115 Which of the following is a valid solution to the congruence 2x1(mod 5)? A
a) x3(mod 5) b) x1(mod 5) c) x4(mod 5) d) x5(mod 5)

116 The elements in the solution set of a linear congruence are ________ to each other. A
(a)Always congruent (b)Maybe congruent (c)Never congruent (d)None of
these
117 If d = (a, m), then the congruence ax b(mod m) has a solution if A
(a)d| b (b)b| d (c)d| b-am (d)None of these
118 Which of the following is inverse of 3 mod 5? A
(a)2 (b)1 (c)3 (d)4
119 An integer a is said to be an inverse of an integer b w.r.t. mod m if D
(a)a  b(mod m) (b)ax  b(mod m) (c)ab  -1(mod m) (d)ab  1(mod m)
120 Which of the following are inverses of each other? D
(a)3, 7 w.r.t. mod 20 (b)2, 5 w.r.t. mod 9 (c)4, 7 w.r.t. mod 9 (d)All of these
121 If a is inverse of a* and b is inverse of b*, then ab is inverse of ____ w.r.t. mod m. C
(a)a* (b)b* (c)a*b * (d)None of these
122 Which of the following congruences is satisfied by the integer x = c = 3? D
a)2x 1(mod 5) (b)5x  1(mod 7) c)4x  1(mod 11) d)All of these
123 Let p be a prime and p doesn’t divide a. Then 𝑎p a(mod p).” is a statement of B
(a)Dirichlet’s Theorem (b)Fermat’s Little Theorem (c)Euclid’s Theorem (d)Wilson’s
Theorem
 124 How many even prime numbers exist? A
(a)Only one (b)Only 20 (c)Infinite many (d)No even prime exists
125 Let ab(modm) if d/a &d/m then C
a)d/a b)d/m c) d/b d) none of these

Signature of Faculty Signature of HOD

Code: C0B23 MR 22(2022-23)

MALLA REDDY ENGINEERING COLLEGE (AUTONOMOUS)
II B.Tech. IV Semester (MR 22-2022-23 Admitted Students)
II Mid Examination Question Bank

Subject: NUMBER THEORY (B0B23) Branch: CSE (Cyber Security)

Q. Questions Marks BT CO
No. Level
Module-III
1. Find the all the integer n such that 𝜙(𝑛) = 𝜙(2𝑛) 5 L3 3
2. (a) Verify that  (n) =  (n + 1) =  (n + 2) =  (n + 3) holds for n = 3655 5 L3 3
(b)When n = 957 show that  (n) =  (n + 1)
3. If n is a positive integer and p is a prime then the exponent of the highest power of p 5 L4 3

 n 
that divides n! is  p
k =1 
k 
.

4. (a) Show that the integers m = 3k .568 and n = 3k . 638 where k ≥ 0 satisfy 5 L3 3
simultaneously  (m) =  (n),  (m) =  (n) and  (m) =  (n)
(b)Find the highest power of 5 dividing 1000! and the highest power of 7 dividing
2000!
Module-IV

1. ℎ 5 L3 4
Prove that if a has exponent h modulo m, then 𝑎𝑘 has exponent 𝑑 , 𝑤ℎ𝑒𝑟𝑒 𝑑 =
 (ℎ, 𝑘)
2. List the primitive roots modulo 7? 5 L3 4
3. Prove that let a be an integer having exponent h modulo m i.e. ah ≡ 1 (modm). Then 5 L3 4
the following hold:
(i)If ak ≡ 1 (𝑚𝑜𝑑 𝑚), for some integer k,then h/k.
(ii) ai ≡ 𝑎 𝑗 (𝑚𝑜𝑑 𝑚) ⇔ i≡ j(mod h).

4. If a is a primitive, root modulo m; then 1,a,a2,........𝑎 𝜙(𝑚)−1 is a reduced residue system 5 L4 4

modulo.
5. Prove that let the integer a have order K modulo n then 𝑎 𝑘 ≡ 1 (mod n) iff k/h. 5 L4 4

6. Prove that there exist at least one primitive root modulo each prime p≥ 3 5 L4 4
𝑘
7. If the integer a has order k modulo n and h>0.then ah has order gcd (ℎ,𝑘) 𝑚𝑜𝑑𝑢𝑙𝑜 𝑛. 5 L4 4

8. solve the linear congruences by using Indices 11x3 ≡ 2 (mod 23) 5 L4 4

Module-V

1. Find the quadratic residues modulo 11& 13. 5 L3 5

2. Explain the state and prove the Euler’s criterion? 5 L3 5
3. Prove that Legendre’s symbol (n/p) is a completely multiplicative function of n .i.e 5 L4 5
𝑚.𝑛 𝑚 𝑛
if p is an odd prime ⇒ ( 𝑝
) = ( 𝑝 ) (𝑝 ) ∀ 𝑚, 𝑛

4. Prove that for every odd prime we have 5 L4 5

𝑝2−1 1 𝑖𝑓 𝑝 = ±1(𝑚𝑜𝑑8)
(2/p) = (−1) 8 ={
− 1 𝑖𝑓 𝑝 = ±3 (𝑚𝑜𝑑8)
5. Evaluate (219/383) by using quadratic reciprocity law? 5 L3 5
6. Explain the state and prove the Quadratic reciprocity law? 5 L3 5
7. Determine those odd primes p for which 3 is a quadratic residue and those for which it is a 5 L4 5
non -residue.
8. Evaluate (127/17) by using Gauss lemma? 5 L3 5
 Signature of Faculty Signature of HOD

MALLAREDDY ENGINEERING COLLEGE (AUTONOMOUS)

II B.Tech. IV Semester (MR-22) II MidQuestionBank 2022-23(Objective)

Subject: Number Theory (C0B23) Branch:CSE (CS)

Name of the Faculty: Dr. K. Malleswari

MULTIPLE CHOICE QUESTIONS

S.No. QUESTION ANSWER

1 A real valued or complex valued function defined on the set of natural number N is called-- B
-
a)Mobius function b) arithmetic function c)exponential function d)None of these
2 That is the value of 𝜇(4) − −−? C
a)1 b)2 c)0 d) -1
3 In this formula [x] denotes the greatest integer less than or equal to x A
a)[x]≤ 𝑥 b)x>[x] c)x<[x] d) [x]≥ 𝑥
4 The mobius function 𝜇 is defined as fallows B
a)n=1; 𝜇(2) = 1 b)n=1; 𝜇(1) = 1c)n=1; 𝜇(2) = 2 d)n=2; 𝜇(2) = 3
5 If n≥ 1 𝑤𝑒 ℎ𝑎𝑣𝑒 ∑𝑑/𝑛 𝜇(𝑑) =---- C
 a)2/n b)3/n c)1/n d) none of these
𝑛
6 If 𝜙(𝑛) = ∑𝑘=1 1 𝑖𝑠 − − − B
a)Mobius function b)Euler totient function c) arithmetic function d)None
7 If 𝜙(5) =--- A
a)4 b) 2 c)1 d)3
8 If p is a prime number 𝜙(p)=--- C
a)p b)q c)|𝑝| d)|𝑞|
9 If n≥ 1 we have ∑𝑑/𝑛 𝜙(𝑑)= A
a)n b)m c)d d)q
10 If n≥ 1 we have 𝜙(n)= B
𝑑 𝑛 𝑛
a)∑𝑑 𝜇 (𝑑 ) . ( ) b)∑𝑑 𝜇 (𝑑 ) . ( ) c)∑𝑑 𝜇(𝑛 ) . ( ) d) none of these
𝑛
𝑛 𝑛
𝑑 𝑛
𝑑

11 If n≥ 1 we have a product formula for 𝜙(n)= A

1 1 1 1
a)n∏𝑝/𝑛[1 − 𝑝] b)∏𝑝/𝑛[1 − 𝑝] c) n.∏𝑛/𝑛[1 − 𝑝] d) n.∏𝑝/𝑛[1 − 𝑛]
Find the value of 𝜙(210)?
12 a)58 b)48 c)53 d)44 B
13 Euler’s totient function has the following properties𝜙(𝑝𝛼 ) = A
a)𝑝𝛼 - 𝑝𝛼−1 b)𝑝2 - 𝑝𝛼−1 c) a)𝑝𝛼 - 𝑝𝛼−2 d)none of these
14 Euler’s totient function has the following properties 𝜙(𝑚𝑛) =
a)𝜙(𝑛)𝜙(𝑚𝑛).(d/ 𝜙(𝑚𝑛)) b) a)𝜙(𝑚)𝜙(𝑛).(d/ 𝜙(𝑑)) B
a)𝜙(𝑛)𝜙(𝑚𝑛).(d/ 𝜙(𝑛)) d) a)𝜙(𝑚)𝜙(𝑚𝑛).(d/ )𝜙(𝑚)
15 If (m, n)=1 then 𝜙(𝑚𝑛) = C
a) 𝜙(𝑚) ∗ 𝜙(𝑛) b) 𝜙(𝑚) − 𝜙(𝑛) c) 𝜙(𝑚). 𝜙(𝑛) d) 𝜙(𝑚) + 𝜙(𝑛)
16 𝜙(𝑛) 𝑖𝑠 even for n≥ 3 more over if n has r distinct odd prime factors then A
a)2r/ 𝜙(𝑛)b)2r/ 𝜙(𝑚)c)2n/ 𝜙(𝑛)d)2/ 𝜙(𝑛)
17 If p is odd prime (p-1) is even then 𝜙(𝑛) D
a)odd b) prime c) both a&b d)even
18 Suppose n>2 .If n is a power of 2 then n=2k with k≥ 2 then 𝜙(2𝑘 ) is B
a)odd b)even c)prime d) none of these
19 Final all the integers n such that 𝜙(𝑛)= C
2 1 𝑛 3
a)𝑛 b)𝑛 c) 2 d) a)𝑛
20 If n is an even integer and it is of the form n=2𝛼 .m where𝛼 ≥ B
1 𝑎𝑛𝑑 𝑚 𝑖𝑠 𝑎𝑛 𝑜𝑑𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟. 𝑡ℎ𝑒𝑛
a)(2𝛼 .m)=2 b)(2𝛼 .m)=1 c)(3𝛼 .m)=2 a)(2𝛼 .m)=5
21 If n is odd integer then A
a) 𝜙(𝑛) = 𝜙(2𝑛)b) 𝜙(𝑛) = 2. 𝜙(2𝑛)c) 𝜙(𝑛) = 2𝜙(𝑛)d) 𝜙(𝑛) = 𝜙(3𝑛)
22 If n is even integer then B
 a) 𝜙(𝑛) = 𝜙(2𝑛)b) 𝜙(𝑛) = 2. 𝜙(𝑛)c) 𝜙(𝑛) = 2𝜙(𝑛)d) 𝜙(𝑛) = 𝜙(3𝑛)
23 If every prime that divides m then prove that A
a) 𝜙(𝑛𝑚) = 𝑛𝜙(𝑚)b) 𝜙(𝑚) = 𝑛𝜙(𝑚)c) 𝜙(𝑛𝑚) = 𝑚𝜙(𝑚)d) 𝜙(𝑛𝑚) = 𝜙(𝑚)
24 If n is a positive integer 𝜙(𝑛 2 )=---- A
a)n 𝜙(𝑛) b) 𝜙(𝑛 2 )𝑛 c) 𝜙(𝑛 2 )𝑚 d)None
25 Arithmetic function N is define by N(n)=--- C
a)n ∀ 𝑛 ∈ 𝑅+ b)n ∀ 𝑛 ∈ 𝑄 + c)n ∀ 𝑛 ∈ 𝑍 + d) None
26 Dirichlet multiplication is commutative and associative i.e, for any arithmetical function A
f,g,h be obtain f*g= g*f is
a)Commutative b)associative c)both a&b d) None
27 Dirichlet multiplication is commutative and associative i.e, for any arithmetical function B
f,g,h be obtain f*(g*k)= (f*g)*k is
a)Commutative b)associative c)both a&b d) None
28 For any arithimaticfunction f we have I*f =f*I=------ C
a)g b)h c)f d)None
29 If f is an arithemetic function with f(1) ≠ 0 𝑡ℎ𝑒𝑟𝑒 𝑖𝑠 a unique arithmetic function f-1 is B
called
a)arithmetic function b) Dirichlet inverse function c)exponential function d)None
30 The arithemetic function u defined by u(n)=1 ∀𝑛is called C
a)arithematic function b) dirichlet function c) unit function d)None
+
31 If u & 𝜇 are Dirichlet inverse to each other then 𝜇 = 𝑢 and B
a) 𝜇 = 𝑢 + b)𝑢 = 𝜇+ c) a) 𝑢 = 𝑢 + d)None
32 What is the mobius inversion formula ? A
𝑛 𝑛
a) 𝜙(𝑛) = ∑𝑑 𝜇(𝑑) 𝜇(𝑑)b) 𝜙(𝑑) = ∑𝑑 𝜇(𝑑) 𝜇(𝑑)
𝑛 𝑛
𝑛 𝑛
c) 𝜙(𝑛) = ∑𝑑 𝑢(𝑢) 𝜇(𝑑)a) 𝜙(𝑛𝑑) = ∑𝑑 𝜇(𝑑𝑛) 𝜇(𝑑)
𝑛 𝑛
33 An arthematic function f is said to be multiplicative if f is not identically zero and if B
(m,n)=1 then
a)f(m*n)=f(m)+f(n) b)f(mn)=f(m).f(n) c)f(mn)=f(m)+f(n) d)f(mn)=f(m)-f(n)
34 An arthematic function f is said to be completely multiplicative if f is not identically zero B
and wholds for all m,n ∀ 𝑚, 𝑛then
a)f(m*n)=f(m)+f(n) b)f(mn)=f(m).f(n) c)f(mn)=f(m)+f(n) d)f(mn)=f(m)-f(n)
35 The Euler function 𝜙(𝑛) is multiplicative Euler’s function is not A
a)completely multiplicative b) multiplicative c)addition d)None
36 The mobius function is multiplicative but B
a)Completely multiplicative b) not Completely multiplicative
c) multiplicative d) None
37 The Identity function I(n) =[1/n] is A
a) Completely multiplicative b) not Completely multiplicative
 c) multiplicative d) None
𝛼
38 Let 𝑓𝛼 (n) = 𝑛 where α is a fixed real or complex number then this function is B
a)not Completely multiplicative b) Completely multiplicative
c) multiplicative d) None
39 If f & g are completely multiplicative then fg & f/g is also A
a)Completely multiplicative b) not Completely multiplicative
c) multiplicative d) None
40 If f is a multiplicative then f(1)=---- C
a)3 b)4 c)1 d)2
41 Given f with f(1) =1 then f is a multiplicative then f is A
a) Completely multiplicative b) not Completely multiplicative
c) multiplicative d) None
42 If f & g are a multiplicative function and this Dirchlet product f*g is also C
a)Completely multiplicative b) not Completely multiplicative
c) multiplicative d) None
43 The dirchlet product of two completely multiplicative function need not be A
a)Completely multiplicative b) not Completely multiplicative
c) multiplicative d) None
44 If both g and f*g are multiplicative then f is also C
a)Completely multiplicative b) not Completely multiplicative
c) multiplicative d) None
45 If f be multiplicative then f is completely multiplicative if and only if A
a)f-1(n) =𝜇(𝑛). 𝑓(𝑛), 𝑛 ≥ 1 b)f-1(n) =𝜇(𝑚). 𝑓(𝑛), 𝑚 ≥ 1
c)f-1(m) =𝜇(𝑛). 𝑓(𝑚), 𝑛 ≥ 1 d)f-1(n) =𝜇(𝑚). 𝑓(𝑛), 𝑚 ≥ 1
46 If g is multiplicative then g-1 is B
a)Multiplicative b) dirchlet inverse c)inverse multiplicative d) None

47 If f is multiplicative then we have ∑𝑑/𝑛 𝜇(𝑑). 𝑓(𝑑) = A

a)∏𝑝/𝑛(1 − 𝑓(𝑝)) a)∏𝑝/𝑚(1 − 𝑓(𝑝)) a)∏𝑚/𝑛(1 − 𝑓(𝑚)) d) None
48 If 𝜇 & 𝑓 𝑎𝑟𝑒 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑣𝑒 𝑡ℎ𝑒𝑖𝑟 𝑜𝑟𝑑𝑖𝑛𝑎𝑟𝑦 𝑝𝑟𝑜𝑑𝑢𝑐𝑡 𝑖𝑠 also C
a)Completely multiplicative b) not Completely multiplicative
c) multiplicative d) None
49 Find the value of ∧ (5) ? C
a)Log6 b)log4 c) log5 d) log7
50 What is the formula for inverse of Euler’s function? A
a)𝜙(𝑛) = (𝜇 ∗ 𝑁)(𝑛)b)𝜙(𝑛) = (𝜇 ∗ 𝑁)(𝑚)
c)𝜙(𝑛) = (𝜇 ∗ 𝑚)(𝑏) d)𝜙(𝑚) = (𝜇 ∗ 𝑁)(𝑣)
51 Find the value of ∧ (8)? A
a)log2 b) log3 c)log4 d)None
52 If n≥ 1 𝑡ℎ𝑒𝑛 𝑙𝑜𝑔𝑛 = − − − − C
a)∑𝑚/𝑛 Λ(𝑑) b)∑𝑑/𝑛 Λ(𝑚) c)∑𝑑/𝑛 Λ(𝑑) d)None
𝑛
53 If n≥ 1 𝑡ℎ𝑒𝑛Λ(n) = ∑𝑑 μ(𝑑) , 𝑙𝑜𝑔 𝑑 = A
𝑛
a)-∑𝑑/𝑛 μ(𝑑)log (𝑑)b)-∑𝑚/𝑛 μ(𝑚)log (𝑑)
c)-∑𝑑/𝑛 μ(𝑚)log (𝑚)d)-∑𝑛/𝑚 μ(𝑛)log (𝑛)
𝛼 𝛼 𝛼
54 The liouvilles function is denoted by 𝜆 we defined 𝜆(1) = 1 𝑖𝑓 n= 𝑝1 1 . 𝑝2 2 ……….𝑝𝑘 𝑘 we B
define 𝜆(𝑛) =…..
a)(1)𝛼1+𝛼2+⋯……..𝛼𝑘 b)(−1)𝛼1+𝛼2+⋯……..𝛼𝑘
c)(−𝑛)𝛼1 +𝛼2+⋯……..𝛼𝑘 ds)(−𝑚)𝛼1+𝛼2+⋯……..𝛼𝑘
55 The sum of the 𝛼 𝑡ℎ power of the divisors of n.the function 𝜎𝛼 is called --- A
a) divisor function b) complete function c)arithematic function d)None
56 The product of positive divisor of n is n i.e.. C
𝑑(𝑛) 𝑑(𝑚) 𝑑(𝑛)
a)∏𝑑/𝑑 𝑑 =𝑛 2 b)∏𝑚/𝑛 𝑑 =𝑛 2 c)∏𝑑/𝑛 𝑑 =𝑛 2 d) None
57 𝜎(𝑛) B
For any n, prove that = ------ for n≥ 1
𝑛
1 1 1
a)∑𝑚/𝑛 𝑑b)∑𝑑/𝑛 𝑑 c)∑𝑑/𝑛 𝑛d) None
58 𝜎𝛼 is an arithematical function which is A
a) multiplicativeb) inversec) additive d) None
59 For n=3600 find d(n)? C
a)26 b)25 c)24 d)56
0
60 For n=360 find 𝜎(𝑛)? A
a)1170 b)1234 c)1126 d)1143
61 If d(n) is odd iff n is A
a) squareb) odds c)prime d)none
62 What is the quadratic congruences of the form B
𝑛
a)(p/q)2 ≡ 𝑛(𝑚𝑜𝑑 𝑝) b)x2 ≡ 𝑛(𝑚𝑜𝑑 𝑝) c)x2 ≡ (𝑚)(𝑚𝑜𝑑 𝑝) d)None
63 How many number of solutions are there in Quadratic congruence ? A
a)0 or 2 b)1 or 4 c) 2 or 5 d)None
64 How can write the n is the quadratic residue mod p B
a)nrp b)nRp c)mnRp d)None
65 How can write the n is the quadratic non-residue mod p C
a)nrp b)nRp c)n𝑅̅p d)None
66 Find the quadratic residues modulo 11 B
a)1,2,3,4,5 b)1,3,4,5,9 c)6,7,8,9,0 d)None
67 Find the quadratic residues modulo 13 C
a)1,2,3,4,5 b)1,3,4,5,9 c)2,5,6,7,8,11 d)None
68 If p=3 and R=1then what value of 𝑅̅ ? C
a)4 b)3 c)2 d)None
69 If p=7 and R=1,2,4 then what value of 𝑅̅ ? A
a)3,5,6 b)4,3,6 c)8,7,9 d)None
70 ̅
If p=5 and 𝑅 =1,4 then what value of R? C
a)3,5, b)4,3, c)2,3 d)None
2
71 If p is an odd prime, then x ≡ 1(𝑚𝑜𝑑𝑝) has a solutions are B
a)1& p-2 b)1 & p-1 c) 5&p d)None
72 If 1 is a quadratic residue mod p and hence (1/p)=? C
a)3 b)2 c)1 d)5
73 If m is an integer then x ≡ m2 (mod p) has solutions are
2
A
a)m & -m b)1&2 c)m&n d)None
74 If m2 is a quadratic residue mod p then B
a)(m/p) b)(m2/p)=1 c)(p/m2) d)None
75 What is the little- Format theorem ? A
a)np-1≡ 1(𝑚𝑜𝑑𝑝) b) np-1≡ 𝑚(𝑚𝑜𝑑𝑝) c) nm-1≡ 𝑚(𝑚𝑜𝑑𝑝) d)None
76 If p is an odd prime and n≢0(modp)then A
𝑝−1 𝑝−1
( ) ( )
a)𝑛 2 ≡ ±1(𝑚𝑜𝑑𝑝) b)𝑝 2 ≡ ±1(𝑚𝑜𝑑𝑝)
𝑝−1 𝑝−1
( 2 ) ( 2 ) 𝑝
c)𝑛 ≡ ±1(𝑚𝑜𝑑𝑝) d)𝑛 ≡ ±1(𝑚𝑜𝑑 (𝑛))
𝑝−1
77 Let p be an odd prime then for all n we have (n/p)≡ 𝑛( 2
)
(mod p) is B
a)Euler format theorem b)Eiler’s criterian c)little –format theorem d)None

78 Legendre’s symbol (n/p) is a completely multiplicative function of n if p is an odd prime then C

𝑚 𝑚 𝑛 𝑚𝑛 𝑚 𝑛
a)( 𝑝 ) = ( 𝑝 ) (𝑝 ) ∀m,n b)( 𝑝 ) = ( 𝑛 ) (𝑝 ) ∀m,n
𝑚𝑛 𝑚 𝑛 𝑚𝑛 𝑚 𝑛
c)( 𝑝 ) = ( 𝑝 ) (𝑝 ) ∀m,n d)( 𝑝 ) = ( 𝑝 ) (𝑚) ∀m,n
79 What is the formula for gauss lemma ? B
a)(n)=(-1)m b)(n/p)=(-1)m c)(m/p)=(-1)m d)None
80 Evaluate (127/17) by using Legendre symbol? C
a)2 b)3 c)1 d)5
81 Euler’s criterian &Gauss lemma give straight forward method for computing A
a)(n/p) b)(p/n) c)(r/m) d)None
𝑝−1 𝑞−1
82 ( )( ) A
If p and q are distinct odd primes then (p/q).(q/p)=(−1) 2 2 is

a)quadratic reciprocity law b)reduced residue system c)legendre symbol d)None

83 Evaluate (219/383) by using quadratic reciprocity law C
a)2 b)3 c)1 d)6
84 Determine those odd prime p for which 3 is a quadratic residue and those for which it is a B
a)residue b)non-residue c)reduced residue system d)None
85 (a,m) =1 if B
a)a and m are integers b)a and m are coprime c)a and m are prime d)None
86 There exist at least ----- primitive roots modulo each prime p≥ 3 B
a)2 b) 1 c)5 d)3
87 Find the exponents of 3 modulo 5 is A
a)4 b)5 c)6 d)8
𝑛−2
88 Let a be any odd integer then 𝑎2 ≡ 1(𝑚𝑜𝑑 2𝑛 ) for all C
a)n>3 b)n<3 c)n≥ 3 d)None
89 What are the coprime numbers to 7? A
a)2,3,4,5,6 b)2,7,6,5,9 c)0,1,2,6,7 d)None
90 Let a have exponent h modulo m.then ak has exponent h modulo m iff C
a)(h,k)=2 b)(k,m)=1 c)(h,k)=1 d)None
91 Exponent of 3(mod 8) is C
a)3 b)4 c)2 d)None
92 What is the primitive roots of modulo 6 A
a)5 b)6 c)8 d)None
93 If a is a primitive root modulo m; then 1,a……𝑎𝜙(𝑚)−1 is A
a)reduced residue system b) increased system c)decreased system d)None
94 If a is a primitive root(mod m) then akis a primitive root(mod m)if and only if k and B
𝜙(𝑚)𝑎𝑟𝑒
a)prime b)coprime c) integers d)None
95 Find the primitive roots modulo5 B
a)2,5 b)2,3 c)8,9 d)None
96 If exponent of a modulo P,p a prime is 3 then show that the exponent of a+1(mod p) is C
a)4 b)7 c)6 d)None
97 Suppose the exponent of an integer a modulo m is m-1.prove that m is a A
a)prime b)coprime c)integer d)None
98 How many primitive roots modulo 15 exist D
a)1 b)2 c)6 d)None
99 Find all the primitive roots modulo 13 and express each as a power of some one of these A
roots
a)2,6,7,11 b)8,7,9,0 c)3,9,1,0 d)None
100 If p is a prime and gcd(a,p)=1=gcd(n,p-1),then xn ≡a (mod p) has ------solutions A
a)1 b)2 c)4 d)None
101 Let p be an odd prime. Find all solutions of xp-1≡2(mod p) D
a)2 b)5 c)3 d)None
102 How many primitive roots belonging to 2n ∀ 𝑛 ≥ 3 D
a)1 b)3 c)2 d)None
103 Let m,n each>2 be any integers and (m,n)=1.then there exist -----primitive roots (modmn) D
a)1 b)3 c)5 d)None
104 Find the remainder when 4175is divided by 3. A
 a)2 b)4 c)5 d)6
105 Find the remainder when 21000000is divided by 7. C
a)2 b)4 c)27 d)6
106 What is the wilson’s thermo A
a)(p-1)!≡ −1(𝑚𝑜𝑑 𝑝) b)(p-2)!≡ −1(𝑚𝑜𝑑 𝑝) c )(p)!≡ −1(𝑚𝑜𝑑 𝑝) d)None
107 If p is a prime such that p∤ n and integer k≥ 1. 𝑡ℎ𝑒𝑛 𝜙(𝑛𝑝𝑘 )=----- C
a) 𝜙(𝑛𝑝𝑘 ) 𝜙(𝑚𝑝𝑘 ) b) 𝜙(𝑝𝑘 ) 𝜙(𝑚𝑝𝑘 ) c) 𝜙(𝑛) 𝜙(𝑝𝑘 ) d)None
108 Let n be any integer >2.then a) 𝜙(𝑛) is B
a)odd b)even c)prime d)None
109 Evaluate a) 𝜙(450) ? C
a)23 b)56 c)120 d)None
110 Let a be a primitive root modulo an odd prime P then A
𝑝−1 𝑝−2 𝑝
a)𝑎 2 ≡-1 (mod p) a)𝑎 2 ≡-1 (mod p) a)𝑎 ≡-1 (mod p) d)None
2

111 Let p=5.we shall find a primitive root mod 52? A

a)3,2 b)4,5 c)6,7 d)None
112 3 is a primitive root mod 5.what are the indices of (mod5) relative to 3. B
a)1,3,5,6 b)1,2,3,4 c)5,4,5,7 d)None
3
113 Solve the congruences 7x ≡ 3(mod11) A
a)x=7+11t,t=±1, ±2 b)x=8+11t,t=±1, ±2 c)x=7+9t,t=±1, ±2 d)None
k
114 Let r be a primitive root (mod p) then r is a quadratic residue mod p iff k is A
a)even b)odd c)integer d)None
115 Find the missing digit of the number 9,555,5-4,353 so that it is divisible by 11 C
a)3 b)5 c)1 d)None

116 Let m be a positive integer,a and b any integers. The linear congruence B
𝑚
a)px≡ 𝑚(𝑚𝑜𝑑 𝑚) b)ax≡ 𝑏(𝑚𝑜𝑑 𝑚) c)ax≡ ( )(𝑚𝑜𝑑 𝑚) d)None
𝑛
(k)
117 For each integer m,f (m) is divisible by ---- C
a)q! b)m! c)k! d)None
118 Solve the linear congruences 25x≡ 10 (mod 29) D
a)13 b)15 c)11 d)12
119 Find aii integer solutions of x2 + 1 ≡ o(mod 53) A
a)82,43 b)99,78 c)67,54 d)None
120 Solve the quadratic congruences x2≡ 145(mod 256) B
a)56,213(mod 27) b)41,215(mod 28) a)16,214(mod 27) d)None
121 For what value of a the quadratic congruence x2≡ a(mod 24) B
a) a≡ 2(𝑚𝑜𝑑 8) b) a≡ 1(𝑚𝑜𝑑 8) c) a≡ 4(𝑚𝑜𝑑 8) d)None
122 Solve the congruence x2+5𝑥 + 3 ≡ 0(mod 11) C
a)one solution b)two solution c)no solution d)None
123 Solve the congruence x2≡ -10(mod 127) A
a)25 b)54 c)56 d)None
124 There are infinitely many primes of the form 4k+1,k is A
a)integer b)prime c)coprime d)None
125 LR6(15)=----- C
a)4 b)9 c)3 d)None

Signature of Faculty Signature of HOD

Practice Questions:

MODULE-I
Divisibility
Long questions:
1) Explain state and prove Euclidean Algorithm?
2) By using the Euclidean Algorithm find the G.C.D of 1769 & 2378 and also find x and y such that
(1769, 2378)=1769x+2378y .
3) Explain state and prove Division Algorithm?
4) Explain state and prove Fundamental theorem of Arithmetic ?
5) Find the general solution of the equation (i) 70x+112y =168 (ii) 39x – 56y=11.

6) The Linear Diophantine equation ax+by=c has a solution if and only if d/c ,where
d=gcd(a,b).

7) a)Determine whether the integer 133 is a prime or not?

b) Use prime factorization to find GCD and LCM of 18 and 30?

8) If x0,y0 is any particular solution of this equation ,then all other solutions are given by
x=x0+(b/d)t, y=y0-(a/d)t, where t is an arbitrary integer.

9) a)If gcd(a,b)=d then gcd(a/d,b/d)=1.

b)Determime all prime numbers that divide 50!

10) a) Solve the Linear Diophantine equation 858x+253y=33 .

b)gcd(a,b) can be expressed as integral linear combination of a and b i.e gcd(a,b) = ax+by
where x and y are integer.

Short Questions

1) state the Division algorithm?

2) state the Euclidean algorithm?

3) Find the GCD of 24 and 36.

4) State the Fundamental theorem of Arithmetic?

5) Write the at least three properties of Divisibility?

6) Write the defination of the common divisior ?

7) Write the defination of the greatest common divisior?

8) Write the definition of the relatively prime?

9) What is the Diophantine equation?

10) What is the least common multiple?

MODULE –II
 Congruences
1) Write the definition and properties of congruence?
2) prove that if C > 0 then a  b(mod m) iff ac bc(modmc).
3) prove that if ac bc (mod mc) and if d= (m,c) then a  b(mod( m/d)) .
4) Prove that a  b(mod m) ⟺ a & b give the same remainder when divided by m.
5) Prove that if a  b(mod m) and 0≤ |𝑏 − 𝑎|<m then a=b.

6) find the remainder when the sum 1!+2!+3!+4!+.............+100! Is divided by 12.

7) find the remainder when (4444)4444 is divided by 9?
8) Explain state and prove Euler –Fermat theorem ?
9) Find the solution of the given linear congruences.14x 12(mod 18).
10) Prove that if p is a prime then all the coefficient of the polynomial f(x) = (x-1) (x-2) ....(x- (p-1)) –xp-1
+ 1 are divisible by p.
11) If a  b(mod m1) and a  b(mod m2) & (m1,m2) = d then a  b(mod d)

b)state and prove Little –Fermat theorem?

12) state and prove Chinese Remainder theorem?

13) Solve the system of linear congruences x 1(mod 3), x 2(mod 4), and x 3 (mod 5) by using
Chinese Remainder theorem.
Short questions
1) Write the definition of congruence?
2) Write the properties of congruence?
3) Write the statement of the Euler –Fermat theorem ?
4) State the Chinese Remainder theorem?
5) State the Little –Fermat theorem?
6) Find 8-1 (mod 35).
7) Write the definition of the Fermat number?
8) Write the cancellation law1.
9) If ab(modm) and 0≤ |𝑏 − 𝑎| < 𝑚 𝑡ℎ𝑒𝑛 𝑎 = 𝑏.
10) If ab(modm) 𝑡ℎ𝑒𝑛 𝑎 + 𝑐 = 𝑏 + 𝑐(𝑚𝑜𝑑 𝑚).
 MODULE-III

Arithmetic Functions

1 1 𝑖𝑓 𝑛 = 1
1) Prove that if n≥ 1 we have ∑𝑑/𝑛 𝜇(𝑑) =[𝑛] = {
0 𝑖𝑓 𝑛 > 1
𝑛
2) Prove that if n≥ 1 𝑤𝑒 ℎ𝑎𝑣𝑒 𝜙(𝑛) = ∑𝑑/𝑛 𝜇(𝑑). (𝑑)
1
3) Prove that if n≥ 1 𝑤𝑒 ℎ𝑎𝑣𝑒 𝜙(𝑛) = 𝑛 ∏𝑝/𝑛 [1 − 𝑝]

4) Prove that Eulers totient function has the following properties.

𝑎) 𝜙(𝑝𝛼 ) = 𝑝𝛼 – 𝑝𝛼−1 for prime p,𝛼 ≥ 1.
𝑑
𝑏) 𝜙(𝑚, 𝑛) = 𝜙(𝑚) 𝜙(𝑛) (𝜙(𝑑)) 𝑤ℎ𝑒𝑟𝑒 𝑑 = (𝑚, 𝑛)

𝑐) 𝜙(𝑚, 𝑛) = 𝜙(𝑚) 𝜙(𝑛) 𝑖𝑓 (𝑚, 𝑛) = 1.

5). Find the all the integer n such that 𝜙(𝑛) = 𝜙(2𝑛)
6). Find 𝜏(630) and 𝜎(180) ?
7). a)Verify that 𝜏(𝑛) = 𝜏(𝑛 + 1) = 𝜏(𝑛 + 2)= 𝜏(𝑛 + 3) 𝑓𝑜𝑟 𝑛 = 3655 ?
b) when n= 14206 show that 𝜎(𝑛)= 𝜎(𝑛 + 1)
8).a) Calculate 𝜙(5040).
b) Verify that 𝜙(𝑛) = 𝜙(𝑛 + 1) = 𝜙(𝑛 + 2)= 𝜙(𝑛 + 3) 𝑓𝑜𝑟 𝑛 = 5186? ?
9).(a) Show that the integers m = 3k .568 and n = 3k . 638 where k ≥ 0 satisfy simultaneously
 (m) =  (n),  (m) =  (n) and  (m) =  (n)
(b)Find the highest power of 5 dividing 1000! and the highest power of 7 dividing 2000!
10). If n is a positive integer and p is a prime then the exponent of the highest power of p that

 n 
divides n! is  p
k =1 
k 
.

Short questions
1) Write the definition of arithmetic function?
2) Define the Mobius function?
3) Write the definition of Euler totient function?
4) What is the number of divisors for 10?
5) Write the product formula for 𝜙(𝑛).
6) Find the value 𝜙(210)?
7) Find that 𝜏(630)?
8) What is the division sum?
9) Write the greatest integer function?
10) Write the 𝜎(180)
MODULE-IV

Primitive Roots

1) List the primitive roots modulo 17?

𝑛−2
2) Prove that let a be any odd integer. Then 𝑎 2 ≡ 1 (mod 2𝑛 ), ∀ 𝑛 ≥ 3.
3) If a is a primitive, root modulo m; then 1,a,a2,........𝑎 𝜙(𝑚)−1 is a reduced residue system modulo.
4) Prove that there exist at least one primitive root modulo each prime p≥ 3
5) Let p=5. We shall find a primitive root mod 52 ?
6) Solve the congruence 2x7 ≡ 5 (mod 11) given 2 is the primitive root modulo11,write out a table
of indices.
7) Prove that let the integer a have order K modulo n then 𝑎 𝑘 ≡ 1 (mod n) iff k/h.
𝑘
8) If the integer a has order k modulo n and h>0.then ah has order gcd (ℎ,𝑘) 𝑚𝑜𝑑𝑢𝑙𝑜 𝑛.

9) (a) let a be a primitive root of integer m then ak is a primitive root of m . if and only if
gcd(k,𝜙(𝑚)) = 1.
(b)Prove that let a be an integer having exponent h modulo m i.e. ah ≡ 1 (modm). Then
the following hold:
(i)If ak ≡ 1 (𝑚𝑜𝑑 𝑚), for some integer k,then h/k.
(ii) ai ≡ 𝑎 𝑗 (𝑚𝑜𝑑 𝑚) ⇔ i≡ j(mod h).
10) solve the linear congruences by using Indices 11x3 ≡ 2 (mod 23)
Short questions:
1) Write the definition of primitive root?
2) Find the primitive root of 5?
3) Write the law of Exponents?
4) define the Indices?
5) Find the primitive root of 3?
6) Find the number of primitive roots of 12?
7) If 12 is the exponent of 2 modulo 13 then find exponent of 23?
8) If 2 is the primitive root of 5, then write the table of indices for 5?
9) Find the order of 3 modulo 7?
10) Write the table of indices of 3?

MODULE –V

Quadratic Congruences and Quadratic Reciprocity Law

1). Find the quadratic residues modulo 11& 13.

2). Explain the state and prove the Euler’s criterion?
3). Prove that Legendre’s symbol (n/p) is a completely multiplicative function of n .i.e
𝑚.𝑛 𝑚 𝑛
if p is an odd prime ⇒ ( ) = ( 𝑝 ) (𝑝 ) ∀ 𝑚, 𝑛
𝑝

4). Prove that for every odd prime we have

𝑝2−1 1 𝑖𝑓 𝑝 = ±1(𝑚𝑜𝑑8)
(2/p) = (−1) 8 ={
− 1 𝑖𝑓 𝑝 = ±3 (𝑚𝑜𝑑8)

5). Evaluate (219/383) by using quadratic reciprocity law?

6). Explain the state and prove the Quadratic reciprocity law?
7). Determine those odd primes p for which 3 is a quadratic residue and those for which it is a
non -residue.
8). Evaluate (127/17) by using Gauss lemma?
 9). Prove that for every odd prime p we have

𝑝−1 1 𝑖𝑓 𝑝 = 1(𝑚𝑜𝑑 4)
(-1/p) = (−1) 2 ={
− 1 𝑖𝑓 𝑝 = −1 (𝑚𝑜𝑑 4)

10) state and prove Gauss Lemma?

Short questions

1) Write the Quadratic Congruences form?

2) Defined quadratic residues?

3) Defined Legendre’s symbol?

4) Write the statement of Euler’s criterian?

5) Find the quadratic residues of 5?

6) Write done quadratic reciprocity law?

7) State Gauss Lemma?
8) Defined Jacobi symbol.
9) Write the properties of Jacobi symbol.
10) Write the properties of Legendre’s symbol?
Code: C0B23 MR 22

MALLA REDDY ENGINEERING COLLEGE (AUTONOMOUS)

(Affiliated to JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD)
Gundlapochampally (H), Maisammaguda (V), Medchal (M), Medchal-Malkajgiri (Dist), Hyderabad
II B.Tech IV- Semester (MR 22-2022-23 Admitted Students)A.Y. 2023-24
MODEL QUESTION PAPER
Subject: Number theory
Branch:CSE(CS)
Time: 3 hours Max. Marks: 60
M
PART-A
Answer all the Questions 10x1M = 10
M

Q. BT Level
No. Questions Marks CO
1
state the Division algorithm? 1 L1 1
a
Find the GCD of 24 and 36. 1 L1 1
b

c Write the definition of congruence? 1 L1 2

d State the Chinese Remainder theorem? 1 L1 2

e Define the Mobius function? 1 L1 3

f Find that 𝜏(630). 1 L1 3

g Find the primitive root of 3? 1 L2 4

h define the Indices? 1 L2 4

Defined quadratic residues? 1 L1 5

i
State Gauss Lemma? 1 L1 5
j

PART-B
Answer all the Questions 5 x 10 M = 50
M
Q. BT
Question Marks CO
No. Level
2. (a) Solve the Linear Diophantine equation 858x+253y=33 . 5 L2 1
(b) gcd(a,b) can be expressed as integral linear combination of a and b i.e
gcd(a,b) = ax+by where x and y are integer. 5 L3 1

OR
(a)Explain state and prove Division Algorithm?
5 L3 1
3. (b) By using the Euclidean Algorithm find the G.C.D of 1769 & 2378 and also
find x and y such that (1769, 2378)=1769x+2378y . 5 L3 1

state and prove Chinese Remainder theorem?

4. 10 L3 2

OR
(a)Explain state and prove Euler –Fermat theorem ?
5 L4 2
5. (b) Find the solution of the given linear congruences.14x 12(mod 18).
5 L2 2

(a) Show that the integers m = 3k .568 and n = 3k . 638 where k ≥ 0 satisfy
simultaneously  (m) =  (n),  (m) =  (n) and  (m) =  (n) 5 L2 3
6. (b) Find the highest power of 5 dividing 1000! and the highest power of 7
5 L3 3
dividing 2000!

OR
Prove that Eulers totient function has the following properties.
𝑎) 𝜙(𝑝𝛼 ) = 𝑝𝛼 – 𝑝𝛼−1 for prime p,𝛼 ≥ 1.
𝑑
7. 𝑏) 𝜙(𝑚, 𝑛) = 𝜙(𝑚) 𝜙(𝑛) (𝜙(𝑑)) 𝑤ℎ𝑒𝑟𝑒 𝑑 = (𝑚, 𝑛) 10 L2 3

𝑐) 𝜙(𝑚, 𝑛) = 𝜙(𝑚) 𝜙(𝑛) 𝑖𝑓 (𝑚, 𝑛) = 1.

a) solve the linear congruences by using Indices 11x3 ≡ 2 (mod 23)

5 L2 4
8.
b) let a be a primitive root of integer m then ak is a primitive root of m . if and
5 L4 4
only if gcd(k,𝜙(𝑚)) = 1.
 OR
a) Prove that let the integer a have order K modulo n then 𝑎 𝑘 ≡ 1 (mod n)
5 L2 4
iff k/h.
9.
b) List the primitive roots modulo 17?
5 L2 4

(a). Explain the state and prove the Euler’s criterion? 5 L2 5

10.
(b) Evaluate (219/383) by using quadratic reciprocity law? 5 L3 5

OR
Evaluate (127/17) by using Gauss lemma?
11. 10 L2 5

Signature of the Faculty Signature of the

HoD