Euler’s Theorem and Remainder problems.

Leonhard Euler (1707-1783)

Euler's theorem is a key concept used in solving remainder problems. In this article, we try to understand how to apply it and also elaborate on a few applications of the totient function. If you're the kind who prefers to know the underlying concept and likes to get going directly on using it to your advantage, just read the bold statements along with the example problems. If you're the kind who likes to understand the logic behind the concepts, go ahead and read all of the article :)

To understand Euler's theorem, we first need to understand the Euler's Totient function.

Euler's Totient Function
Euler’s totient function, E[n] denotes number of positive integers that are coprime to and less than a certain positive integer ‘n’.

Such a count is not hard to deduce. Let’s take a simple example and find out Euler’s totient for 100, ie number of positive integers that are less than 100 and coprime to 100

Prime divisors of 100 are 2 and 5.

From 1 to 100, no. of integers divisible by 2 and 5 are 100/2 and 100/5 respectively.

So no. of integers less than 100 and not divisible by 2 or 5 are:-

100 – 100/2 – 100/5 + 100/(2)(5)

This can be written in simpler manner as:- 100(1-1/2)(1-1/5)

In general, for a positive integer N having prime divisors p₁, p₂, ... , p_n;

E[N] = N(1-1/p₁)(1-1/p₂)....(1-1/p_n)

Euler's Theorem:

Euler's theorem states that if P and N are positive coprime integers, then: 

Rem[P^E[N]/N] = 1
where E[N] is the Euler's totient function for N.

Note: E[N] is not necessarily the smallest power of P, such that the remainder obtained is 1 when divided by N.

Example Problem: 

Find remainder for 9¹⁰¹/125.

Soln:
E[125] = 125(1-1/5) = 100

Since 9 and 125 are coprime, Rem[9¹⁰⁰/125] = 1

Thus, Rem[9¹⁰¹/125] = Rem[9/125] = 9

Application 1: 

All positive integers coprime to 2 and 5, follow a power cyclicity of 20 in terms of their last 2 digits. 

--> Last 2 digits of a^y = Last 2 digits of a^20x+y  (for ‘a’ coprime to 2 and 5)

Last 2 digits of a number P is nothing but: Rem[P/100]

We saw earlier, that E[100] = 100(1-1/2)(1-1/5) = 40

So, for any positive integer P coprime to 100, Rem [P⁴⁰/100] = 1.

We also noted that 40 cannot necessarily be termed as the lowest power of P that leaves remainder 1.So let’s see if there indeed exists a lower exponential power as per our requirements.

100 = 4 * 25

E[25] = 20 --> Denotes that Rem[P²⁰/25] = 1

E[4] = 2 --> Denotes that Rem[P²/4] = 1. So we can safely say that Rem[P²⁰/4] = 1

Applying CRT (discussed in previous post), we can conclude : Rem[P²⁰/100]= 1

So any coprime to 100 raised to power 20 will leave remainder 01 when divided by 100.

This means that all positive integers P coprime to 2 and 5, follow a power cyclicity of 20 in terms of their last 2 digits.

Example problem: 

Find last two digits of 13¹⁹⁸²

Soln:
Since 13 is coprime to 100, it follows a power cyclicity of 20 in its last 2 digits.

So last two digits of 13¹⁹⁸² = last two digits of 13² = 69

Note: Last 2 digits for all other numbers also follow cyclicity of 20, but with a condition that a^20x+y = a^y if a^y is not a¹

Application 2:

Any digit repeated E[n] times is divisible by n, if n is coprime to 2,3 and 5.

Let K = aaaaaaaaa...... repeated E[n] times

K = a/9 (10^E[n] -1)

Since n is coprime to 2 and 5, Rem[10^E[n]/n]=1

Further, since n is coprime to 3, Rem[a/9 (10^E[n] -1)] = 0
Thus, K is divisible by n.

Example problem:

Find remainder when 33333333......86 times is divided by 13

Soln:
E[13] = 13(1-1/13) = 12

So 3333.... repeated 12(7) = 84 times is divisible by 13.

Thus, the problem reduces to Rem[33/13] => 7

Feel free to put forth any doubts/clarifications in the comments section. We'll revert back pronto :)
-Angadbir

Chinese Remainder Theorem (CRT)

CRT is one of the most handy tools that one can use to crack some complex remainder problems. Let's understand how we can use it.

CRT states that if N is divided by coprimes ‘a’ and ‘b’ and that:

Rem[N/a] = x

Rem[N/b] = y

Then we can arrive at a solution for Rem[N/ab]

We will take 2 examples for understanding this concept. The first example provides an introduction to the second one, which is the kind where we would regularly need to apply CRT.

Example Problem 1: 

Find the lowest integer N which when divided by 5 leaves a remainder of 1, when divided by 7 leaves remainder 4, and when divided by 9 leaves remainder 2.

Soln:
Rem [N/5] = 1

Rem [N/7] = 4

Rem [N/9] = 2

Putting it mathematically, we are looking for N of the following form:

N = 5x + 1 = 7y + 4 = 9z + 2 

Above mathematical representation is the essence of CRT.

By solving (which is much easier by plugging in options whilst in the exam),
we get N = 11 for (x,y,z) = (2,1,1)

• There are greater values of N possible which would yield similar remainders when divided by 5, 7 and 9. 
• These can be found out by adding multiples of LCM(5,7,9) = 315 to 11. For example 11 + 315 = 326 is the next such number. 
• This fact is utilized more extensively in the next example problem, where we are given one such large number to start with but are asked (in a manner) to find out the smallest possible one.

Example Problem 2: 

Find the remainder when 3¹²⁰ is divided by 105

Soln:
105 = 3 * 5 * 7

If we can find the remainders obtained when 3¹²⁰ is divided by 3, 5 and 7 respectively, we can apply CRT to find the overall remainder as below:

Rem [3¹²⁰/3] = 0

Rem [3¹²⁰/5] = Rem[9⁶⁰/5] = Rem[-1⁶⁰/5] = 1

Rem [3¹²⁰/7] = Rem[9⁶⁰/7] = Rem[2⁶⁰/7] = Rem[8²⁰/7] = 1

• R = 3x = 5y + 1 = 7z + 1
• It is important to note that R = 3¹²⁰, for a particular set of (x,y,z). However, this set does not yield the smallest value for R. As we observed earlier, larger values for R are obtained by adding multiples of 105 to the smallest value for R.
• So in finding the smallest possible R of the above given form, we are in essence finding out R = Rem[3¹²⁰/105]

By carefully introspecting the above 3 points, it is not difficult to understand how CRT really works.

By solving, we get R = 36 for (x,y,z) = (12,7,5)

Thus, Rem[3¹²⁰/105] = 36

Note: In the above example and the definition given for CRT in the beginning of the article, the smaller individual divisors are taken to be coprimes to each other. For our objective, this is required for redundancy purposes but need not always be necessarily mandatory while solving using CRT.


-Angadbir

Divisibility Rules

This is one of the important concept of number system .Questions on remainders and factor are quite frequent in CAT these days . Lets see the divisibility rule of few numbers.

We all perhaps know what is the divisibility rule of 2,4,6,8,3,9 .But do everyone know the logic behind it ? 

First case :

Let me start from divisibility of 2
 

If last digit is divisible by 2 , then it is divisible by 2 ...

why ?
 

Last digit is nothing but divide by 10 ...10 is perfectly divisible by 2..
 

Now we can extend this  for 4 ..

lets take last digit --> divide by 10 -->  10 /4 --> Not perfectly divisible

Now move to next digit--> divide by 100

100 is perfectly divisible by 4 .. So divisibility rule of 4 is last two digits to be divisible by 4
 

Now this goes on ... jus try for various numbers like 8 ,16,32

the above logic works for factor of 10^n  like powers of 2 and 5 . Other numbers can't be treated this way

Second case
 

Lets take an example of next number .. take 3

10/3 --> not divisible

100/3 --> not divisible

1000/3 --> not divisible and it goes on ..

But in all three cases , the remainder is 1 .

If remainder is 1 , add the digits

Divisibility rule of 3 will add the digits and then check if its divisible by 3  . This is applicable for numbers which leaves remainder 1 when 10^n is divided by that number

Quick divisibility rule :

Take 33 :

100/33 leaves remainder 1 . So one can frame divisibility rule of 33 as sum of digits taken two at a time from the right hand side of number .

Eg . Is 2112 divisible by 33 ?

12 + 21 = 33 . 33/33 perfectly divisible . Yes .. isn’t that easy ?

Third case :

Lets take an example of next number .. take 7

10/7 --> not divisible but remainder is not 0 or 1 or -1

100/7 --> not divisible but remainder is not 0 or 1 or -1

1000/7 --> not divisible but remainder is -1

so every three digit we will have -1 remainder ..

if 10^3 has -1 remainder , 10^6 has 1 as remainder...

so its alternative in nature for every three digits .

Divisibility rule of 7 will difference of sum of  the digits taken at three at a time alternatively from RHS of the number  and then check if this resultant divisible by 7

say number is 123130 to check for divisibility by 7 .,..

so according to this concept we have , 130 - 123= 7 which is divisible by 7

Or let’s say 7123130 -- > (130 + 7) – 123 = 14 which is divisible by 7

The beauty of this method is it works well for big number divisors (for instance- 143) .

235378/143 .. is it divisible ?

10^3 / 143 = remainder is -1

By this method ,we can say 378 - 235 = 143.. 143 / 143 is perfectly divisible .That's all you r done

Applying this formula , we can test divisibility of 2,3,4,5,7,8,9,11,27,13,33,37,99,77,143,259(37*7)   etc ....

Just work on these lines .. You can easily find the divisibility of all above numbers

Ps : Feel free to revert me back in comments if you have any doubts .

Hello ! !

Hi Guys , 

Chillfactor, Angadbir and I will share our approaches/tricks in problem solving which we learnt over the years. 

Let us know if you guys need any specific concept to cover in this blog so that we can try our best to explain it. Please leave the comment in this post. 

As off now , we have planned to post atleast 2 posts per week . So you guys will get at least 4 posts a week . 

Let us know your feedback.

We will get started soon 

Cheers and good luck !


- Naga