From: Richard Carr <carr@math.columbia.edu>
Subject: Re: Relatively prime numbers
Date: Sun, 9 Jan 2000 18:12:20 -0500
Newsgroups: sci.math
Summary: [missing]

On Sun, 9 Jan 2000, Matthew Burgess wrote:

:Date: Sun, 09 Jan 2000 17:57:33 GMT
:From: Matthew Burgess <mattb@nospam.umit.maine.edu>
:Newsgroups: sci.math
:Subject: Relatively prime numbers
:
:Hi all,
:
:I was wondering if there is a formula to determine the number of
:relatively prime positive integers less than a given number n.  For
:instance f(7) = 6 {1,2,3,4,5,6} and f(12) = 4  {1,5,7,11}. By
:"relatively prime" I mean all numbers are relatively prime to n.

Yes, there is. You can use the function phi(n) which is multiplicative (in
the number theory sense- i.e. phi(mn)=phi(m)*phi(n) if m and n are
relatively prime). phi(p^k) is easy to compute for a prime
p. phi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1), since it is justs the cardinality of
the set {1,2,...,p^k}\{p,2p,3p,...,p^{k-1}p}.
For the multiplicative thing to work properly you need to define phi(1)=1,
which isn't strictly the case though.
To show that the function is multiplicative, you can use the Chinese
Remainder theorem, observing that (Z_{mn})^* is isomorphic to
(Z_m)^*x(Z_n)^* if (m,n)=1, where (Z_r)^* is the multiplicative group of
Z_r. phi(n) is the order of (Z_n)^*. (One can observe that, indeed,
(Z_1)^*=1 too.)
Given ([a],[b]) in (Z_m)^*x(Z_n)^*, use the fact that (m,n)=1. Thus there
are integers r,s such that rm+sn=1. Then let c=r(b-a) and d=s(a-b). Thus
cm-dn=b-a and cm+a=dn+b=t, say. Then t is an integer which is congruent to
a modulo m and to b modulo n. Let ([a],[b])->[t] in (Z_{mn})^*. You need
to check that this map is well-defined. Suppose that for some integers r
and s, rm+a=sn+b=u. Now u-t=(r-c)m=(s-d)n and so u is congruent to t
modulo mn. Further [t] is a unit in Z_{mn}. If not, then some prime factor 
of mn divides t, say p. If p|m then [a] isn't in (Z_m)^*. If not, [b]
isn't in (Z_n)^*.
Next, if ([a],[b]) and ([e],[f]) are both mapped to [t], then there are
u,v,w and x with t=um+a=vn+b=wm+e=xn+f. Hence a-e=(w-u)m and b-f=(x-v)n,
so that a is congruent to e modulo m and b is congruent to f modulo n.
Finally, if c is a unit modulo mn, then there are d and e with
dmn+ce=1. Thus (dn)m+ce=1 and (dm)n+ce=1 so that c is a unit modulo both m
and n. Then ([c],[c]) maps to [c], since 0m+c=0n+c=c.
Thus the map is a bijection. You can check it's an isomorphism if you want
but for the purposes here it only matters that they are the same size.

:
:Thanks in advance,
:Matt
: