Euler/Fermat's Little Theorem | Algebra - Number Theory

Answer: 1

Join our Telegram Channel for CAT/MBA Preparation.

Explanation :

Using Fermat’s Little Theorem we know, remainder of a^(p-1) when divided by p is 1.

where p is a prime number, a and p are co-primes.

Here, a = 2 and p = 5.

∴ Remainder when 2⁴ is divided by 5 = 1.

⇒ R[2¹⁰⁰/5] = R[2^4×25/5] = R[2⁴/5]²⁵ = 1²⁵ = 1.

Hence, 1.

Answer: 1

Join our Telegram Channel for CAT/MBA Preparation.

Explanation :

Using Fermat’s Little Theorem we know, remainder of a^(p-1) when divided by p is 1.

where p is a prime number, a and p are co-primes.

Here, a = 2 and p = 31.

∴ Remainder when 2³⁰ is divided by 31 = 1.

⇒ R[2¹²⁰/31] = R[2^30×4/31] = R[2³⁰/31]⁴ = 1⁴ = 1.

Hence, 1.

Answer: 2

Join our Telegram Channel for CAT/MBA Preparation.

Explanation :

Using Fermat’s Little Theorem we know, remainder of a^(p-1) when divided by p is 1.

where p is a prime number, a and p are co-primes.

Here, a = 2 and p = 7.

∴ Remainder when 2⁶ is divided by 7 = 1.

⇒ R[2¹⁰⁰/7] = R[2^6×16+4/7] = R[2⁶/7]¹⁶ × R[2⁴/7] = 1¹⁶ × 2 = 2.

Hence, 2.

Answer: 4

Join our Telegram Channel for CAT/MBA Preparation.

Explanation :

Using Fermat’s Little Theorem we know, Remainder of a^(p-1) when divided by p is 1.

where p is a prime number, a and p are co-primes.

Here, a = 3 and p = 7.

∴ Remainder when 3⁶ is divided by 7 = 1.

⇒ R[3¹⁰⁰/7] = R[3^6×16+4/7] = R[3⁶/7]¹⁶ × R[3⁴/7] = 1 × 4 = 4.

Hence, 4.

Answer: 8

Join our Telegram Channel for CAT/MBA Preparation.

Explanation :

Using Fermat’s Little Theorem we know, Remainder of a^(p-1) when divided by p is 1.

where p is a prime number, a and p are co-primes.

Here, a = 5 and p = 13.

∴ Remainder when 5¹² is divided by 13 = 1.

⇒ R[5⁸⁷/13] = R[5^12×7+3/13] = R[5¹²/13]⁷ × R[5³/13] = 1 × 8 = .

Hence, 8

Answer: 8

Join our Telegram Channel for CAT/MBA Preparation.

Explanation :

Here, 6 and 14 have a common factor i.e., 2.

⇒ R[6¹⁰⁰/14] = R[2¹⁰⁰×3¹⁰⁰/14] = 2 × R[2⁹⁹×3¹⁰⁰/7] = 2 × R[2⁹⁹/7] × R[3¹⁰⁰/7]

Now, R[3¹⁰⁰/7] = 4

and, R[2⁹⁹/7] = 1

∴ R[6¹⁰⁰/14] = 2 × R[2⁹⁹/7] × R[3¹⁰⁰/7] = 2 × 1 × 4 = 8.

Alternately,

Let us find the pattern that remainders follow when successive powers of 6 are divided by 14.

Remainder when 6¹/14 = 6.
Remainder when 6²/14 = 8.
Remainder when 6³/14 = 6.
Remainder when 6⁴/14 = 8.

∴ We find that the remainders are repeated after every two powers.

⇒ R[6¹⁰⁰/14] = R[6²/14] = 8

Hence, 8.

Answer: 7

Join our Telegram Channel for CAT/MBA Preparation.

Explanation :

According to Euler's theorem, a^φ(n)​​​ when divided by n leaves a remainder of 1, where a and n are co-primes.

φ(n) is the number of co-primes to n which are less than n.

Here, a = 7 and n = 30 = 2 × 3 × 5

∴ φ(n) = $30\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)$ = 8

⇒ 7⁸ when divided by 30 will give a remainder of 1

⇒ R$\left[\frac{7^{73}}{30}\right]$ = R$\left[\frac{7^{72}\times 1}{30}\right]$ = R${\left[\frac{7^8}{30}\right]}^9$ × R$\left[\frac{7}{30}\right]$ = 1⁹ × 7 = 7

Hence, 7.