The Set of Coprimes of n

The set of coprimes of n, where n is an integer larger than 1, is an infinite set, but considered modulo n, it's a set whose size is the totient of n, φ(n).  In this section, we will consider everything using modulo arithmetic.  I'll try to put a little notice to that effect at the top of every page.

Contents of this section: Factors, Coprimes, and Totient Function Sigma Function Highly Composite Numbers Totient Function Euler's Totient Theorem Sum of Totients Of Divisors of N is N

Facts about the Set of Coprimes of n

First, let's start with an example.  The set of coprimes of 12 is {1,5,7,11}.  Remember, though numbers like 13 and 145 are coprime to 12, these are equivalent to 1 (mod 12), so we don't list them separately.

The product of any two coprimes of n is another coprime of n

Proof: Suppose the opposite -- that ab shares a factor, f, with n, and f>1, even though GCD(a,n)=1 and GCD(b,n)=1.  Since f is larger than one, it has a prime factor, p.  So ab shares this prime factor, p, with n.  If p|ab then p|a or p|b, so either GCD(a,n) is not 1 or GCD(b,n) is not 1, a contradiction.

If a, b, c are coprimes of n, and b is not equal to c, then ab is not equal to ac

Proof: Suppose a is coprime to n, and b and c are two different numbers, also coprime to n, in the range [1,n-1] and ab=ac, mod n.
Then ab-ac=nk, where k is an integer.
a(b-c)=nk, and since b-c is smaller than n in absolute value, a must be larger than k in absolute value.
a and n have no factors in common, so a|k, but a can't divide k, since a is larger than k, a contradiction.

Definition of Totient Function

φ(n) is the number of positive integers not larger than n that are coprime to n.  (Coprime is defined this way: two numbers are coprime when they share no factor other than 1.)  Note that φ(1)=1, because 1 is coprime to itself.

More about the totient function.

Definition of Sigma Function

σ(n) is the sum of the factors of n.

σ_k(n) is the sum of the n's factors, each to the power k.  So, in particular, σ₀(n), sometimes called τ(n), tau(n), is the number of factors of n.

More about the sigma and tau functions.

Internet references

 . . . . . .  

Related Pages in this website

Squares.

Fermat's Theorems -- Fermat's Little Theorem, in particular.

Group - definition of a "group", which has properties closure, associativity, identity, and inverse.

The proof that primes of the form 4k+3 can be expressed as the sum of four squares uses Fermat's Little Theorem.

A bunch of Ring Theory theorems and definitions.

Proof that there is no solution to the Diophantine equation A⁴+B⁴=C², which means Fermat's last theorem is true 

The webmaster and author of this Math Help site is Graeme McRae.