Coprime Integers

An integer ( m ) is said to be a divisor of ( n ) (denoted ( m|n )) if the result of ( n/m ) is an integer. Two integers ( m ) and ( n ) are termed coprime (or relatively prime) if their greatest common divisor (gcd) equals 1, which is represented as ( (n,m) = 1 ). For instance, ( 3|6 ) and ( (5,6)=1 ), demonstrating that 3 divides 6 and the highest common factor of 5 and 6 is 1.

The Totient Function

A common inquiry in number theory is, "How many integers less than a given integer ( n ) are coprime to ( n )?" The Euler Totient function, often denoted as ( phi(n) ), counts the number of natural numbers less than ( n ) that are coprime to it.

For example, ( phi(6) = 2 ) because the only numbers less than 6 that are coprime to it are 1 and 5. Similarly, ( phi(10) = 4 ) and ( phi(30) = 8 ).

To derive a formula for this function, we can utilize a unique approach that applies broadly in mathematics: a probabilistic method.

A Probabilistic Approach

Instead of employing traditional proof techniques like induction or direct proof, let's consider a probabilistic question: "What is the likelihood that a randomly chosen integer between 1 and ( n ) is coprime to ( n )?"

According to the definition of the totient function ( phi(n) ), this probability can be expressed as ( phi(n)/n ), since there are ( phi(n) ) integers that meet the coprimality condition out of a total of ( n ).

On the other hand, we can think about prime divisors of ( n ). If a number ( m ) is coprime to ( n ), it means ( m ) is not divisible by any of the prime factors of ( n ). The probability that a prime number ( p ) divides ( m ) is ( 1/p ), and thus the probability that ( p ) does not divide ( m ) is ( 1 - 1/p ).

Consequently, the probability that none of the primes dividing ( n ) also divides ( m ) is the product of the probabilities that each prime factor of ( n ) does not divide ( m ). This yields:

By multiplying both sides by ( n ), we obtain:

This formula implies that if ( p ) is a prime number, then ( phi(p) = p(1 - 1/p) = p - 1 ). This is logical, as all integers less than a prime number are coprime to it.

Applications of the Totient Function

It is notable that ( phi ) is a multiplicative function, meaning if ( (n,m) = 1 ), then ( phi(nm) = phi(n) phi(m) ). This can be easily demonstrated with the formula we discussed earlier.

However, this multiplicative property does not hold if ( m ) and ( n ) share a prime divisor. In general, if ( (n,m) = d ), then ( phi(nm) = phi(n) phi(m) frac{d}{phi(d)} ).

A remarkable finding by Gauss is that:

Such sums over divisors are connected to the Riemann zeta function, leading to the following theorem:

When we apply this to the sum of the totient function of divisors, we derive:

Another significant result is that ( phi(n) ) represents the order of the multiplicative group of integers modulo ( n ). This becomes crucial when examining group characters and Gauss sums, eventually leading to the theory of Dirichlet L-functions, which generalizes the Riemann zeta function.

One of the most renowned applications of the Euler Totient Function is found in Euler's theorem, which extends Fermat's little theorem (not to be confused with his last theorem). It states that if ( (n,m) = 1 ), then:

When ( n ) is prime, this is referred to as Fermat's little theorem. While some may view this as abstract, it has practical significance, especially in online transactions where Euler's theorem secures data transfer by relying on the difficulty of computing ( phi(n) ) without factorizing ( n ) into its prime components, a task that remains computationally challenging.

We'll conclude this article with a quote from Carl Friedrich Gauss: "Mathematics is the queen of sciences, and number theory is the queen of mathematics."

The first video provides a foundational introduction to the Euler's Totient Function, outlining its significance and basic properties.

The second video simplifies the concept of the Euler Totient Function, making it accessible for learners at all levels.