Remainders of Large Numbers using Fermat’s and Euler’s Theorem

To understand the basics of calculating remainders like the sum and product of remainders, concept of negative remainders etc click here – Remainders Basics

In this post we will see how to find the remainders of large numbers using the remainder theorems – Fermat’s Little theorem and Euler’s theorem using the Euler’s Totient function.

Fermat’s Little Theorem

As per the Fermat’s little theorem, if N is a prime number & M is prime to N, then

$Remainder(\frac{M^{N-1}}{N}) = 1$

Example:
What is the remainder of 15 to the power of 26 when divided by 13.

Here, since the divisor 13 is prime number, as per the Fermat’s little theorem, we have
$Remainder(\frac{15^{12}}{13}) = 1$

Now,
$Remainder(\frac{15^{26}}{13})$ => $Remainder(\frac{(15^{12})^2\ *\ 15^2 }{13})$

15 to the power of 12 when divided by 13 leaves a remainder 1 and 15 when divided by 13 leaves a remainder 2. Hence,

$Remainder(\frac{(15^{12})^2\ *\ 15^2 }{13})$ => $Remainder(\frac{(1)^2\ *\ 2^2 }{13})$ => 4

Therefore, $Remainder(\frac{15^{12}}{13}) = 4$

So Fermat’s theorem will be handy in calculating remainders when the divisor is a prime number.

Euler’s Theorem

In order to understand the Euler’s theorem, we must first understand the Euler’s Totient Function.

Euler’s Totient Function

The number of positive integers less than or equal to n and prime to n is given by

φ(n) = $n(1-\frac{1}{a})(1-\frac{1}{b})(1-\frac{1}{c})$

where,
φ(n) is the Euler’s Totient function,
n is a natural number such that n = {$a^p * b^q * c^r$…}. Here a,b,c are prime factors of n and p, q, r are positive integers.

Example :
1. Find the Euler’s totient function of 33.
33 in terms of terms of its prime factors is written as 33 = 11 * 3.
The Euler’s totient function of 33 is given by
φ$(33) = 33(1 – \frac{1}{11})(1 – \frac{1}{3}) = 20$.

2. Find the Euler’s totient function of 9.
9 in terms of terms of its prime factors is written as $9 = {3^2}$.
The Euler’s totient function of 9 is given by
φ$(9) = 9(1 – \frac{1}{3}) = 6$.

Now that we know the Euler’s totient function, lets understand the Euler’s theorem.

Euler’s Theorem

Consider a number in the form $\frac{m^x}{n}$. As per the Euler’s theorem,

If n is relatively prime to m then ${m^{\Phi(n)}}$ divided by n gives 1 as the remainder. i.e

$Remainder(\frac{m^{\Phi(n)}}{n}) = 1$.

Approach to problems based on Euler’s Theorem
If the remainder of the number in the form $\frac{m^x}{n}$ has to be calculated, then

1. Identify if m & n are co-primes.
2. Calculate $\Phi(n)$.
3. Divide the power of m by $\Phi(n)$, The remainder of which is the new power of m. Lets call this new power of m as y.
4. $Remainder(\frac{m^x}{n})$ = $Remainder(\frac{m^y}{n})$

Problem:

1. What is the remainder when 2 to the power of 63 is divided by 99?
Here, m = 2 and n = 99 are co-prime to each other. Hence we can apply Euler’s theorem.

-> Calculate the Euler’s totient function of 99.
$99 = 11 * {3^2}$
$=> \Phi(99) = 99(1 – \frac{1}{11})(1 – \frac{1}{3}) => 60$

-> Divide the exponent x by \Phi(n) to find remainder y.
$ y = Remainder(\frac{63}{\Phi(99)}) => 3 $

-> Find the remainder of m to the power of y when divided by n.
$ Remainder(\frac{2^3}{99}) = 8 $

Therefore, $ Remainder(\frac{2^{63}}{99}) = 8 $

In the previous problem, m and n were co-primes, now what if m and n are not co-primes?
Consider this problem

2. What is the remainder when 3 raised to 45 is divided by 45?
Here, m = 3 and n = 45 are not co-primes.
To solve this kind of a problem, we will first separate the common factor from the numerator and the denominator. i.e

$\frac{3^{45}}{45} = \frac{3^2*3^{43}}{9*5}$

-> We will use the common factor 9 later.
-> Consider $\frac{3^{43}}{5}$ both 3 and 5 are co-primes. So, we can calculate the remainder of $\frac{3^{43}}{5}$ using the Euler’s theorem.

Lets first calculate the remainder when the exponent 43 is divided by the Euler’s totient function of 5.
$ Remainder(\frac{43}{\Phi(5)}) = 3 $

Now, calculate the remainder of $\frac{3^{43}}{5}$

$ Remainder(\frac{3^{43}}{5}) => Remainder(\frac{3^{3}}{5}) => 2 $

-> Multiplying the common factor 9 with the remainder of $\frac{3^{43}}{5}$ gives us the actual remainder of $\frac{3^{45}}{45}$

$ Remainder(\frac{3^{43}}{45}) => 9 * 2 = 18 $

Math Tricks Workout

Please do try our android app – Math Tricks Workout. The app is developed to improve mental arithmetic using a series of left to right fast math workouts.

Scan the QR code below or click on it for more details.
qr code

Comments

  • Sushant
    Reply

    What will be the remainder when (4)^98 divided by 25???

    • Sujith Patnaik

      Hi Sushant,

      A very good problem. I will try to answer this problem using an approach that will make use of Euler’s theorem and the remainders of product (Remainder of product = Product of the remainders). This approach might be helpful in fine tuning your basics on finding remainders.

      Since 4 and 25 are co primes, we can apply Euler’s theorem.
      Euler totient function of 25 is 20. Hence, according to Euler’s theorem $4^{20}$ by 25 gives 1 as remainder.

      If $4^{20}$ by 25 gives 1 as remainder, then $4^{100}$ by 25 also gives 1 as the remainder.

      Hence, remainder of $\frac{4^{100}}{25}$ = 1

      Now,
      Remainder of $\frac{4^{98} \text{ x } 4^2}{25}$ = Remainder of $\frac{4^{100}}{25}$

      => Remainder of $\frac{4^{98}}{25}$ x Remainder of $\frac{4^{2}}{25}$ = 1

      Here, Remainder of $\frac{4^{98}}{25}$ is a value between 0 and 24, let this be $x$ and Remainder of $\frac{4^{2}}{25}$ is 16.

      Hence, Remainder of $\frac{x \text{ x } 16}{25}$ = 1

      By evaluating, you get $x$ to be 11

    • Vandana

      Hi Sujith, How did we get 11 in the last step?

    • Sujith Patnaik

      By substituting the values from 0 to 24 (since remainder of $\frac{x \text{ x } 16}{25}$ will be always between 0 and 24 ) to $x$ and checking by trial and error.

  • Sushant
    Reply

    Thank you sir….great work….

  • Sushant
    Reply

    I was having confusion with another problem {(4)^456}÷6 . I m getting 4 as remainder could u pls tell I m right or not

    • Sujith Patnaik

      You are right Sushant 🙂
      In case you are still confused:
      Here, m = 4 and n = 6 are not co-primes.
      Hence, separate the common factor from the numerator and the denominator. i.e

      $\frac{4^{456}}{6} = \frac{2^{912}}{6} = \frac{2*2^{911}}{2*3}$

      -> We will use the common factor 2 later.
      -> Consider $\frac{2^{911}}{3}$ both 2 and 3 are co-primes. So, we can calculate the remainder of $\frac{2^{911}}{3}$ using the Euler’s theorem. (Note: you can also apply the concept of negative remainders at this point: remainder of 2 by 3 is -1, & $(-1)^{911}=-1$)

      Lets first calculate the remainder when the exponent 911 is divided by the Euler’s totient function of 3.
      $ Remainder(\frac{911}{\Phi(3)}) =Remainder(\frac{911}{2}) = 1$

      Now, calculate the remainder of $\frac{2^{911}}{3}$

      $ Remainder(\frac{2^{911}}{3}) => Remainder(\frac{2^{1}}{3}) => 2 $

      -> Multiplying the common factor 2 with the remainder of $\frac{2^{911}}{3}$ gives us the actual remainder of $\frac{2^{912}}{6}$ or $\frac{4^{456}}{6}$

      $ Remainder(\frac{4^{456}}{6}) => 2 * 2 = 4 $

  • Vandana
    Reply

    Thank you was really helpful.

  • jafar
    Reply

    4^98 mod 25 means 2^196 mod 25
    25=5^2 so phi(25)=25*(1-1/5)=20
    so (2^20)^9mod25=1 (i.e. 2^180 mod 25 =1)
    remaining 2^16 mod 25= 11
    so remainder of 2^196mod25 is 11.

  • Mihir Chhatbar
    Reply

    can you please explain how to find remained of the following:
    4831 x 4833 x 4835 when divided by 24?

    • Sujith Patnaik

      Hi Mihir,
      You can apply the concept of remainder of product, according to which the remainder of product is the product of remainders. {Check this post for more info – Remainders Basics}

      In 4831 x 4833 x 4835 when divided by 24,
      First consider 4831. If you look at this number, you will notice that it is easily divisible by 24. {By easily i mean you can mentally divide the number}. Thus if you calculate correctly the remainder you get will be 7.
      Next, since 4833 is 2 more than 4831, it gives remainder 9 when divided by 24.
      Similarly 4835 gives 11.

      Now Remainder of $\frac{\text{4831 x 4833 x 4835}}{24}$ = Remainder of $\frac{\text{7 x 9 x 11}}{24}$ = 21.

  • Mihir Chhatbar
    Reply

    remainder**

  • Abhishek
    Reply

    How to find the remainder of y when divided by 90, where 𝑦= (〖21〗^3+〖22〗^3+〖23〗^3+〖24〗^3)/90.

    • Sujith Patnaik

      Abhishek,

      (a$^n$ + b$^n$ + c$^n$ + …) is divisible by (a + b + c + …), if a + b + c +… are in Arithmetic progression and n is odd.

      So, 21$^3$ + 22$^3$ + 23$^3$ + 24$^3$ is divisible by 21+22+23+24 = 90. Hence remainder of (21$^3$ + 22$^3$ + 23$^3$ + 24$^3$)/90 = 0;

  • Abhishek
    Reply

    What is the remainder when 479547954795… upto 600 digits is divided by 101?

  • Sushant
    Reply

    Hello sir….could u pls help me to find remainder of (22)^7/123???

    • Sujith Patnaik

      Hi Sushant,
      Since the exponent is small, i would go with the basic approach of calculating remainders.

      $\frac{22^7}{123}$ =>$\frac{(22^2)^3\text{ x }22}{123}$

      => $\frac{(484)^3\text{ x }22}{123}$

      => $\frac{(-8)^3\text{ x }22}{123}$ [Since, 123×4 = 492 and using the concept of negative remainders 484 by 123 gives -8 as the remainder]

      => $\frac{(-512)\text{ x }22}{123}$

      => $\frac{(-20)\text{ x }22}{123}$ [Since, 512 by 123 gives 20 as remainder, -512 by 123 gives -20 as remainder]

      => $\frac{(-440)}{123}$ => Gives remainder -71

      The negative remainder -71 is converted to positive by adding it with 123 => 123 – 71 = 52

      Hence remainder of $\frac{22^7}{123}$ = 52

  • Sushant
    Reply

    Thanku sir for ur help…
    Bs apne ek choti si galti kr di sol main…123*4=492…apne galati se 192 likh diya….

    • Sujith Patnaik

      Oops!!! Thanks Sushant… I updated it 🙂

  • Abhishek
    Reply

    In the question: 4^(98)/ 25,
    Why is remainder of 4^(98)/ 25,a value between 0 and 24?

    • Sujith Patnaik

      Abhishek,

      The remainder of any number when divided by n, will always be a value between 0 and n.

      For example, the remainder of a number N when divided by 3 will be 0 or 1 or 2.

      Similarly, remainder of a number N by 25 will be a value between 0 and 24.

    • Abhishek

      I understood now. Thank you, Sir. 🙂

  • mark
    Reply

    what will be the remainder when 19^92 divided by 92

    • Sujith Patnaik

      Hi,

      Since 19 and 92 are co-primes, we can apply Euler’s theorem.

      Euler’s totient function of 92 is 44. Hence by Euler’s theorem ${19}^{44}$ by 92 gives 1 as remainder.

      Now since ${19}^{44}$ by 92 gives 1 as remainder, ${19}^{88}$ by 92 gives remainder 1.

      Hence remainder of $\frac{{19}^{92}}{92}$

      = Remainder of $\frac{{19}^{88}\text{ x }{19}^4}{92}$

      = Remainder of $\frac{{19}^{88}}{92}$ x Remainder of $\frac{{19}^{4}}{92}$

      = 1 x Remainder of $\frac{{19}^{4}}{92}$

      Now ${19}^2$ by 92 gives -7 as remainder. Hence ${19}^4$ by 92 gives remainder 49.

      Hence remainder of $\frac{{19}^{92}}{92}$ = 1 x Remainder of $\frac{{19}^{4}}{92}$ = 1×49 = 49

  • Antonio
    Reply

    Hi,
    I need calculate the remainder of (2^((n-1)/2))/n. Can you help mi?

    I’m spanis

  • Antonio
    Reply

    n is in form 4m+3 . Thanks

49 + = 50