Elementary Number Theory MCQ Quiz in मल्याळम - Objective Question with Answer for Elementary Number Theory - സൗജന്യ PDF ഡൗൺലോഡ് ചെയ്യുക

Concept:

Let b ∈ Z such that a^b ≡ 1(mod n).

Let us apply division algorithm to b and k then we have,

b = kq + r where 0 ≤ r ≤ k

Consider, a^b = a^{kq + r} = (a^k)^q . a^r

By hypothesis ab ≡ 1(mod n) and ak ≡ 1(mod n).

Hence, ar ≡ 1(mod n) where 0 ≤ r ≤ k

∴ r has to be equal to zero and otherwise the choice of k has the smallest positive integer such that ak ≡ 1(mod n) will be contradicted.

Hence, b = qk

⇒ k | b

⇒ k divides b

Hence, the correct answer is option 2)

Concept:

As we know that

a \(\equiv\) r (mod b) means when a is divided by b  then r is the remainder or can be written as 

a = bq + r where q is any positive integer.  

Euler's criteria:

If p is a prime where p | a, then the quadratic congruence x²  \(\equiv\) a (modm) has solutions or no solutions depending if \(a^\left({\frac{p-1}{2}}\right)=1. modp\)  or   \(a^\left({\frac{p-1}{2}}\right)=-1. modp\)

Calculation:

x2 + 1 ≡ 0 (mod p).

Case I: For x = 1

By definition of congruence and modulo we have 

p | x² + 1 

Let, x = 1 then p | 1² + 1 \(\Rightarrow \) p | 2

As, p can divide 2 only when p = 2.

Case II: For x > 1

As by Euler's criteria, p | x² + 1 if and only if \((-1)^\left({\frac{p-1}{2}}\right)=1. modp\).

Above condition can be only true if and only if the exponent of (-1) should be even.   ( As (-1)ⁿ = 1 if and only if n is even )

So, \(\frac{p-1}{2}\) should be even or is a multiple of 2.

\(\Rightarrow \frac{p-1}{2}= 2m\)   for m as some integer.

\(\Rightarrow p-1= 4m\)

p = 4m + 1 which is equivalent to p ≡ 1 (mod 4).   

Hence, If 'p' is a prime, then the congruence x2 + 1 ≡ 0 (mod p) has a solution if and only if p = 2 or p ≡ 1 (mod 4).

Concept:

Euclid division algorithm: If a and b are any integers and b > 0then there exists unique integers q and r such that a = bq + r where 0 ≤ r ≤ b.

Greatest common divisor: Let a and b be any two positive integers with atleast one of them different from zero then the greatest common divisor (GCD) of a and b is the positive integer d satisfying the following two conditions.

1. d | a and d | b
2. If c | a and c | b the c ≤ b then c ≤ d. Further c | d.

Calculations:

To find : gcd(4598, 3211) = ?

By using Euclid´s division algorithm, we have

\(4598 = 3211 ​\times 1 + 1387\)

⇒ \(3211= 1387 \times 2 + 437\)

⇒ \(1387 = 437 \times 3 + 76 \)

⇒ \(437 = 76 \times 5 + 57\)

⇒ \(76= 57 \times 1 + 19\)

⇒ \(57 = 19 \times 3 + 0\)

∴ gcd(4598, 3211) = 19

Hence, the correct answer is option 3)

Concept:

Euclid's division lemma: Given positive integers a and b there exist whole numbers q and r satisfying,

a = bq + r, where, 0 ≤ r ≤ b         ----(1)

• The remainder is always less than the divisor
• If r = 0 then a = bq so b divides a.

• Similarly, if b divides a then a = bq.

Calculation:

Using the division lemma, we can easily get the answer. 

To get the first number, let q = 0, r = 3 (given) and b = 5 (given)

⇒ a = 5(0) + 3         [using (1)]

⇒ a = 3

Similarly, To get the second number, let q = 1, r = 3 (given) and b = 5 (given)

⇒ a = 5(1) + 3

⇒ a = 8

Now, to get the third number, let q = 2, r = 3 (given) and b = 5 (given)

⇒ a = 5(2) + 3

⇒ a = 13

Thus, The next number will be 5 more than the preceding number.

So, the series would be 3, 8, 13, 18, 23, ...

Hence, the series of all positive integers, when divided by 5 leaves the remainder 3 is 3, 8, 13, 18, 23, ...

Concept: 

Chinese remainder theorem: Let n1, n2, ... ,nr be positive integers such that (ni, nj) = 1 for i ≠ j.Then the system of linear congruence x ≡ ai (mod ni) 1 ≤ i ≤ r, has a simultaneous solution which is unique modulo n1, n2, ... ,nr.

And the solution for the above system of linear congruence is given by x = a1N1x1 + a2N2x2 + ... + akNkxk

Calculations:

Given, x ≡ 1(mod 3) ;  x ≡ 2(mod 5) ;  x ≡ 3(mod 7)

we have n1 = 3 , n2 = 5, n3 = 7 and a1 = 1, a2 = 2, a3 = 3

And, gcd(3, 5) =  gcd(5, 7) = gcd(3, 7) = 1

Let n = n1. n2. n3 = 3 . 5 . 7 = 105

n = 105 Then, N1 = n/n1 = 105/3 = 35

N2 = n/n2 = 105/5 = 21 and N3 = n/n3 = 105/7 = 15

Now to find x1, x2 and x3 consider the congruences

N1x1 ≡ 1(mod n1) ⇒ 35x1 ≡ 1(mod 3) ⇒ x1 = -1

N2x2 ≡ 1(mod n2) ⇒ 21x2 ≡ 1(mod 5) ⇒ x2 = 1

similarly, N3x3 ≡ 1(mod n3) ⇒15x3 ≡ 1(mod 7) ⇒ x3 = 1

So, on substituting all the values in  x = a1N1x1 + a2N2x2 + a3N3x3

x = 1 × 35 × (-1) + 2 × 21 × 1 + 3 × 15 × 1 ⇒ x = 87 - 35 ⇒x = 52

Hence, the correct answer is option 4)

Concept:

Peano's axioms: 

1. Zero is a number.

2. For every natural number n, the successor of n is also a natural number. We denote the successor of n by S(n).

3. Zero is not the successor of any natural number n i.e.,S(n) = 0 is false.

4. Two numbers of which the successors are equal are themselves equal i.e.,for all natural numbers m and n, S(m) = S(n) if and only if m = n.

5. If a set K of numbers contains zero and also the successor of every number in K, then every number is in K (induction axiom).

(or) ) If K is a set of natural numbers such that

• 0 is in K, and
• for every natural number n, if n ∈ K then S(n) ∈ K. then K contains every natural number.

But option 3) is Euclid's axiom but not Peano's axiom.

Hence, the correct answer is option 3)

Concept:

Euclid's division lemma: If a and b are two positive integers, then there exists unique positive integers q and r such that 

 \(a=bq+r\) where \(0\leq{r}\ <\ {b}\) .

If b ∣ a then r = 0 otherwise r must satisfy stronger inequality 0 < r < b.

Explanation:

From the above discussion, we can conclude that Euclide division lemma can be applied in all positive integers

Hence, option 3 is correct.

Additional Information

• Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.
• The HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

Explanation:

\([{26\over2}]+[{26\over2^2}]+[{26\over2^3}]+[{26\over2^4}]\)

= 13 + 6 + 3 + 1 ([.] is greatest integer function)

= 23

then

26! = a2²³

⇒ 26! = a(2³)⁷× 2²

⇒ 26! = 4a × 8⁷

Comparing with 26! = n8k we get maximum value of k is 7.

Hence option (2) is true.

Concept:

Euclid's division lemma: It states that if 'p' and 'q' are positive integers then there exists 'a' and 'b' such that

p = aq + b    where,  0 ≤ b < q

Calculation:

Here in the given problem, we have 'p', and 'q' = 9 as any positive integers, then by applying the above lemma there exists 'a' and 'b' such that

p = 9q + b where,

0 ≤ b < 9 ( As q = 9)

Hence, the correct answer is 0 ≤  b < 9.  

Concept:

To find the last three digits of a number, you can simply take the number modulo 1000. This operation gives you the remainder when dividing the number by 1000, which effectively keeps only the last three digits.

Explanation:

Firstly, find 25⁶³ mod(1000)

25² ≡ 625 (mod1000)

⇒ 25⁶² ≡ 625³¹ (mod1000)

⇒ 62531 ≡ 625 (mod1000)

⇒ 25⁶² ≡ 625 (mod1000)

⇒ 25⁶³ ≡ 625 (mod1000) ....(1) 

To find 

625 x 63²⁵ (mod1000)

Now, 625 x 63 ≡ 375 (mod1000)

625 x 63² ≡ 625 (mod1000)

625 x 63³ ≡ 375 (mod1000)

........................................

⇒ 625 x 63²⁵ ≡ 375 (mod 1000) 

⇒ 25⁶³ x 63²⁵ ≡ 375 (mod1000)