wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Euler phi is DFT of GCD
        
(Message started by: Eigenray on Jan 27^th, 2009, 11:53am)

Title: Euler phi is DFT of GCD
Post by Eigenray on Jan 27^th, 2009, 11:53am

I saw this cute result on the Wikipedia:

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1ⁿ gcd(k,n) cos(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifk/n)

Title: Re: Euler phi is DFT of GCD
Post by towr on Jan 27^th, 2009, 12:19pm

"gcd" is missing in front of (k,n)

Title: Re: Euler phi is DFT of GCD
Post by ThudanBlunder on Jan 27^th, 2009, 12:56pm

on 01/27/09 at 11:53:33, Eigenray wrote:

I saw this cute result on the Wikipedia:

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1ⁿ (k,n) cos(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifk/n)

I saw this cute result elsewhere:

If http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(n)/n = 5/3 then 5n is an odd perfect number
where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(n) is the sum of the divisors of the positive integer n, including 1 and n.

The idea crossed my mind to post it as a problem: Find an n such that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(n)/n = 5/3
And then, after you had duly found one, to claim my 15 minutes of fame and fortune before you wised up. LOL

Title: Re: Euler phi is DFT of GCD
Post by balakrishnan on Jan 30^th, 2009, 10:36am

Here (http://www.westga.edu/~integers/cgi-bin/get.cgi) is an interesting article.

Title: Re: Euler phi is DFT of GCD
Post by Eigenray on Jan 30^th, 2009, 12:14pm

on 01/27/09 at 12:19:37, towr wrote:

"gcd" is missing in front of (k,n)

I think it's clear from the context but if you insist...

on 01/30/09 at 10:36:53, balakrishnan wrote:

Here (http://www.westga.edu/~integers/cgi-bin/get.cgi) is an interesting article.

Unfortunately their forms use post requests so a direct link won't work. Which one are you referring to?

Anyway, the result is not hard to prove; I only put it in this section because it seemed too abstract for a riddle.

Hint: What is the sum of [hide]all primitive m-th roots unity[/hide]?

Title: Re: Euler phi is DFT of GCD
Post by balakrishnan on Jan 30^th, 2009, 12:42pm

Oh, sorry: I was referring to ."The Fourier Transform of Functions of the Greatest Common Divisor " by Wolfgang Schramm