Euler Totient or Phi Function

forthright48 on September 4, 2015

I have been meaning to write a post on Euler Phi for a while now, but I have been struggling with its proof. I heard it required the Chinese Remainder Theorem, so I have been pushing this until I covered CRT. But recently, I found that CRT is not required and it can be proved much more easily. In fact, the proof is so simple and elegant that after reading it I went ahead and played Minecraft for 5 hours to celebrate.

Problem

Given an integer $N$, how many numbers less than or equal $N$ are there such that they are coprime to $N$? A number $X$ is coprime to $N$ if $gcd(X,N)=1$.

For example, if $N = 10$, then there are $4$ numbers, namely ${1,3,7,9}$, which are coprime to $10$.

This problem can be solved using Euler Phi Function, $phi()$. Here is the definition from Wiki:

In number theory, Euler’s totient function (or Euler’s phi function), denoted as $\phi(n)$, is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. – Wiki

That’s exactly what we need to find in order to solve the problem above. So, how does Euler Phi work?

Euler Phi Function

Before we go into its proof, let us first see the end result. Here is the formula using which we can find the value of the $phi()$ function. If we are finding Euler Phi of $N = p_1^{a_1}p_2^{a_2}…p_k^{a_k}$, then:

$$\phi(n) = n \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2}… \times \frac{p_k-1}{p_k}$$

If you want you can skip the proof and just use the formula above to solve problems. That’s what I have been doing all these years. But I highly recommend that you read and try to understand the proof. It’s simple and I am sure someday the proof will help you out in an unexpected way.

Read More

Lowest Common Multiple of Two Number

forthright48 on July 7, 2015

Problem

Given two number A and B, find their lowest common multiple (LCM).

We are trying to find the LCM of A and B. What is LCM? It is the smallest positive number which is divisible by both A and B.

How do we find it?

It is based on the formula that, $LCM(A,B) \times GCD(A,B) = A \times B$. How did we get this formula? I will discuss it another day. It’s not that hard to figure out though. Anyways, from that formula we can derive $LCM(A,B) = \frac{A \times B}{GCD(A,B)}$.

For example, $LCM(6,15) = \frac {(6 \times 15 )}{GCD(6,15)}= \frac{90}{3} = 30$, $LCM(3,4)= \frac{3 \times 4 }{GCD(3,4)} = \frac{12}{1} = 12$.

Code and Pitfalls

Let us try to convert the above equation for LCM to code. If we convert exactly like the equation, code would be something like the following:

int lcm ( int a, int b ) {
    return ( a * b ) / gcd ( a, b );
}

This will work, but for some cases, this code will overflow. For example, if we try to find $LCM( 2^{20}, 2^{15})$, it is obvious that the LCM is $2^{20}$. But notice what happens when we follow the algorithm. We first try to multiply $2^{20}$ with $2^{15}$, which results in $2^{35}$ which is too big to fit in an int variable. It overflows and returns us wrong answer. But the LCM itself should fit in the “int” variable easily.

A better way to write the above code is using the following observation. $LCM(A,B) = \frac{A \times B}{GCD(A,B)} = \frac{A}{GCD(A,B)} \times B$. Since $GCD(A,B)$ divides both A and B, the fraction $\frac{A}{GCD(A,B)}$ will be an integer. This alternate equation avoids overflow since instead of multiplying A and B, it first reduces A to a smaller number and multiplies the resultant number with B. So, if $LCM(A,B)$ fits in int variable, then we will get it without the risk of intermediate products overflowing.

int lcm ( int a, int b ) {
    return ( a / gcd ( a, b ) ) * b;
}

Related Problems

  1. UVA 11388 – GCD LCM (Analysis)

Euclidean Algorithm – Greatest Common Divisor

forthright48 on July 1, 2015

Problem

Given two number A and B, find the greatest number that divides both A and B.

What we are trying to find here is the Greatest Common Divisor(GCD) of A and B. What is GCD? Like the name suggests, it the largest number ( let that be G ), that can divide both A and B. For example, $GCD(2,8) = 2$, $GCD(3,4) = 1$, $GCD(12,15) = 3$.

How do we find it?

There are many ways. One way is to list down all the divisors of A and B and then find the largest common divisors from those two lists. This is a naive method and takes too much time.

Another approach is to use Euclidean Algorithm, that works on the principle $GCD(a,b) = GCD(b,a\%b) $. Since $GCD(b,a\%b)$ is a smaller state, it is easier to find than the original. And of course, we can apply the principle to the smaller states repeatedly until the state becomes trivial. The two trivial states for GCD are $GCD(a,a) = a$ and $GCD(a,0) = a$.

Read More