Congruence MCQ Quiz - Objective Question with Answer for Congruence - Download Free PDF

Explanation:

To solve the congruence relation \(2x \equiv 1 \mod{7}\)  we need to find an integer x

such that when multiplied by 2, it leaves a remainder of 1 when divided by 7.

We need to find an integer y such that:

\(2y \equiv 1 \mod{7}\)

We can check the values of y from 1 to 6:

For y = 1 : 2 .1 = 2 (not congruent to 1)

For y = 2 : 2. 2 = 4 (not congruent to 1)

For y = 3 : 2 . 3 = 6 (not congruent to 1)

For y = 4 : 2 . 4 = 8 \(\equiv 1 \mod{7}\)

So, y = 4 is the multiplicative inverse of 2 modulo 7.

Now we can multiply both sides of the original congruence \(2x \equiv 1 \mod{7}\) by

4,

\(4 \cdot (2x) \equiv 4 \cdot 1 \mod{7}\)
 

Hence option 1 is correct.

Concept Used:

For a positive integer n, Euler's totient function is defined as follows:

\( \phi(n) = \text{number of positive integers } k \leq n \text{ such that } \text{gcd}(n, k) = 1\)

Here, gcd(n, k) represents the greatest common divisor of n and k.

Some properties of Euler's totient function include:

• ϕ(1)  = 1, as 1 has no positive integers less than itself.

Explanation:

Given: f(x) = x2 - 4x + 4

f(x) = 0

⇒ x2 - 4x + 4 = 0

⇒ (x - 2)2 = 0

⇒ x - 2 = 0

⇒ x = 2

Thus, only solution to the given equation f(x) = 0 is x = 2.

Thus, n = 1.

Thus, ϕ(n) = ϕ(1) = 1

1 is neither a prime nor an even number.

Thus, options 1 and 2 are incorrect.

1 is also not a multiple of 3, thus option 4 is also not correct.

Thus, correct option is option 3.

Explanation -

We can start by considering the possible factors of the difference between 26 and 5, which is  26 - 5 = 21.

The factors of 21 are 1, 3, 7, and 21.

Now, let's check which of these values satisfy 26 ≡ 5 (mod x).

For x = 1,  26 and  5  are not congruent because any integer divided by 1 will always have the same remainder.

For x = 3, 26 ≡  5 (mod 3) because both 26 and 5  leave the same remainder 2 when divided by 3.

For x = 7, 26 ≡ 5 ( mod 7) because both  26 and  5  leave the same remainder 5 when divided by 7.

For x = 21, 26 ≡ 5 ( mod 21 ) because both 26 and 5 leave the same remainder 5 when divided by 21.

Therefore, the set of values of x satisfying 26 ≡ 5 (mod x) is {3, 7, 21}

Hence Option(4) is correct.

Concept: 

If b is the remainder when a is divisible be m then a ≡ b (mod m)

Explanation:

We know that

16 ≡ -2 (mod 9)

(16)³ ≡ - 8 (mod 9) 

(16)3 ≡ 1 (mod 9) (since -8 ≡ 1 (mod 9) )

((16)3)⁶⁷² ≡ (1)⁶⁷² (mod 9) 

(16)2016 ≡ 1 (mod 9) 

ence The remainder obtained when 162016 is divided by 9 equals 1.

Option (1) is correct

Concept:

Linear congruence: A congruence of the form ax ≡ b(mod m) where x is an unknown integer is called a linear congruence in one variable where,

a, b and m are integers in which m must be prime number.

Wilson theorem:  According to this theorem, if p is a prime number, than

(p - 1)! = -1 (mod P)

In other words, when (P - 1)! is divided by P, than remainder is p - 1

⇒ \(\rm Rem\ \left[\dfrac{(P - 1)!}{P}\right] = P \ - \ 1\)

Where n! = n(n - 1)(n - 2).......3.2.1

Similarly

(P - 2)! = 1(mod P)

\(\rm (P\ - \ 3)!\ = \dfrac{P - 1}{2}(mod \ P)\)

Calculation:

Given that,  

27! = x (mod 29)     ---(1)

We can see that, P = 29 which is prime number. Hence, Wilson theorem can be used.

We know that

(P - 2)! = 1(mod P)

On comparing (1) with this property, we will get

x = 1

Hence, option 1 is the correct option.

Concept:

Chinese remainder theorem(CRT):

Let a and b be two relatively prime (coprime) numbers such that 0 ≤ r < a and  0 ≤ s < b. There exists a unique number N such that 0 ≤ N < ab and

\(r\ \equiv N \ mod(a)\)

\(s\ \equiv N \ mod(b)\)

i.e. N has remainder r on dividing by a and remainder s on dividing by b.

Calculation:

Given simultaneous congruences are

\(x\ \equiv 5 \ mod(25)\)   ----(1)

\(x\ \equiv 32 \ mod(23)\)   ----(2)

That means we have to find x such that, when it is divided by 25, gives remainder 5 and when divided by 23, gives a remainder 32.

⇒ x = 25a + 5

Where, a = 0, 1, 2, ...

⇒ x = 5, 30, 55, 80, ...

x = 23b + 32

⇒ x = 32, 55, 87, .... 

x will satisfy both equations simultaneously. 

x = 55

∵ LCM of 25 & 23 is 575

Hence, the general solution of x will be 55 + 575k

(3) is correct

Concept:

Fermat’s little theorem: It states that if p is a prime number, then for any integer a, the number a p – a is an integer multiple of p. 

• Here p is a prime number a^p ≡ a (mod p).
• If 2^p ≡ 2 (mod p) i,e, 2p - 2 is divisible by p.

Given:

X = 3 (mod 9), X = 7 (mod 13)

Concept:

Chinese Remainder Theorem:

If m1, m2, .., mk are pairwise relatively prime positive integers, and if a1, a2, .., ak are any integers, then

The simultaneous congruences

x ≡ a1 (mod m1),

x ≡ a2 (mod m2)

x ≡ ak (mod mk)

have a solution, and the solution is unique modulo M, where

M = m1m2⋅⋅⋅mk .

Now, the solution x is given by

X = M1X1a1 + M2X2a2+......... + MkXkak 

Where, 

\(M_i = \frac{M}{m_i}\), I = 1, 2, 3, ....K    

and

MiXi  ≡ 1 mod(mi)

Calculation:

We have given,

x = 3 (mod9),

x = 7 (mod13)

m1 = 9 and m2 = 13 which are relatively co-prime.

Also, a1 = 3 and a2 = 7, which are integer.

Hence the condition of the Chinese  Remainder Theorem satisfied.

So, according to the theorem, there will be the unique solution of x for modulo

M = 9 × 13 = 117

Now, using the relation,

 \(M_i = \frac{M}{m_i}\)     

we will get

M1 = 13 and M2 = 9

To calculate X1 and X2 we can use the relation,

MiXi  ≡ 1 (mod mi)

⇒ 13X1  ≡ 1 (mod 9)

⇒  4X1  ≡ 1 (mod 13)

Multiplying both sides with 7, we will get

28X1  ≡ 7 (mod 9)

⇒ X1  ≡ 7 (mod 9)

⇒ X1 = 7

Again, using the above relation

9X2  ≡ 1 mod(13)

⇒ 27X2  ≡ 3 mod(13)

⇒ X2  ≡ 3 mod(13)

⇒ X2  = 3

Hence the unique solution of x will be

X = M1X1a1 + M2X2a2

⇒ X = 13 × 7 × 3 +  9 × 3 × 7 = 138

⇒ X ≡ 462 mod(117)

⇒ X ≡ 111 mod(117)

Concept:

Fermat´s theorem: 

• If p is a prime and p doesn´t divide a, then a p - 1 ≡ 1(mod p).
• If a ≡  b (mod n) and c ≡  d (mod n) then a + c ≡ b + d (mod n) where a, b, c, d are any integers.

Calculation:

Here 7 is a prime  And gcd(2, 7) = gcd(3, 7) = gcd(4, 7) = gcd(5, 7) = gcd(11, 7) = 1

So,by using Fermat´s theorem,

Consider, 2^{7 - 1} ≡ 1(mod 7) ⇒ 2⁶ ≡ 1(mod 7) ⇒ ( 2⁶)³ ≡ 1(mod 7)

⇒ 218 ≡ 1(mod 7)

multiply throughout by 2²,we get

⇒ 2¹⁸ . 2²  ≡ 2² (mod 7) ⇒ 220 ≡ 4(mod 7)       .....(1)

Next consider, 37 - 1 ≡ 1(mod 7) ⇒ 36 ≡ 1(mod 7) ⇒ ( 36)5 ≡ 1(mod 7)

⇒ 330 ≡ 1(mod 7)       ......(2)

Next consider, 47 - 1 ≡ 1(mod 7) ⇒46 ≡ 1(mod 7) ⇒ ( 46)6 ≡ 1(mod 7)

⇒ 436 ≡ 1(mod 7)

multiply throughout by 44,we get

⇒ 4³⁶. 44​  ≡ 44 (mod 7) ⇒ 440 ≡ 256 (mod 7)  ⇒ 440 ≡ 4(mod 7)  ......(3)

Next consider, 57 - 1 ≡ 1(mod 7) ⇒56 ≡ 1(mod 7) ⇒ ( 56)8 ≡ 1(mod 7)

⇒ 548 ≡ 1(mod 7)

multiply throughout by 5²,we get

⇒ 548 . 5² ≡ 52  (mod 7) ⇒ 550 ≡ 25  (mod 7) ⇒ 550 ≡ 4  (mod 7)       ....(4)

Finally consider, 117 - 1 ≡ 1(mod 7) ⇒116 ≡ 1(mod 7)

multiply throughout by 11,we get

⇒11⁶ . 11 ≡ 11 (mod 7) ⇒ 117  ≡ 11(mod 7) ⇒ 117  ≡ 4(mod 7)       ......(5)

Now adding (1), (2), (3), (4) and (5) we get,

220 + 330 + 440 + 550 + 117 ≡ (4 + 1 + 4 + 4 + 4 )(mod 7)  | using (6)

⇒ 220 + 330 + 440 + 550 + 117 ≡ 17 (mod 7) ⇒ 220 + 330 + 440 + 550 + 117 ≡ 3 (mod 7)

Hence, the correct answer is option 4)

Concept :

For any fixed integer n > 1 and for any arbitrary integers a, b, c and d.

If a ≡ b (mod n) and c ≡ d (mod n) then

• a + c ≡ b + d (mod n) and 
• ac ≡ bd (mod n)

Proof:

Firstly,

Given , a ≡ b (mod n) and c ≡ d (mod n) 

⇒ n | (a - b) and n | (c - d)

⇒ a - b = hn and c - d = kn ; for some integers h and k    ---(1)

Now consider, a - b + c - d = nh + nk

⇒ (a + c) - (b + d) = n (h + k)         ( ∵ h + k is an integer )

⇒ n | [ (a + c) - (b + d) ]

⇒ a + c ≡ b + d (mod n)

Next,

From (1) we have,

a = b + hn and c = d + kn

Consider, ac = (b + hn) × (d + kn)

⇒ ac = bd + bkn + hnd + hknn

⇒ ac - bd = n (bk + hd + hkn) 

⇒ n | ac - bd                                  ( ∵ (bk + hd + hkn) is an integer )

⇒ ac ≡ bd (mod n)

Hence, the correct answer is option 3)

Given:

X = 3 (mod 5), X = 5 (mod 7)

Concept:

Chinese Remainder Theorem:

If m1, m2, .., mk are pairwise relatively prime positive integers, and if a1, a2, .., ak are any integers, then

The simultaneous congruences

x ≡ a1 (mod m1),

x ≡ a2 (mod m2)

x ≡ ak (mod mk)

have a solution, and the solution is unique modulo M, where

M = m1m2⋅⋅⋅mk .

Now, the solution x is given by

X = M1X1a1 + M2X2a2+......... + MkXkak 

Where, 

\(M_i = \frac{M}{m_i}\), I = 1, 2, 3, ....K    

and

MiXi  ≡ 1 mod(mi)

Modulo or modulus or mod: It is the remainder after dividing one number by another.

Calculation:

We have given,

m1 = 5 and m2 = 7 which are relatively co-prime.

Also, a1 = 3 and a2 = 5, which are integer.

Hence the condition of the Chinese  Remainder Theorem satisfied.

SO, according to the theorem, there will be the unique solution of x for modulo

M = 5 × 7 = 35

Now, using the relation,

 \(M_i = \frac{M}{m_i}\)     

we will get

M1 = 7 and M2 = 5

To calculate X1 and X2 we can use the relation,

MiXi  ≡ 1 mod(mi)

⇒ 7X1  ≡ 1 mod(5)

⇒  2X1  ≡ 1 mod(5)

Multiplying both sides with 3, we will get

6X1  ≡ 3 mod(5)

⇒ X1  ≡ 3 mod(5)

⇒ X1 = 3

Again, using the above relation

5X2  ≡ 1 mod(7)

⇒ 15X2  ≡ 3 mod(7)

⇒ X2  ≡ 3 mod(7)

⇒ X2  = 3

Hence the unique solution of x will be

X = M1X1a1 + M2X2a2

⇒ X = 7 × 3 × 3 +  5 × 5 × 3 = 138

⇒ X ≡ 138 mod(35)

⇒ X ≡ 33 mod(35)

Concept:

Linear congruence: A congruence of the form ax ≡ b(mod m) where x is an unknown integer is called a linear congruence in one variable where,

a, b and m are integers in which m must be prime number.

Wilson theorem:  According to this theorem, if p is a prime number, than

(p - 1)! = -1 (mod P)

In other words, when (P - 1)! is divided by P, than remainder is p - 1

⇒ \(\rm Rem\ \left[\dfrac{(P - 1)!}{P}\right] = P \ - \ 1\)

Where n! = n(n - 1)(n - 2).......3.2.1

Similarly

(P - 2)! = 1(mod P)

\(\rm (P\ - \ 3)!\ = \dfrac{P - 1}{2}(mod \ P)\)

Calculation:

Given that,  

27! = x (mod 29)     ---(1)

We can see that, P = 29 which is prime number. Hence, Wilson theorem can be used.

We know that

(P - 2)! = 1(mod P)

On comparing (1) with this property, we will get

x = 1

Hence, option 1 is the correct option.

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: 

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)