Fermat Theorem : Application in finding remainders

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.