Author 
Topic: Euler phi is DFT of GCD (Read 2271 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Euler phi is DFT of GCD
« on: Jan 27^{th}, 2009, 11:53am » 
Quote Modify

I saw this cute result on the Wikipedia: (n) = _{k=1}^{n} gcd(k,n) cos(2k/n)

« Last Edit: Jan 30^{th}, 2009, 12:05pm by Eigenray » 
IP Logged 



ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Euler phi is DFT of GCD
« Reply #2 on: Jan 27^{th}, 2009, 12:56pm » 
Quote Modify

on Jan 27^{th}, 2009, 11:53am, Eigenray wrote:I saw this cute result on the Wikipedia: (n) = _{k=1}^{n} (k,n) cos(2k/n) 
 I saw this cute result elsewhere: If (n)/n = 5/3 then 5n is an odd perfect number where (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 (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

« Last Edit: Jan 30^{th}, 2009, 12:34pm by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



balakrishnan
Junior Member
Gender:
Posts: 92


Re: Euler phi is DFT of GCD
« Reply #3 on: Jan 30^{th}, 2009, 10:36am » 
Quote Modify

Here is an interesting article.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Euler phi is DFT of GCD
« Reply #4 on: Jan 30^{th}, 2009, 12:14pm » 
Quote Modify

on Jan 27^{th}, 2009, 12:19pm, towr wrote:"gcd" is missing in front of (k,n) 
 I think it's clear from the context but if you insist... on Jan 30^{th}, 2009, 10:36am, balakrishnan wrote:Here 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 all primitive mth roots unity?


IP Logged 



balakrishnan
Junior Member
Gender:
Posts: 92


Re: Euler phi is DFT of GCD
« Reply #5 on: Jan 30^{th}, 2009, 12:42pm » 
Quote Modify

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


IP Logged 



