There must have been a lot of times that you would have seen aspirants throwing across terms involving a certain Euler and a certain Fermat. Many fall into the trap of having a one-size-fits-all approach when it comes to simple remainder questions and end up getting an incorrect answer when it matters the most. In this series, I will be covering all the basic concepts plus the different types of questions that can appear in CAT from this topic.
The first article will deal with the concept of Euler’s number or Euler’s totient function which will be followed by a session on finding remainders when the base of the numerator and denominator are co-prime using Euler theorem and when they are not co-prime which will be followed by a special form of question that might come and I will end the topic with the much popular Chinese remainder theorem. All these articles are focused on covering basics and should be useful even for someone who has just picked up the topic.
Euler’s totient function/Euler’s number
Whenever you come across a natural number, there will be quite a few interesting facts that you observe about it. One such fact involves the number of co-prime numbers that are present in the set of natural numbers less than the original number.
Two numbers are said to be co-prime if they do not share any other factor except 1.
Corollary 1: Any number when paired with 1 will form a co-prime pair.
For example: If you have a number, say 4. The natural numbers less than 4 are 1, 2 and 3. Now, we will try to see how many among these numbers are co-prime with 4.
1 and 4 form a co-prime pair
2 and 4 are not co-prime as they share a common factor 2
3 and 4 form a co-prime pair
So, we have 2 co-primes when the original number is 4.
For another number, say 5, the co-prime numbers would be 1, 2, 3, 4 and so, 4 co-primes.
While for smaller numbers, it is possible to do this the manual way, for larger numbers, it becomes practically impossible to find it out using this method.
But, there is a formula that we can use to find the number of natural numbers that are lesser than a particular number and are co-prime to it. Commonly known as the Euler number and technically the Euler totient function, the number of co-prime numbers for a number N = am * bn * cp … where, a, b, c are the basic prime factors of N is given by:
Remember that E is not dependent on the power to which individual prime factors are raised to.
Let’s take an example to study the same:
For a small number say 20, which can be written in its basic form as 22 * 5, we can find E as follows:
On observation we find that {1, 3, 7, 9, 11, 13, 17, 19} are less than 20 and are co-prime to it ie. 8 elements.
Now, you can do this for larger numbers too easily:
Find the Euler number for 540.
540 = 22 * 33 * 5
Corollary 2: Euler number of any prime number is always one less than that prime number. For example: If we have to find E for say, 97 we will simply write it as 97-1 = 96. This is quite evident from the very definition of a prime number which rules out any common factors except 1.
Corollary 3: Another important observation that can be found is that, for two co-prime numbers a and b, E(a)*E(b) = E(a*b).
Example: For a = 12, E(a) = 4, for b = 35, E(b) = 24. So, E(a)*E(b) will be 4*24 = 96. While E(a*b) will be E(12*35) = E(420) = 96
Corollary 4: If two numbers are not co-prime, E(a) * E(b) * HCF (a, b) = E(a*b) * E(HCF (a, b))
What is the use of this concept?
a) Direct word-based questions can appear which use the basic of this concept. How many natural numbers are present such that they do not share a factor other than 1 with 549 and are less than it? OR How many numbers less than ‘n’ (1, 2, 3, 4 … n-1) are such that when the lowest form of the ratio of each individual element divided by n is calculated, you still get n as the denominator? (Essentially you have to find E here) OR questions based on direct or indirect application of either of the 4 corollaries.
b) Probably the most important and widespread use of this concept is while reducing the power of the numerator when dealing with division questions using Euler theorem which we will be covering in the part 2 of the series.
The remaining parts of the series:
