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.

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


Try CAT 2020 online course for 1 day for FREE

Please provide your details to get FREE Trial of Bodhee Prep's Online CAT Course for one day. We will inform you about the trial on your whatsApp number with the activation code.

Leave a Reply

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