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