|
|
"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 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)
> > (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
begin 666 img9.png
MB5!.1PT*&@H````-24A$4@````L````0! ,```%%E*C;````*E!,5$4```"9
MF9EW=W=5557N[NXS,S/,S,P1$1&JJJJ(B(C____=W=TB(B*[N[LZ\.96````
M6$E$051XG#6*H1& ,!1#(SH(,U2BF(,1& D50$ #`LT$'+(3]?,+XN4E=X&P
M@@!$3/R27B1!AY&,,-AF93$V(J&#>NN/D?U?+[^B:P^NN76=ERMJ?-7<8@%6
3%CQ&,1_](0````!)14Y$KD)@@@``
`
end
begin 666 img10.png
MB5!.1PT*&@H````-24A$4@````L````0! ,```%%E*C;````*E!,5$4```"9
MF9EW=W=5557N[NXS,S/,S,P1$1&JJJJ(B(C____=W=TB(B*[N[LZ\.96````
M6$E$051XG#6*H1& ,!1#(SH(,U2BF(,1& D50$ #`LT$'+(3]?,+XN4E=X&P
M@@!$3/R27B1!AY&,,-AF93$V(J&#>NN/D?U?+[^B:P^NN76=ERMJ?-7<8@%6
3%CQ&,1_](0````!)14Y$KD)@@@``
`
end
|
|