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