Number Theory — Concept, Formulas & Examples

Example: Find if 5741648 is divisible by 101 or not.

Solution:
Here we need to find divisiblity with 101 (10² + 1). Hence we make pair of 2-digit starting from right side.

5 74 16 48

Now, we add the alternate pair of digits
x = 48 + 74 = 122
y = 16 + 5 = 21

Now, x - y = 122 - 21 = 101.

Since, x - y is divisible by 101, the original number 5741648 is also divisible by 101.

Example: Find if 5741648 is divisible by 99 or not.

Solution:
Here we need to find divisiblity with 99 (10² - 1). Hence we make pair of 2-digit starting from right side.

5 74 16 48

Now, we add these pair of digits
5 + 74 + 16 + 48 = 143

Since, 143 is not divisible by 99, the original number 5741648 is also not divisible by 99.

Example: Find unit's digit of (123)²³

Solution:
Unit's digit of (123)²³ = Unit's digit of 3²³

= Unit's digit of 3^{4×5 + 3}

= Unit's digit of 3³

= 7

Example: Find unit's digit of (23454)⁷⁶⁹

Solution:
Unit's digit of (23454)⁷⁶⁹ = Unit's digit of 4⁷⁶⁹

We know Unit's digit of 4^{odd number} = 4

∴ Unit's digit of (23454)⁷⁶⁹ = 4

Example: Find unit's digit of (582)⁹⁴⁵

Solution:
Unit's digit of (582)⁹⁴⁵ = Unit's digit of 2⁹⁴⁵

= Unit's digit of 2^{4×236 + 1}

= Unit's digit of 2¹

= 2

Example: Find unit's digit of ${\left(147\right)}^{{61}^{25}}$

Solution:
Unit's digit of ${\left(147\right)}^{{61}^{25}}$ = Unit's digit of ${\left(7\right)}^{{61}^{25}}$

Now, 61²⁵ when divided by 4 leaves a remainder of 1 [Concept of Remainders]

∴ Unit's digit of ${\left(7\right)}^{{61}^{25}}$ = Unit's digit of 7^{4k + 1}

= Unit's digit of 7¹

= 7

Example: Divide 100 successively by 2 and 5.

Solution:
We first divide 100 by 2. The quotient will be 50

Now, we divide 50 by 5 and the final answer will be 10.

Example: What are the remainder when 100 is successively divided by 3 and 5.

Solution:
We first divide 100 by 3. The quotient will be 33 while the remainder will be 1.

Now, we divide 33 by 5. The quotient will be 6 while the remainder will be 3.

∴ When 100 is successively divided by 3 and 5, the remainders are 1 and 3 respectively.

Example: Find the smallest possible number which when successively divided by 3 and 4 leaves remainder of 1 and 3 respectively.

Solution:
In such examples we need to start from the last of the successive divisions.

When divided by 4 the remainder is 3. Since we need to find the smallest possible such number, we will assume the quotient for this division to be 0.
∴ The smallest possible number which when divided by 4 leaves remainder 3 is 3 itself.

Now, 3 must have been the quotient of previous division.

We need to find the number which when divided by 3 gives quotient as 3 and leaves remainder of 1.

∴ Original number = 3 × 3 + 1 = 10

The smallest number which when successively divided by 3 and 4 leaves remainder of 1 and 3 respectively is 10.

Example: Find the smallest possible number which when successively divided by 2 and 5 leaves remainder of 1 and 4 respectively.

Solution:
In such examples we need to start from the last of the successive divisions.

When divided by 5 the remainder is 4. Since we need to find the smallest possible such number, we will assume the quotient for this division to be 0.
∴ The smallest possible number which when divided by 5 leaves remainder 4 is 4 itself.

Now, 4 must have been the quotient of previous division.

We need to find the number which when divided by 2 gives quotient as 4 and leaves remainder of 1.

∴ Original number = 2 × 4 + 1 = 9

The smallest number which when successively divided by 2 and 5 leaves remainder of 1 and 4 respectively is 9.

Example: Find the smallest possible number which when successively divided by 2, 3 and 5 leaves remainder of 1, 2 and 3 respectively.

Solution:
In such examples we need to start from the last of the successive divisions.

When divided by 5 the remainder is 3. Since we need to find the smallest possible such number, we will assume the quotient for this division to be 0.
∴ The smallest possible number which when divided by 5 leaves remainder 3 is 3 itself.

Now, 3 must have been the quotient of previous division.

We need to find the number which when divided by 3 gives quotient as 3 and leaves remainder of 2.

∴ Number = 3 × 3 + 2 = 11

Now, 11 must have been the quotient of previous division.

We need to find the number which when divided by 2 gives quotient as 11 and leaves remainder of 1.

∴ Initial Number = 2 × 11 + 1 = 23

The smallest number which when successively divided by 2, 3 and 5 leaves remainder of 1, 2 and 3 respectively is 23.

Example: Find the highest three-digit number possible number which when successively divided by 2, 3 and 5 leaves remainder of 1, 2 and 3 respectively.

Solution:
In such example we need to first find the smallest possible such number.

The smallest number which when successively divided by 2, 3 and 5 leaves remainder of 1, 2 and 3 respectively is 23. (from previous example)

Now, N = 2 × 3 × 5 × k + 23

⇒ N = 30k + 23

Now, N = 30k + 23 < 1000

⇒ k < 977/30
∴ highest possible value of k = 32

∴ N = 30 × 32 + 23 = 983

Example: Find the smallest three-digit number possible number which when successively divided by 3 and 5 leaves remainder of 1 and 2 respectively.

Solution:
In such example we need to first find the smallest possible such number.

The smallest number which when successively divided by 3 and 5 leaves remainder of 1 and 2 respectively is 7.

Now, N = 3 × 5 × k + 7

⇒ N = 15k + 7

Now, N = 15k + 7 > 99

⇒ k > 92/15
∴ least possible value of k = 7

∴ N = 15 × 7 + 7 = 112

Example: Find the highest power of 2 in 10!.

Solution:
To find the highest power of 2 in 10!, we successively divide 10 by 2 and then add all the quotients.

$\mathrm{Q}\left[\frac{10}{2}\right]$ = 5

$\mathrm{Q}\left[\frac{5}{2}\right]$ = 2

$\mathrm{Q}\left[\frac{2}{2}\right]$ = 1

(We stop the division when quotient is less than the divisor)

∴ Highest power of 2 in 10! = 5 + 2 + 1 = 7

Example: Find the highest power of 5 in 100!.

Solution:
To find the highest power of 5 in 100!, we successively divide 100 by 5 and then add all the quotients.

$\mathrm{Q}\left[\frac{100}{5}\right]$ = 20

$\mathrm{Q}\left[\frac{20}{5}\right]$ = 4

∴ Highest power of 5 in 100! = 20 + 4 = 24

Example: Find the highest power of 6 in 10!.

Solution:
To find the highest power of 6 in 10!, we prime factorise 6 as 2 × 3. Now we will find the highest power of 2 and 3 in 10!

Highest power of 2 in 10! is 7 (obtained in previous example).

To find the highest power of 3 in 10!, we successively divide 10 by 3 and then add all the quotients.

$\mathrm{Q}\left[\frac{10}{3}\right]$ = 3

$\mathrm{Q}\left[\frac{3}{3}\right]$ = 1

∴ Highest power of 3 in 10! = 3 + 1 = 4

∴ N! can be written as 2⁷ × 3⁴ × X (X is coprime to both 2 and 3)

⇒ N! = 2³ × 6⁴ × X

∴ Highest power of 6 in 10! is 4.

Example: Find the highest power of 4 in 50!.

Solution:
To find the highest power of 4 in 5!, we prime factorise 4 as 2². Now we will find the highest power of 2 in 50!

To find the highest power of 2 in 50!, we successively divide 50 by 2 and then add all the quotients.

∴ Highest power of 2 in 50! = 25 + 12 + 6 + 3 + 1 = 47

∴ 50! can be written as 2⁴⁷ × X

⇒ 50! = (2²)²³ × 2 × X

⇒ 50! = 4²³ × 2 × X

∴ Highest power of 4 in 50! is 23.

Example: Find the highest power of 12 in 50!.

Solution:
To find the highest power of 12 in 50!, we prime factorise 12 as 2² × 3. Now we will find the highest power of 2 and 3 in 50!

Highest power of 2 in 50! is 47 (obtained in previous example).

To find the highest power of 3 in 50!, we successively divide 50 by 3 and then add all the quotients.

∴ Highest power of 3 in 50! = 16 + 5 + 1 = 22

∴ 50! can be written as 2⁴⁷ × 3²² × X

⇒ 50! = (2²)²² × 2³ × 3²² × X

⇒ 50! = 4²² × 3²² × 2³ × X

⇒ 50! = 12²² × 2³ × X

∴ Highest power of 12 in 50! is 22.

Example: Prime Factorise 180.

Solution:
Given, 180 = 4 × 45

⇒ 180 = 2² × 9 × 5

⇒ 180 = 2² × 3² × 5

∴ Prime Factorised form of 180 = 2² × 3² × 5

Example: Find the number of factors of 180.

Solution:
180 can be factorised as 2² × 3² × 5¹

∴ Number of factors of 180 = (2 + 1)(2 + 1)(1 + 1) = 18

Example: In how many ways can we write 180 as a product of two of its factors.

Solution:
180 can be factorised as 2² × 3² × 5¹

∴ Number of ways of writing 180 as a product of two of its factors = $\frac{1}{2}$(2 + 1)(2 + 1)(1 + 1) = 9

Example: In how many ways can we write 144 as a product of two of its factors.

Solution:
144 can be factorised as 2⁴ × 3²

∴ Number of ways of writing 144 as a product of two of its factors = $\frac{1}{2}$[(4 + 1)(2 + 1) - 1] + 1 = 8

Example: Find LCM of 10, 12 and 15.

Solution:
Let us prime factorise 10, 12 and 15.

10 = 2 × 5
12 = 2² × 5
15 = 3 × 5

The distinct prime factors for given numbers are 2, 3 and 5

Highest power of these prime numbers i.e., 2, 3 and 5 in the given numbers is 2, 1 and 1.

∴ LCM(10, 12 and 15) = 2² × 3¹ × 5¹ = 60

Example: Find LCM of 36, 48 and 64.

Solution:
Let us prime factorise 36, 48 and 64.

36 = 2² × 3²
48 = 2⁴ × 3
64 = 2⁶

The distinct prime factors for given numbers are 2 and 3

Highest power of these prime numbers i.e., 2 and 3 in the given numbers is 6 and 2.

∴ LCM(36, 48 and 64) = 2⁶ × 3² = 576

Example: Find the smallest 2-digit number which when divided by 2, 3 or 5 leaves remainder of 1.

Solution:
Let smallest such number is N.

N when divided by 2 leaves remainder of 1.
∴ N = 2 × a + 1
⇒ N - 1 = 2 × a ...(1)

N when divided by 3 leaves remainder of 1.
∴ N = 3 × b + 1
⇒ N - 1 = 3 × b ...(2)

N when divided by 5 leaves remainder of 1.
∴ N = 5 × c + 1
⇒ N - 1 = 5 × c ...(3)

From (1), (2) and (3) we can say that N - 1 is a multiple of 2, 3 and 5.
∴ N - 1 will be a multiple of LCM(2, 3, 5) ⇒ N - 1 = LCM(2, 3, 5) × k
⇒N = LCM(2, 3, 5) × k + 1 ⇒ N = 30k + 1

For N to be smallest 2-digit number we put k = 1, hence N = 31.

Example: Find the smallest 2-digit number which when divided by 2, 3 or 5 leaves remainder of 1, 2 and 4 respectively.

Solution:
Let smallest such number is N.

Here, divisors are 2, 3 and 5 while remainders are 1, 2 and 4 respectively such that
2 - 1 = 3 - 2 = 5 - 4 = 1 (d)

N when divided by 2 leaves remainder of 1.
∴ N = 2 × a + 1
⇒ N - 1 = 2 × a
Adding 2 (divisor) both sides we get
N + 1 = 2(a + 1) ...(1)

N when divided by 3 leaves remainder of 2.
∴ N = 3 × b + 2
⇒ N - 2 = 3 × b
Adding 3 (divisor) both sides we get
N + 1 = 3(b + 1) ...(2)

N when divided by 5 leaves remainder of 4.
∴ N = 5 × c + 4
⇒ N - 4 = 5 × c
Adding 5 (divisor) both sides we get
N + 1 = 5(c + 1) ...(3)

From (1), (2) and (3) we can say that N + 1 is a multiple of 2, 3 and 5.
∴ N + 1 will be a multiple of LCM(2, 3, 5) ⇒ N + 1 = LCM(2, 3, 5) × k
⇒ N = LCM(2, 3, 5) × k - 1 (d) ⇒ N = 30k - 1

For N to be smallest 2-digit number we put k = 1, hence N = 29.

Example: Find the highest 2-digit number which when divided by 3 or 5 leaves remainder of 1 and 4 respectively.

Solution:
Let smallest such number is n.

Here, divisors are 2 and 5 while remainders are 1 and 4 respectively such that
3 - 1 ≠ 5 - 4

n when divided by 5 leaves remainder of 4.
∴ n = 5 × a + 4
⇒ n can be 4, 9, 14, 19, 24, 29, ... etc.

Now smallest value of n which when divided by 3 gives remainder 1 is 4.

Now we can generalise, any number which when divided by 3 or 5 and gives remainders as 1 or 4 respectively (N) = LCM(3, 5) × k + 4 = 15k + 4

For N to be highest 2-digit number (N) = 15k + 4 < 100
15k < 96
k < 6.4

Highest possible value of k = 6

Highest 2-digit value of N = 15 × 6 + 4 = 94

Example: Find the smallest 3-digit number which when divided by 12 or 15 leaves remainder of 2 and 8 respectively.

Solution:
Let smallest such number is n.

Here, divisors are 12 and 15 while remainders are 2 and 8 respectively such that
12 - 2 ≠ 15 - 8

n when divided by 15 leaves remainder of 8.
∴ n = 15 × a + 8
⇒ n can be 8, 23, 38, 53, 68, 83, ... etc.

Now smallest value of n which when divided by 12 gives remainder 2 is 38.

Now we can generalise, any number which when divided by 12 or 15 and gives remainders as 2 or 8 respectively (N) = LCM(12, 15) × k + 38 = 60k + 38

For N to be smallest 3-digit number (N) = 60k + 38 > 99
⇒ 60k > 61
⇒ k > 1.01

Least possible value of k = 2

Smallest 3-digit value of N = 60 × 2 + 38 = 158

Example: Find HCF of 12 and 18.

Solution:
Let us prime factorise 12 and 18.

12 = 2² × 3
18 = 2 × 3²

The common distinct prime factors for given numbers are 2 and 3

Smallest power of these prime numbers i.e., 2 and 3 in the given numbers is 1 and 1.

∴ HCF(12 and 18) = 2 × 3 = 6

Example: Find HCF of 36, 48 and 60.

Solution:
Let us prime factorise 36, 48 and 64.

36 = 2² × 3²
48 = 2⁴ × 3
60 = 2² × 3 × 5

The common distinct prime factors for given numbers are 2 and 3

Highest power of these prime numbers i.e., 2 and 3 in the given numbers is 2 and 1.

∴ LCM(36, 48 and 60) = 2² × 3 = 12

Example: The greatest number which divides 53 and 68 leaving remainders 5 and 8

Solution:
Let the required number be p.

53 when divided by p leaves a remainder of 5
∴ 53 = p × a + 5
⇒ 53 - 5 = p × a ⇒ a = (53 - 5)/p ...(1)

68 when divided by p leaves a remainder of 8
∴ 68 = p × b + 8
⇒ 68 - 8 = p × b
b = (68 - 8)/p ...(2)

From (1) and (2)
Since, a and b are integers, p should completely divided (53 - 5) and (68 - 8) i.e., 48 and 60

Highest possible value of p = HCF(48 and 60) = 12.

Example: The greatest number which divides 327, 223 and 411 leaving remainders 15, 7 and 3

Solution:
Highest possible such number = HCF[(327 - 15), (223 - 7), (411 - 3)] = HCF[312, 216, 408].

312 = 2³ × 3 × 13
216 = 2³ × 3³
408 = 2³ × 3 × 17

∴HCF[312, 216, 408] = 2³ × 3 = 24

Example: The greatest number which divides 470, 545 and 410 leaving remainders 5 and 8

Solution:
Let the required number be p.

470 when divided by p leaves a remainder of say r
∴ 470 = p × a + r
⇒ 470 - r = p × a ...(1)

545 when divided by p leaves a remainder of say r
∴ 545 = p × b + r
⇒ 545 - r = p × b ...(2)

410 when divided by p leaves a remainder of say r
∴ 410 = p × c + r
⇒ 410 - r = p × c ...(3)

(1) - (3)
470 - 410 = p(a - c)
a - c = (470 - 410)/p ...(4)

(2) - (3)
545 - 410 = p(b - c)
b - c = (545 - 410)/p ...(5)

(2) - (1)
545 - 470 = p(b - a)
b - a = (545 - 470)/p ...(6)

From (4), (5) and (6)
Highest possible value of p = HCF[(470 - 410), (545 - 410), (545 - 470)] = 15

Example: The greatest number which divides 559, 415 and 343 leaving remainders 5 and 8

Solution:
Let the required number be p.

Highest possible value of p = HCF[(559 - 415), (415 - 343)] = 72

Note: Taking LCM of 2 pairs will give the same answer as taking LCM of all 3 pairs.

Example: How many pair of numbers exist such that their HCF is 12 and LCM is 72.

Solution:
Let the required numbers be a and b.

Since their HCF is 12, a = 12x and b = 12y where x and y are co-prime numbers.

Now, product of two numbers = product of their HCF and LCM

∴ a × b = LCM × HCF
⇒ 12x × 12y = 12 × 72 ⇒ x × y = 6

Now, we need to write 6 as a product of two co-prime numbers.

⇒ 6 = 1 × 6 or 2 × 3

∴ x = 12 and y = 72 or x= 24 and y = 36

⇒ 2 pair of values are possible.

Example: Find the last 2 digits of (131)⁹⁹

Solution:

Last 2 digits of (131)⁹⁹ = Last 2 digits of (31)⁹⁹

Unit's digit of (131)⁹⁹ = 1

Ten's digit of (131)⁹⁹ = Unit's digit of 3 × 9 = 7

Last 2 digits of (131)⁹⁹ = 71

Example: Find the last 2 digits of (133)⁹⁹

Solution:
Last 2 digits of (133)⁹⁹ = Last 2 digits of (33)⁹⁹

We need to convert the given number in the form of (a1)^power

We know 4^th power of 3 gives last digit as 1.

Last 2 digits of (33)⁹⁹ = Last 2 digits of (33)⁹⁶ × 33³ 

= Last 2 digits of ((33)⁴)²⁴ × 33³ = Last 2 digits of ((89)²)²⁴ × 33² × 33

= Last 2 digits of (21)²⁴ × 89 × 33

= Last 2 digits of 81 × 89 × 33

= 97

Example: Find the last 2 digits of (257)¹³³

Solution:
Last 2 digits of (257)¹³³ = Last 2 digits of (57)¹³³

We need to convert the given number in the form of (a1)power

We know 4^th power of 7 gives last digit as 1.

Last 2 digits of (57)¹³³ = Last 2 digits of (57)¹³² × 57 

= Last 2 digits of ((57)⁴)³³ × 57 = Last 2 digits of ((49)²)³³ × 57

= Last 2 digits of (01)³³ × 57

= Last 2 digits of 01 × 57

= 57

Unit's digit of (01)³³ = 1
Ten's digit of (01)³³ = Unit's digit of 0 × 3 = 0
Last 2 digits of (01)³³ = 01

Example: Find the last 2 digits of (569)¹⁷⁰

Solution:
Last 2 digits of (569)¹⁷⁰ = Last 2 digits of (69)¹⁷⁰

We need to convert the given number in the form of (a1)^power

We know 2nd power of 9 gives last digit as 1.

Last 2 digits of (69)¹⁷⁰ = Last 2 digits of ((69)²)⁸⁵  

= Last 2 digits of (61)⁸⁵

= 01

Unit's digit of (61)⁸⁵ = 1
Ten's digit of (61)⁸⁵ = Unit's digit of 6 × 5 = 0
Last 2 digits of (61)⁸⁵ = 01

Example: Find the last 2 digits of (475)⁵⁸⁹

Solution:
Last 2 digits of (475)⁵⁸⁹ = Last 2 digits of (75)⁵⁸⁹

Last 2 digits of 75¹ = 75
Last 2 digits of 75² = 25
Last 2 digits of 75³ = 75
Last 2 digits of 75⁴ = 25
Last 2 digits of 75⁵ = 75
Last 2 digits of 75⁶ = 25

⇒ Last 2 digits of 75^{odd number} = 75
⇒ Last 2 digits of 75^{even number} = 25

∴ Since 589 is odd, Last 2 digits of 75⁵⁸⁹ = 75

Example: Find the last 2 digits of (345)²⁵⁰

Solution:
Last 2 digits of (345)²⁵⁰ = Last 2 digits of (45)²⁵⁰

Last 2 digits of 45¹ = 45
Last 2 digits of 45² = 25
Last 2 digits of 45³ = 25
Last 2 digits of 45⁴ = 25

⇒ Last 2 digits of 45^{power (> 1)} = 25

∴ Last 2 digits of 45²⁵⁰ = 25

Example: Find the last 2 digits of (472)¹⁰⁰

Solution:
Last 2 digits of (472)¹⁰⁰ = Last 2 digits of (72)¹⁰⁰

We need to convert the given number in the form of (2)^a × (odd)^b

∴ 72 can be written as 2³ × 9
∴ 72¹⁰⁰ can be written as 2³⁰⁰ × 9¹⁰⁰

Last 2 digits of 2³⁰⁰ = Last 2 digits of 2^{30 × 10} = 76

Last 2 digits of 9¹⁰⁰ = Last 2 digits of 81⁵⁰ = 01

⇒ Last 2 digits of 72¹⁰⁰ = Last 2 digits of 76 × 01 = 76

Example: Find the last 2 digits of (54)²¹⁰

Solution:

We need to convert the given number in the form of (2)^a × (odd)^b

∴ 54 can be written as 2 × 27
∴ 54²¹⁰ can be written as 2²¹⁰ × 27²¹⁰

Last 2 digits of 2²¹⁰ = Last 2 digits of 2^{21 × 10} = 24

Last 2 digits of 27²¹⁰ = Last 2 digits of (27²)¹⁰⁵
Last 2 digits of 27²¹⁰ = Last 2 digits of (29)¹⁰⁵
Last 2 digits of 27²¹⁰ = Last 2 digits of (29²)⁵² × 29
Last 2 digits of 27²¹⁰ = Last 2 digits of (41)⁵² × 29
Last 2 digits of 27²¹⁰ = Last 2 digits of 81 × 29
Last 2 digits of 27²¹⁰ = 49

⇒ Last 2 digits of 54²¹⁰ = Last 2 digits of 24 × 49 = 76

Example: Find the remainder when 37 × 48 is divided by 5

Solution:

$\mathrm{R}\left[\frac{37\times 48}{5}\right]$ = $\mathrm{R}\left[\frac{37}{5}\right]$ × $\mathrm{R}\left[\frac{48}{5}\right]$ = 2 × 3 = 6

Since 6 ≥ 5, we can get the final remainder by finding the remainder of 6 with 5.

= $\mathrm{R}\left[\frac{6}{5}\right]$ = 1

Note: $\mathrm{R}\left[\frac{37\times 48}{5}\right]$ = $\mathrm{R}\left[\frac{1776}{5}\right]$ = 1

Example: Find the remainder when 2¹⁰⁰ is divided by 5

Solution:
Let us check remainders of various powers of 2 when divided by 5.

$\mathrm{R}\left[\frac{2^1}{5}\right]$ = 2

$\mathrm{R}\left[\frac{2^2}{5}\right]$ = 4
$\mathrm{R}\left[\frac{2^3}{5}\right]$ = 3
$\mathrm{R}\left[\frac{2^4}{5}\right]$ = 1
$\mathrm{R}\left[\frac{2^5}{5}\right]$ = 2
$\mathrm{R}\left[\frac{2^6}{5}\right]$ = 4
$\mathrm{R}\left[\frac{2^7}{5}\right]$ = 3
$\mathrm{R}\left[\frac{2^8}{5}\right]$ = 1

We see that remainders follow a cyclic pattern which repeats after every 4 powers of 2.

∴ $\mathrm{R}\left[\frac{2^{\mathrm{4k}}}{5}\right]$ = $\mathrm{R}\left[\frac{2^4}{5}\right]$ = 1
∴ $\mathrm{R}\left[\frac{2^{\mathrm{4k+1}}}{5}\right]$ = $\mathrm{R}\left[\frac{2^1}{5}\right]$ = 2
∴ $\mathrm{R}\left[\frac{2^{\mathrm{4k+2}}}{5}\right]$ = $\mathrm{R}\left[\frac{2^2}{5}\right]$ = 4
∴ $\mathrm{R}\left[\frac{2^{\mathrm{4k+3}}}{5}\right]$ = $\mathrm{R}\left[\frac{2^3}{5}\right]$ = 3

⇒ $\mathrm{R}\left[\frac{2^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{2^{\mathrm{4*25}}}{5}\right]$ = 1

Example: Find the remainder when 12¹⁰⁰ is divided by 5

Solution:
$\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{12}{5}\right]$ × $\mathrm{R}\left[\frac{12}{5}\right]$ × $\mathrm{R}\left[\frac{12}{5}\right]$ × ... × $\mathrm{R}\left[\frac{12}{5}\right]$ [100 times]

⇒ $\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = 2 × 2 × 2 × ... × 2 [100 times] = 2¹⁰⁰

Since 2¹⁰⁰ is greater than the divisor 5, we again calculate the remainder of 2¹⁰⁰ when divided by 5

∴ $\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{2^{100}}{5}\right]$

Now, this question becomes same as the previous example.

∴ $\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{2^{100}}{5}\right]$ = 1

Example: Find the remainder when 18¹¹¹ is divided by 7

Solution:
$\mathrm{R}\left[\frac{{18}^{111}}{7}\right]$ = ${\left(\mathrm{R}\left[\frac{18}{7}\right)\right]}^{111}$

⇒ $\mathrm{R}\left[\frac{{18}^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{4^{111}}{7}\right]$

Now, let us figure out the cyclicity of remainder of powers of 4 when divided by 7.

$\mathrm{R}\left[\frac{4^1}{7}\right]$ = 4

$\mathrm{R}\left[\frac{4^2}{7}\right]$ = 2

$\mathrm{R}\left[\frac{4^3}{7}\right]$ = 1

Remainders will repeat after this. Remainders start repeating after remainder 1 is obtained.

∴ Cyclicity is of three terms.

⇒ $\mathrm{R}\left[\frac{4^{3k}}{7}\right]$ = 1

⇒ $\mathrm{R}\left[\frac{4^{3k+1}}{7}\right]$ = 4

⇒ $\mathrm{R}\left[\frac{4^{3k+2}}{7}\right]$ = 2

Now, $\mathrm{R}\left[\frac{4^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{4^{3\times 37}}{7}\right]$ = 1

∴ $\mathrm{R}\left[\frac{{18}^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{4^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{4^{3\times 37}}{7}\right]$ = 1

Example: Find the remainder when 2¹¹¹ is divided by 9

Solution:
$\mathrm{R}\left[\frac{2^{111}}{9}\right]$

Let us figure out the cyclicity of powers of 2 when divided by 9.

⇒ $\mathrm{R}\left[\frac{2^1}{9}\right]$ = 2

⇒ $\mathrm{R}\left[\frac{2^2}{9}\right]$ = 4

⇒ $\mathrm{R}\left[\frac{2^3}{9}\right]$ = 8 or negative remainder is -1

∴ $\mathrm{R}\left[\frac{2^6}{9}\right]$ = ${\left(\mathrm{R}\left[\frac{2^3}{9}\right)\right]}^2$ = (-1)² = 1

∴ The cyclicity of remainders is that of 6 terms.

⇒ $\mathrm{R}\left[\frac{2^{111}}{9}\right]$ = $\mathrm{R}\left[\frac{2^{6\times 18+3}}{9}\right]$ = $\mathrm{R}\left[\frac{2^3}{9}\right]$ = 8

Example: Find the remainder when 8¹⁰⁰ is divided by 13.

Solution:

Using FLT we know, $\mathrm{R}\left[\frac{8^{13-1}}{13}\right]$ i.e., $\mathrm{R}\left[\frac{8^{12}}{13}\right]$ = 1

Now we can need to find $\mathrm{R}\left[\frac{8^{100}}{13}\right]$

= $\mathrm{R}\left[\frac{8^{96+4}}{13}\right]$

= $\mathrm{R}\left[\frac{8^{96}}{13}\right]$ × $\mathrm{R}\left[\frac{8^4}{13}\right]$

= ${\left(\mathrm{R}\left[\frac{8^{12}}{13}\right)\right]}^8$ × $\mathrm{R}\left[\frac{8^2}{13}\right]$ × $\mathrm{R}\left[\frac{8^2}{13}\right]$

= 1 × -1 × -1

= 1