|
|
"Brendan O'Sullivan" <bos4@xxxxxxxxxxxx> wrote in message
news:dceqfq$e60$1@xxxxxxxxxxxxxxxxxxxxxxxxx
>
> "Daniel W. Johnson" <panoptes@xxxxxxxxxx> wrote in message
> news:1h0hcut.1ddyjfc1qovda8N%panoptes@xxxxxxxxxxxxx
> > Brendan O'Sullivan <bos4@xxxxxxxxxxxx> 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.
> 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.
> >
> > > (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
> > panoptes@xxxxxxxxxx
> > http://members.iquest.net/~panoptes/
> > 039 53 36 N / 086 11 55 W
>
>
>
|
|