UNIVERSITY OF CALICUT

SCHOOL OF DISTANCE EDUCATION

Basic Logic and Number Theory

Core Course
For
BSc Mathematics
(CBCSS - 2019 Admission)
SEMESTER I
QUESTIONBANK

1. The truth value of given statement is 4 + 3 = 7 or 5 is not prime’.

a) False b) True

2. What is the value of x after this statement, assuming initial value of x is

5? ‘If x equals to one then x = x + 2 else x = 0’.
a) 1 b) 3 c) 0 d) 2

3. Let P : Mathematics is interesting, Q: You should not learn it. Then

‘Mathematics is interesting and you should learn it.’ is best represented by:
a) ¬P ∨ ¬Q b) P ∧ ¬Q
c) P ∨ Q d) P ∧ Q

4. The compound statement A → (A → B) is false, then the truth values of

A, B are respectively
a) T, T b) F, T c) T, F d) F, F

5. Let P , Q, R be true, false, false, respectively, which of the following is

true a) P ∧
(Q ∧ ¬R) b) (P → Q) ∧ ¬R
c) Q ↔ (P ∧ R) d) P ↔ (Q ∨ R)

1
6. (A ∨ ¬A) ∨ (q ∨ T ) is a
a) Tautology b) Contradiction
c) Contingency d) None of the mentioned

7. (A ∨ F ) ∨ (A ∨ T ) is always
a) True b) False

8. The compound propositions p and q are called logically equivalent if - - -

is a tau- tology.
a) p ↔ q b) p → q
c) ¬(p ∨ q) d) ¬p ∨ ¬q

9. The contrapositive of p → q is the proposition:

a) ¬p → ¬q b) ¬q → ¬p
c) q → p d) ¬q → p

10. Let P (x) denote the statement ”x > 7”. Which of these have truth value
true?
a) P (0) b) P (4) c) P (6) d) P (9)

11. “The product of two negative real numbers is not negative.” Is given by?
a) ∃x ∀y((x < 0) ∧ (y < 0) → (xy > 0))
b) ∃x ∃y((x < 0) ∧ (y < 0) ∧ (xy > 0))
c) ∀x ∃y((x < 0) ∧ (y < 0) ∧ (xy > 0))
d) ∀x ∀y((x < 0) ∧ (y < 0) → (xy > 0)

12. p ∨ q is logically equivalent to:

a) ¬q → ¬p b) q → p c) ¬p → ¬q d) ¬p → q

13. p ∧ q is logically equivalent to:

a) ¬(p → ¬q) b) (p → ¬q)
c) (¬p → ¬q) d) (¬p → q)

14. When to proof P → Q true, we proof P false, that type of proof is known
as
a) Direct proof b) Contrapositive proofs
c) Vacuous proof d) Mathematical Induction

2
15. Which of the following can only be used in disproving the statements?
a) Direct proof b) Contrapositive proofs
c) Counter Example d) Mathematical Induction

16. In the principle of mathematical induction, which of the following steps

is manda- tory?
a) induction hypothesis b) inductive reference
c) induction set assumption d) minimal set representation

17. By induction hypothesis, the series 12 + 22 + 32 + ..... + p2 can be proved

equivalent to
a) p2 + 27
b) p∗ (p+1)∗
6
(2p+1)

c) p∗ (p+1)
4
d) p + p2

18. For any positive integer m, - - - is divisible by 4.

a) 5m2 + 2 b) 3m + 1
2
c)m + 3 d) m3 + 3m

19. Let P (n) be the statement that a postage of n cents can be formed using
just 3-cents stamps and 5-cents stamps. Is the statements P (8) and P (10) are
correct?
a) True b) False

20. Suppose that P (n) is a propositional function. Determine for which

positive inte- gers n the statement P (n) must be true if: P (1) is true; for all
positive integers n, if P (n) is true then P (n + 2) is true.
a) P (3) b) P (2) c) P (4) d) P (6)

21. Which of the following is the division algorithm?

a) For any integer a, and any positive integer b, there exists unique
integers q and r, such that a = bq + r, where r is greater than or equal
to
0 and less than b.
b) For any integer a, there exists an integer b, such that a = 4b.
c) For any n > 2, there does not exist positive integers x, y, and z such
that
xn + y n = z n .
d) All even numbers are prime numbers, so they are not divisible by 2.

3
22. If a is divisible by b, which of the following are true?
a) b divides into a evenly
b) In the division algorithm, when we divide a by b, the remainder is 0.
c) a = bq, for some integer q.
d) All of these statements are true

23. Let gcd(a, b) = d. If c divides a and c divides b, then

a) c ≤ d b) c ≥ d
c) c = 1 d) cannot determine c with the given information.

24. The value of 155mod9 is

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

25. If a|b and a|c, then

a) b|c b) c|a
c) a|(b + c) d) b|a

26. If a and b are relatively prime then

a) a|b b) b|a
c) gcd(a, b) = 1 d) lcm(a, b) = 1

27. If a and b are non zero integers with a|b, then gcd(a, b) equals
a) |a| b) b
c) ab d) a

28. The product of any three consecutive integers is divisible by

a) 36 b) 9 c) 6 d) 8

29. Let gcd(a, b) = d, then

a) d = ax + by, f or some x and y b) a|d
c) b|d d) d=a+b

30. Let gcd(a, b) = d, then gcd( a , b ) isd d

a) 1 b) a c) b d) d

31. If a is an odd integer then gcd(3a, 3a + 2) equals

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

32. The quotient and remainder when ­ 1 is divided by 3 is

a) -1 and -1 b) -1 and 2 c) 1 and 2 d) -1 and -2
4
33. The number ‘1’ is
a) Prime number b) Composite number
c) Neither Prime nor Composite d) None of the mentioned

34. The number of primes is

a) finite b) infinite c) uncountable

35. Difference of two distinct prime numbers is ?

a) Odd and prime
b) Even and composite
c) None of the mentioned

36. If a, b are two distinct prime number than highest common factor of a, b is
a) 2 b) 0 c) 1 d) ab

37. If a, b are integers such that a > b then lcm(a, b) lies in

a) a > lcm(a, b) > b b) a > b > lcm(a, b)
c) lcm(a, b) ≥ a > b d) None of the mentioned

38. If number a is 22 ∗ 31 ∗ 50 and b is 21 ∗ 31 ∗ 51 then lcm(a, b) is

a) 22 ∗ 31 ∗ 51 b) 22 ∗ 32 ∗ 52
c) 23 ∗ 31 ∗ 50 d) 22 ∗ 32 ∗ 50

39. (1001111)2 =- - -
a) 79 b) 89 c) 69 d) 99

40. What is the one’s complement of the number 1010110

a) 1111111 b) 0101001
c) 1100110 d) None of the mentioned

41. The linear Diophantine equation ax + by = c has a solution if and only if

a) gcd(a, c)|b b) gcd(a, b)|c c) gcd(c, b)|a d) c|gcd(a, b)

42. Which of the following Diophantine equation cannot be solved ?

a) 6x + 51y = 22 b) 33x + 14y = 115
c) 14x + 35y = 93 d) 11x + 13y = 21

5
43. An integer n is called a pseudoprime if
a) n|2n ­ 2 b) n is composite and n|2n ­ 2
c) n is prime and n|2n ­ 2 d) n is composite and n|2n ­ 1

44. A composite number n for which an ≡ a(modn) is called

a) a pseudoprime b) a prime
c) a pseudoprime to the base a d) an absolute pseudoprime

45. The composite numbers n that are pseudoprime to every base a are called
a) pseudoprime b) prime
c) pseudoprime to the base a d) absolute pseudoprimes

46. If p, q1 , q2 , ....., qn are all primes and p|q1 q2 .....qn , then

a) p = qk for some k b) p = 2
c) qk = 2 for some k d) p|qk for some k

47. Any positive integer n > 1, the canonical form for n is

1 2
a) nn = pk1 pk2 .....p
i
kn
, where p0 s are primes.
b) n = p1 p2 .....pn , where
i p0 s are primes
c) n = 2p + 1 , where p is a prime
d) n = pk , where p is a prime

48. If Pn is the nth prime number, then

a) Pn = n + 1
b) Pn ≤ 22
n−1

c) Pn = n! + 1

49. For n ≥ 1, there are at least - - - primes less nthan 22

a) n b) n – 1 c) n + 1

50. If a is a solution of P (x) ≡ 0(modn) and a ≡ b(modn), then

a) ab is also a solution b) a + b is also a solution
c) a ­ b is also a solution d) b is also a solution

51. Give an example for a2 ≡ b2 (modn) need not imply a ≡ b(modn)

a) a = 2, b = 3, n = 5
b) a = 4, b = 9, n = 5
c) a = 8, b = 13, n = 5
d) a = 16, b = 11, n = 5
6
52. f a is an odd integer then a2 ­ 1 is
a) a multiple of 7 b) a multiple of 8
c) a multiple of 11 d) a multiple of 9

53. If a ≡ bmodn , then

a) n|a and n|b b) n|b only c) n|(a ­ b)

54. If a ≡ bmodn , then

a) a and b leave the same non negative remainder when divided by n.
b) a and b leave the different non negative remainder when divided by n.
c) a and b need not leave the same non negative remainder when divided
by n.

55. a ≡ bmodn and b ≡ cmodn , then

(a) a ≡ cmodn
(b) a = b
(c) a = c

56. If a is an odd integer, then a2 ≡ ­ ­ ­ (mod8)

a) 1 b) 2 c) 3 d) 4

57. If ca ≡ cb(modn) and gcd(c, n) = 1, then

(a) a ≡ bmod(n) (b) a ≡ bmodn (c) a ≡ bmod(c/n)

58. The solution of 25x ≡ 15(mod29) is

a) x ≡ 18(mod29) b) x ≡ 29(mod29)
c) x ≡ 18(mod19) d) x ≡ 17(mod19)

59. If a ≡ bmodn , then

a) a ­ b = n
b) a ­ b = kn, for some integer k
c) a + b = kn, for some integer k

60. If ca ≡ cb(modp) and p - c, where p is a prime number, then

a) a ≡ bmod(p/c) b) a 6≡ b(modp) c) a ≡ bmodp

61. If a ≡ bmodn , and m|n, then

a) a ≡ bmod b) a 6≡ bmodm c) a ≡ bmod(n/m)

7
62. If a ≡ bmodn , and c > 0, then
a) ca ≡ cbmodcn b) ca 6≡ cbmodcn c) a ≡ bmod(n/c)

63. If a ≡ bmodn and gcd(a, n) = d, then gcd(b, n) is

a) a b) d c) nd
Pn
64. Let P (x) = i=1
i
ci x be a polynomial function of x with integral coefficients ci .
If a ≡ bmodn , then
a) a ≡ P (b)modn b) P (a) ≡ P (b)modn c) P (a) ≡ bmodn

65. If a ≡ bmodn and a is a solution of P (x) ≡ 0modn , then

a) b is also a solution b) b need not be a solution c) 0 is a solution

66. A positive integer is divisible by 9 if and only if the sum of the digits
in its deci- mal representation is divisible by
a) 3 b) 81 c) 9

67. A positive integer is divisible by 11 if and only if the alternating sum of

its digits is divisible by
a) 121 b) 22 c) 11

68. The linear congruence ax ≡ bmodn has a solution if and only if

a) b = 1 b) b = 0 c) d|b, where d = gcd(a, n)

69. If gcd(a, n) = 1, then the congruence ax ≡ bmodn has

a) Infinitely many solutions modulo n
b) Unique solution modulo n
c) More than one solution modulo n

70. The value of 52003mod7 is

a) 3 a b) 4 c) 8 d) 9

71. The linear congruence 18x ≡ 6mod3 has

a) Infinitely many solutions modulo 3
b) Unique solution modulo 3
c) Exactly 3 solution modulo 3
8
72. The linear congruence 19x ≡ 6mod30 has
a) Infinitely many solutions modulo 30
b) Unique solution modulo 30
c) Exactly 6 solution modulo 30

73. The system of linear congruences ax + by ≡ r(modn) and cx + dy

≡ s(modn) has a unique solution modulo n whenever
(a) gcd(ad ­ bc, n) = 1
(b)gcd(ad, bc) = 1
(c) gcd(ad, bc) = n

74. Let p be a prime and suppose that p - a. Then

a) ap ≡ 1modp b) ap­ 1 ≡ 1modp c) ap­ 1 ≡ ­ 1modp

75. If p is a prime, then for any integer a

a) ap ≡ amodp b) ap­ 1 ≡ 1modp c) ap­ 1 ≡ ­ 1modp

76. If p is a prime, then

a) (p ­ 1)! ≡ 1modp
b) (p ­ 1)! ≡ ­ 1modp
c) (p ­ 1)! ≡ 0modp

77. σ(12) is
a) 28 b) 27 c) 16

78. τ (12) is
a) 28 b) 5 c) 6

79. τ (n) = 2 if and only if

a) n is a prime number
b) n is an odd number
c) n is an even number

80. σ(n) = n + 1 if and only if

a) n is an odd number
b) n is an even number
c) n is a prime number
81. If n is an odd pseudoprime, then 2n ­ 1 is
a) pseudoprime b) prime c) irrational d) not pseudoprime
9
 √
82. If p is any prime then p is
a) prime b) an integer c) irrational d) rational

83. The Sieve of Eratosthenes is used for finding

a) all primes below a given integer
b) all even numbers below a given integer
c) all odd numbers below a given integer
d) all composite numbers below a given integer

84.
1 2
If n =r pk1 pk2 .....pkr is the canonical form for n > 1, then
a) τ (n) = k1 + k2 + .... + kr

b) τ (n) = (k1 + 1)(k2 + 1)...(kr + 1)

c) τ (n) = (k1 ­ 1)(k2 1)....(kr ­ 1)

85.
1 2
If n =r pk1 pk2 .....pkr is the canonical form for n > 1, then
a) σ(n) = k1 + k2 + .... + kr
k1 +1 k2
+1 kr +1
­1 ­1 ­1
b) σ(n) = ( p1 p
p ­1
)( p2 )......( pr
pr ­ 1
)
1 2
­1

10
 c) σ(n) = (k1 + 1) + (k2 + 1) + ..... + (kr + 1)

86. A number-theoretic function f is said to be multiplicative if f (m, n) = f (m)f

(n)
a) Whenever lcm(m.n) = mn
b) For all integers m and n
c) For all positive integers m and n

87. If n and r are positive integers with 1 ≤ r < n, then the binomial
coefficient
(rn) = r!(n­
n!
r)! is
a) an integer
b) a prime c) irrational
d) an even integer

88. The functions τ and σ are both multiplicative functions. The statement is
a) False
b) True
c) Partially true

89. The Euler’s Phi- function is

a) Multiplicative
b) Not Multiplicative
c) Injective

90. Which of the following statement is true

a) The functions τ and σ are both multiplicative functions
b) The Euler’s Phi- function is injective
c) The Euler’s Phi- function is not Multiplicative

91. For n > 2, φ(n) is

a) Prime number
b) Even number
c) Odd number

92. If n > 1, is prime. Then φ(n) is

a) n ­ 1 b) n c) n + 1

11
93. φ(13) is
a) 13 b) 12 c) 14

94. If n ≥ 1 and gcd(a, n) = 1, then

a) aφ(n) ≡ ­ 1(modn)
b) aφ(n) ≡ 0(modn)
(c)aφ(n) ≡ 1(modn)

95. For n > 1, the sum of the positive integers less than n and relatively prime
to n is
a) φ(n) b) 1 φ(n) (c) n φ(n)
2

96. 2 n = pk1 pk2 .....pkr is the canonical form for n > 1, then
If
1 2 r
a)
p1
φ(n) =
p2
n(1 + 1 )(1pr
+ 1 )......(1 + 1 )
b)
p1
φ(n) =
p2
n(1 ­ 1 )(1pr
­ 1 )......(1 ­ 1 )
c)
p
φ(n) =
p
(1 ­ 1 )(1p ­ 1 )......(1 ­ 1 )
1 2 r

97. Given integers a, b, c, gcd(a, bc) = 1 if and only if

a) gcd(a, b) = 1 and gcd(a, c) = 1
b) gcd(a, b) = 1 and gcd(b, c) = 1
c) gcd(a, b) = 1 and gcd(a, c) = b

98. φ(23 ) is
a) 2 b) 3 c) 7

99. Which of the following statement is false

a) If p is a prime and k > 0, then φ(pk ) = pk ­ pk­ 1
b) Given integers a, b, c, gcd(a, bc) = 1 then gcd(a, b) = 1 and gcd(a, c) = 1
c) φ is an one-to-one function

100. Which of the following statement is true

k 1
a) If p is a prime and k > 0, then φ(pp ) = (1 + )
b) Given integers a, b, c, gcd(a, bc) = 1 then gcd(a, b) = 1 and gcd(a, c) = 1
c) φ is an one-to-one function

12
Answer Key:
1 b 26 c 51 a 76 b

2 c 27 d 52 b 77 a

3 b 28 c 53 c 78 c

4 c 29 a 54 a 79 a

5 c 30 a 55 a 80 c

6 a 31 c 56 a 81 a

7 a 32 b 57 a 82 c

8 a 33 c 58 a 83 a

9 b 34 b 59 b 84 b

10 d 35 c 60 c 85 b

11 d 36 c 61 a 86 a

12 d 37 c 62 a 87 a

13 a 38 a 63 b 88 b

14 c 39 a 64 b 89 a

15 c 40 b 65 a 90 a

16 a 41 b 66 c 91 b

17 b 42 c 67 c 92 a

18 d 43 b 68 c 93 b

19 a 44 c 69 b 94 c

20 a 45 d 70 a 95 c

21 a 46 a 71 c 96 b

22 d 47 a 72 b 97 a

23 a 48 b 73 a 98 c

24 c 49 c 74 b 99 c

25 c 50 d 75 a 100 b