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

Primality Test – Naive Methods

forthright48 on July 8, 2015

Problem

Given a number N, determine if it is a prime.

What is a Prime Number?

A prime number is a positive number greater than 1 which has no positive divisor except for 1 and itself. For example, 2, 3, 5, 11 are prime numbers. Whereas 4, 6 are non-prime or composite numbers.

O(N) Solution

From the definition, we can easily construct a Primality Test function that can determine if a given number N is prime or not. Let us call it isPrime() function.

bool isPrime ( int n ) {
    if ( n <= 1 ) return false; // n needs to be greater than 1
    for ( int i = 2; i < n; i++ ) {
        // If it is possible to divide n with a number other than 1 and n, then it is not prime
        if ( n % i == 0 ) return false;
    }
    return true; // Otherwise, this is prime
}

The code simply iterates over all values between 2 and N-1 and checks if it can divide N. It has a complexity of O(N).

Read More