fermat theorem

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.

Join the FB Group for FREE preparation of CAT 2019

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.

For regular updates and FREE sessions, join our following GROUPS

Share with:


CAT online Course @ 999/- only

Leave a Reply

Your email address will not be published. Required fields are marked *