If \(\phi (n)\) represents number of positive integers less than \(’n’\) and co–prime to \(n\),  and a number \(‘a’\) is co prime to \(n\), then 

\({a^{\phi (n)}} \equiv 1(\bmod \,\,n)\), which means when \({a^{\phi (n)}}\)is divided by \(n\), remainder is 1. For example the number 100 has 40 co–primes which are less than 100 and 3 is one of them, hence we can conclude that \({3^{40}}\) when divided by 100, remainder will be 1.

Example 25: Find the remainder when \({11^{401}}\) is divided by 100.

Solution: First we will calculate \(\phi \left( {100} \right)\), that is equal to \(100\left( {1 - \frac{1}{2}} \right)\left( {1 - \frac{1}{5}} \right)\) =40

Now we know that 11 is one of the co–primes of 100. Hence \({11^{40}}\) when divided by 100, remainder is 1.

Now \(\frac{{{{11}^{401}}}}{{100}} = \frac{{{{({{11}^{40}})}^{10}}.11}}{{100}} = 11\)

Example 26: Find the remainder when \({11^{360}}\) is divided by 37.

Solution: First we will calculate the value of (37), that is equal to \(37\left( {1 - \frac{1}{{37}}} \right) =36\).

[Since 37 is prime, hence all the positive integers which are less than 37, will be co–prime to 37]

Now we know that 11 is one of the co–primes of 37. Hence \({11^{36}}\) when divided by 37, remainder is 1.

Now \(\frac{{{{11}^{360}}}}{{37}} = \frac{{{{({{11}^{36}})}^{10}}}}{{37}} = 1\)