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 ...$

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$

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.