Bodhee Prep-Online CAT Coaching | Online CAT Preparation | CAT Online Courses

Get 10% OFF on CAT 24 Course. Code: BODHEE10. valid till 3rd Dec Enroll Now
| Best Online CAT PreparationFor Enquiry CALL @ +91-95189-40261

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

### 4 Responses

1. Himanshu says:

Very well explained

1. bodheeprep says:

Thanks for your appreciation, Himanshu:)

2. noahvishnu.2021 says:

Better notes than many other portals

1. bodheeprep says:

Thanks Vishnu for this appreciation. Please recommend Bodhee Prep to others as well:)

### CAT success stories of our 2022, 2021 and 2020 batches

The stories that we are sharing here are some of those students whom we mentored right from the start of their preparation. Having mentored them,

### [PDF] CAT 2021 Question Paper (slot 1, 2 & 3) with Solutions

CAT 2021 question paper PDF is available on this page. The page has the CAT 2021 question paper PDFs of all the three slots. There

### All About CAT Mock Test Series

Table of Content for CAT Mock Tests Ideal number of CAT Mock Test Series How many CAT mocks should one write What is the right

### [PDF] CAT 2020 Question Paper (slot 1,2 &3) with Solution

CAT 2020 question paper threw a number of surprises. Not only was there a change in exam pattern but also the difficulty level of almost

### CAT 2020 Analysis : Slot (1 2 and 3) – cutoffs

Much of CAT 2020 turned out to be as expected, both in terms of pattern and difficulty. Following the announcement of the change in pattern,

### BIG change in CAT 2020 Paper Pattern

Announced changes in CAT 2020 Pattern As we march towards the end of the year 2020, there is another unexpected turn in the sorry saga

#### CAT 2023 Mock Test Series

• 400+ Topic Tests
• 45 Sectional tests
• 20 Mock Tests (Video Solutions)
• Only at INR 2499

20% Discount Code: GET20

FREE CAT Prep Whatsapp Group

CAT 2023 Online Course at affordable price