# Fermat Theorem : Application in finding remainders

Fermat Theorem : Application in finding remainders
5 (100%) 7 votes

Fermat theorem states that for any two positive natural numbers N and P, if they are co-prime to each other then remainder obtained when ${N^{\phi \left( P \right)}}$is divided by P is 1, where $\phi \left( P \right)$ is the euler of P.

i.e. $\frac{{{N^{\phi \left( P \right)}}}}{P} \to R\left( 1 \right)$

Example 1:Find the remainder 25^6 when is divided by 9.

Solution:

Observe that Euler of 9, $\phi \left( 9 \right) = 6$, and 9 is co-prime to 25, hence with the direct application of Fermat theorem, the required remainder is 1.

### Extension of Fermat theorem

For any two positive natural numbers N and P, if they are co-prime to each other then remainder obtained when ${N^{M \times \phi \left( P \right)}}$is divided by P is also 1, where $\phi \left( P \right)$ is the euler of P and M is any positive integers.

Example 2: Find the remainder when ${11^{705}}$ is divided by 17.

Solution:

Observe that 11 and 17 are co-prime to each other, and Euler of 17 = 16.

Also, 705 = 44×16 +1 so we can write ${11^{44 \times 16 + 1}}$

Or $\frac{{{{11}^{705}}}}{{17}} = \frac{{{{11}^{44 \times 16 + 1}}}}{{17}} = \frac{{{{11}^{44 \times 16}} \times 11}}{{17}}$

Applying Fermat theorem, $\frac{{{{11}^{44 \times 16}}}}{{17}} \to R\left( 1 \right)$and 11 divided by 17 the remainder obtained is 11 only.

Therefore, the final remainder obtained when ${11^{705}}$ is divided by 17 is 1×11 = 11.