19^{2200002}/23, Remainder = ?
The apparent complexity of this question can send a chill down the spine of students. However, one concept that makes such questions very simple and easy, is the concept of Euler number.
What is Euler's formula?
The Euler number of a number x means the number of natural numbers which are less than x and are co-prime to x. E.g. the Euler number of 6 will be 2 as the natural numbers 1 & 5 are the only two numbers which are less than 6 and are also co-prime to 6.
Mathematically, the Euler number of a number z denoted by the symbol E(z) is calculated as explained below. where P, Q and R are the different prime factors of z.
Euler's Theorem Examples
Example 1: What is the Euler number of 20?
Solution: Now, the factorization of 20 is 2, 2, 5. It has only two prime factors i.e. 2 and 5.
So, the Euler number of 20 will be Hence, there are 8 numbers less than 20, which are co-prime to it. Cross check: Numbers co-prime to 20 are 1, 3, 7, 9, 11, 13, 17 and 19, 8 in number.Application of Euler's Theorem:
Example 2: What is the remainder when 13^{18} is divided by 19?
Solution: If y^{E (z)} is divided by z, the remainder will always be 1; if y, z are co-prime In this case the Euler number of 19 is 18
(The Euler number of a prime number is always 1 less than the number). As 13 and 19 are co-prime to each other, the remainder will be 1.Example 3: What is the remainder when 13^{32} is divided by 15?
Solution: Now in this case the Euler number of 15 is 8 Now the Numerator can also be written as 13^{8×4}. Thus the remainder in this case will be 1.
Example 4: Now, let us solve the question given at the beginning of the article using the concept of Euler Number:
What is the remainder of 19^{2200002}/23?Solution: The Euler Number of the divisor i.e. 23 is 22, where 19 and 23 are co-prime.
Example 5: How many numbers from 1 to 300 can neither be divisible by 2, nor by 3 nor by 5?
Solution: The Euler number of 300 is 80, which is the answer.
Key Learning:
For any query on the topic, feel free to post in the comment section below.