document.write (document.title)

 Math Help > Number Theory > Factors, Coprimes, and Totient Function

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.

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.

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, σ0(n), sometimes called τ(n), tau(n), is the number of factors of n.

. . . . . .

Related Pages in this website

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 A4+B4=C2, which means Fermat's last theorem is true

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