Euler's totient function (also called the Phi function) counts the number of positive integers less than that are coprime to . That is, is the number of such that and .
Among positive numbers less than 15, eliminate multiples of 3 or 5, which are The remaining numbers are so
The goal of this section will be to prove the formula for : if are the distinct primes dividing then
The proof begins with some preliminaries about the properties of In particular, the set in the definition of consisting of positive integers which are relatively prime to has a name; it is denoted
So equals the size of
Omitting the requirement about the GCD gives the full set which has elements and can be thought of as the integers modulo The subset is precisely the set of units in . Units are the elements with multiplicative inverses. This is equivalent to being coprime to by Bezout's identity.
The totient function is multiplicative: if
The left side counts elements and the right side counts ordered pairs where and . The identity will be proved by exhibiting a bijection between the two sets.
This is essentially the Chinese remainder theorem: let be the ordered pair This is a bijection whose inverse is the map that sends an ordered pair to the unique solution mod to the congruences
Note that is relatively prime to if and only if it is relatively prime to and to So is indeed a bijection between and as desired.
As with any multiplicative function, computing can be reduced to factoring as a product of prime powers, and expressing as the product of the
Consider where is a prime. Then the positive integers in the range that are not coprime to are the multiples of in that range. There are of these, so
This leads to a formula for :
If where are primes and then
This formula can also be proved directly by a sieving argument; as in the example in the introduction, remove multiples of the but since numbers can be multiples of more than one of the primes, counting them correctly requires the principle of inclusion-exclusion.
How many positive integers less than are relatively prime to
Multiplicativity: The formula for can be used to prove the following result, which generalizes the multiplicativity of :
Factoring and RSA: Note that the formula for involves knowing the prime factorization of For numbers which are the products of two distinct primes, a sort of converse is true. That is, given and and the information that for distinct primes and it is straightforward to recover and
To see this, note that so Knowing and is enough to find and : the polynomial factors as so the two roots are easy to recover via the quadratic formula.
This is important in the discussion of the security of RSA encryption; the strength of the encryption method rests on the secrecy of and the above paragraph shows that this is equivalent to factoring which is widely believed to be a very hard problem in general.
Divisor sum: This is one of the most well-known properties of and it is discussed in the wiki on multiplicative functions: There are several ways to prove this, but an appealingly direct way proceeds as follows:
Consider the fractions There are obviously of these. Reduce them all to lowest terms. The new fractions on the list will all be of the form where and is relatively prime to And it's straightforward to see that all fractions of this type will show up somewhere on the list.
The number of such fractions with denominator is so the total number is This shows that as desired.
How many numbers in are coprime to 100?
There are coprime numbers to 100 in
So there are coprime numbers to 100 in So the answer is
Find the number of positive integers such that
These are the positive integers of the form where and So the answer is
Let be a positive integer, then find
(a) the sum of all the positive integers less than and relatively prime to ;
(b) the sum of all the positive integers less than and relatively prime to .
(a) Let be the value of and be the positive numbers less than and relatively prime to . Also note that only if . Then
(b) We have to find