|
|
From: Brendan O'Sullivan <bos4@xxxxxxxxxxxx>
> (i) Prove that the Euler phi function is multiplicative:
It's multiplicative only for coprime integers.
phi(nm) = phi(n) phi(m) only when n,m are coprime.
> This isn't too bad, I think it is best done with the principle of
> inclusion exclusion. Although someone might have a method I have not
> considered?
That is a direct result of the isomorphisms in the theorem
(m,n) = 1 ==> Z_mn = Z_m x Z_n, Z_mn^* = Z_m^* x Z_n^*
Let f be the first isomorphism and show that the same f
restricted to the multiplicative groups is an isomorphism.
Yes, you can use the Chinese Remainder Theorem to show f is surjection.
Alternatively you can use an injection between equinumerous sets is a
surjection.
> (ii) For any positive integers m and n
> prove phi(mn)= phi(m).phi(n).(d/phi(d))
> where d is the gcd of m and n.
This may be useful
distinct primes p1,.. pk, n = p1^a1 p2^a2 ... pk^ak
==> phi(n) = n(1 - 1/p1)(1 - 1/p2)...(1 - 1/pk)
> (iii) For any positive integers m and n
> prove phi(m).phi(n)= phi(gcd(m,n)).phi(lcm(m,n))
(iii) follows from (ii) since nm = (n,m)[n,m]
phi nm = phi m * phi n * (n,m)/phi (n,m)
phi (n,m)[n,m]
= phi (n,m) * phi [n,m] * ((n,m),[n,m])/phi ((n,m),[n,m])
= phi (n,m) * phi [n,m] * (n,m)/phi (n,m)
> (iv) Take n to be a positive integer greater than 1. Prove that the
> sum of the integers m with 1<=m<=n that are coprime with n is
> (n.phi(n))/2
Do like Gauss by adding
1 2 ... n-2 n-1
n-1 n-2 .... 2 1
-------------------
n n ..... n n
To get 1 +..+ n-1 = n(n - 1)/2
Show when a + b = n and a coprime n, so is b.
Then count the number of additions, viz phi n.
----
|
|