Back

Factors & Remainders

ALL MODULES

CAT 2025 Lesson : Factors & Remainders - Euler & Fermat

4. Euler's Totient

Euler's Totient of a number is a function that provides a count of the natural numbers less than the number that would form a co-prime pair with it.

\phi (n)

is the function that represents the Euler's totient for the number

n

.

If the prime factors of

n

are

x_1, x_2, x_3, ...

\bm{ \phi (n)}

n \times \left(1 - \dfrac{1}{x_1}\right) \times \left(1 - \dfrac{1}{x_2}\right) \times \left(1 - \dfrac{1}{x_3}\right) \times ...

Example 23

How many natural numbers less than

24

are co-prime with

24

Solution

24 \times 2^3 \times 3

\therefore

The prime factors of

24

are

2

and

3

\phi (24) =

24 \times \left(1 - \dfrac{1}{2}\right) \times \left(1 - \dfrac{1}{3}\right)

= 24 \times \dfrac{1}{2} \times \dfrac{2}{3} = 8

Number of co-primes

= 8

Answer:

8

Note: The co-primes of

24

that are less than it are

1

5

7

11

13

17

19

and

23

4.1 Fermat's Little Theorem of Remainders

For any given number

n

and divisor

d

, if
(

1

)

n

and

d

are co-prime, and
(

2

)

\phi(d)

is the Euler's totient of

d

\mathrm{Rem} \left(\dfrac{n^{\phi(d)}}{d}\right) = 1

Example 24

What is the remainder when

79^{1983}

is divided by

12

Solution

We first reduce the base of

79

, applying the exponent rule.

\mathrm{Rem} \left(\dfrac{79^{1983}}{12}\right) = \mathrm{Rem} \left(\dfrac{(72 + 7)^{1983}}{12}\right) = \mathrm{Rem} \left(\dfrac{7^{1983}}{12}\right)

7

and

12

are co-prime.

\therefore

We can now reduce the power by applying Fermat's little theorem.

\phi (12)

12 \times \left(1 - \dfrac{1}{2}\right) \times \left(1 - \dfrac{1}{3}\right) = 4

Fermat's little theorem states

\mathrm{Rem} \left(\dfrac{7^4}{12}\right) = 1

\mathrm{Rem} \left(\dfrac{7^{1983}}{12}\right) =

\mathrm{Rem} \left(\dfrac{(7^4)^{495} \times 7^3}{12}\right) =

\mathrm{Rem} \left(\dfrac{1^{495} \times 343}{12}\right) = 7

Alternatively

When the base and the divisor are co-prime, you can directly apply the following to improve your speed:

1) Exponent Rule: In the base, write the remainder when base is divided by the divisor
2) Fermat's Theorem: In the power, write the remainder when the power is divided by the

\phi

(divisor).

\mathrm{Rem} \left(\dfrac{79}{12}\right) = 7

;

\mathrm{Rem} \left(\dfrac{1983}{4}\right) = 3

\therefore

\mathrm{Rem} \left(\dfrac{(79)^{1983}}{12}\right) = \mathrm{Rem} \left(\dfrac{7^3}{12}\right) = 7

Answer:

7

Example 25

What is the remainder when

43^{47}

is divided by

23

Solution

43

and

23

are co-prime.

\phi (23) =

23 \times \left(1 - \dfrac{1}{23}\right) = 22

Applying Fermat's little theorem,

we get

\mathrm{Rem} \left(\dfrac{(43)^{22}}{23}\right) = 1

\mathrm{Rem} \left(\dfrac{(43)^{47}}{23}\right) = \mathrm{Rem} \left(\dfrac{((43)^{47})^2 \times (43)^3}{23}\right) = \mathrm{Rem} \left(\dfrac{(43)^3}{23}\right)

\mathrm{Rem} \left(\dfrac{(43 - 3)^3}{23}\right) = \mathrm{Rem} \left(\dfrac{(- 3)^3}{23}\right) = \mathrm{Rem} \left(\dfrac{- 27}{23}\right)

The remainder is unchanged when a multiple of the divisor is added to the dividend.

\therefore

\mathrm{Rem} \left(\dfrac{(- 27 + 46)}{23}\right) = 19

Answer:

19

5. Chinese Remainder

If the numerator and denominator are not co-prime, then Fermat's Little Theorem cannot be directly applied.

The following steps are then followed,
1) The divisor is prime factorised

2

) The remainders when the number is divided by each of the prime factors (with their respective powers) is found.

3

) The number is expressed in

dq + r

for the different divisors to find the common remainder.

Example 26

What is the remainder when

250^{340}

is divided by

44

Solution

44 = 2^2 \times 11

2^2

perfectly divides

250^{340}

⇒

\mathrm{Rem} \left(\dfrac{(250)^{340}}{2^2}\right) = 0

\therefore

Where

a

is an integer,

\bm{250^{340} = 4a + 0}

\longrightarrow

(

1

)

\mathrm{Rem} \left(\dfrac{(250)^{340}}{11}\right) = \mathrm{Rem} \left(\dfrac{(242 + 8)^{340}}{11}\right) = \mathrm{Rem} \left(\dfrac{(8)^{340}}{11}\right)

\phi(11) = 11 \times \left(1 - \dfrac{1}{11}\right) = 10

\therefore

\mathrm{Rem} \left(\dfrac{8^{340}}{11}\right) = \mathrm{Rem} \left(\dfrac{(8^{10})^{34}}{11}\right) = 1

\therefore

Where

b

is an integer,

\bm{250^{340} = 11b + 1}

\longrightarrow

(

2

)

Equating (

1

) and (

2

4a + 0 = 11b + 1

⇒

a = \dfrac{11b + 1}{4}

$b$ = $1$ satisfies. Substituting in (

2

),

Remainder =

11 \times 1 + 1 = 12

Answer:

12

Want to read the full content

Unlock this content & enjoy all the features of the platform

Subscribe Now