Four Properties of the Euler Phi Function
Brendan O'Sullivan
using the word phi instead of the standard notation, so forgive me in
advance.
(i) Prove that the Euler phi function is multiplicative:
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?
(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.
I think the multiplicative nature makes the m and n parts doable, what
happens with d/phi(d)?
(iii) For any positive integers m and n
prove phi(m).phi(n)= phi(gcd(m,n)).phi(lcm(m,n))
It might be possible to use the fact that gcd(m,n)lcm(m,n) = mn? Or does
that move away from the multiplicativity?
(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
Not sure where this is going?
Daniel W. Johnson
> The following properties of the Euler 'phi' function are troubling me: I am
> using the word phi instead of the standard notation, so forgive me in
> advance.
>
> (i) Prove that the Euler phi function is multiplicative:
>
> 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?
I would use the Chinese remainder theorem.
> (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.
>
> I think the multiplicative nature makes the m and n parts doable, what
> happens with d/phi(d)?
Note that the case d=1 is equivalent to the first property.
> (iii) For any positive integers m and n
> prove phi(m).phi(n)= phi(gcd(m,n)).phi(lcm(m,n))
>
> It might be possible to use the fact that gcd(m,n)lcm(m,n) = mn? Or does
> that move away from the multiplicativity?
As a last resort, you could use the prime factorizations of m and n.
> (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
> Not sure where this is going?
If m is coprime with n, what can you say about n-m and n?
--
Daniel W. Johnson
pano...@iquest.net
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W
Brendan O'Sullivan
"Daniel W. Johnson" <pano...@iquest.net> wrote in message
news:1h0hcut.1ddyjfc1qovda8N%pano...@iquest.net...
> Brendan O'Sullivan <bo...@esatclear.ie> wrote:
>
> > The following properties of the Euler 'phi' function are troubling me: I
am
> > using the word phi instead of the standard notation, so forgive me in
> > advance.
> >
> > (i) Prove that the Euler phi function is multiplicative:
> >
> > 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?
>
> I would use the Chinese remainder theorem.
Suppose t = mn where m,n are coprime. Then the chinese remainder theorem
states that (a,t) = 1 if and only if (a,m)=1 and (a,n)=1.
Now the number of positive integers not greater than and coprime with is
precisely phi(t), but it is also the number of pairs (u,v) where u is not
greater than m and coprime with m and v not greater than n and coprime with
n, thus
phi(mn)=phi(m)phi(n)
Brendan O'Sullivan
"Brendan O'Sullivan" <bo...@esatclear.ie> wrote in message
news:dceqfq$e60$1...@reader01.news.esat.net...
>
> "Daniel W. Johnson" <pano...@iquest.net> wrote in message
> news:1h0hcut.1ddyjfc1qovda8N%pano...@iquest.net...
> > Brendan O'Sullivan <bo...@esatclear.ie> wrote:
> >
> > > The following properties of the Euler 'phi' function are troubling me:
I
> am
> > > using the word phi instead of the standard notation, so forgive me in
> > > advance.
> > >
> > > (i) Prove that the Euler phi function is multiplicative:
> > >
> > > 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?
> >
> > I would use the Chinese remainder theorem.
> Here I go:
> Suppose t = mn where m,n are coprime. Then the chinese remainder theorem
> states that (a,t) = 1 if and only if (a,m)=1 and (a,n)=1.
Brendan O'Sullivan
I
am
using the word phi instead of the standard notation, so forgive me in
advance.
(i) Prove that the Euler phi function is multiplicative:
Suppose t = mn where m,n are coprime. Then the chinese remainder theorem
states that (a,t) = 1 if and only if (a,m)=1 and (a,n)=1.
Now the number of positive integers not greater than t and coprime with t
is
precisely phi(t), but it is also the number of pairs (u,v) where u is not
greater than m and coprime with m and v not greater than n and coprime
with
n, thus
phi(mn)=phi(m)phi(n)
(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.
>
I think the multiplicative nature makes the m and n parts doable, what
happens with d/phi(d)?
Note that the case d=1 is equivalent to the first property.
If m and n are not coprime? How does the proof develop?
(iii) For any positive integers m and n
prove phi(m).phi(n)= phi(gcd(m,n)).phi(lcm(m,n))
It might be possible to use the fact that gcd(m,n)lcm(m,n) = mn? Or
does
that move away from the multiplicativity?
As a last resort, you could use the prime factorizations of m and n.
(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
Not sure where this is going?
If m is coprime with n, what can you say about n-m and n? They are also
coprime?
William Elliot
> (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.
----
Johann Wiesenbauer
> phi(nm) = phi(n) phi(m) only when n,m are coprime.
>
Actually, the meaning of "multiplicative" functions is restricted to coprime arguments, otherwise one uses the term "strongly multiplicative".
Johann
Brendan O'Sullivan
"William Elliot" <ma...@hevanet.remove.com> wrote in message
news:Pine.BSI.4.58.05...@vista.hevanet.com...
> From: Brendan O'Sullivan <bo...@esatclear.ie>
>
> > (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.
Thanks, lost there at that last bit
>