wu :: forums
wu :: forums - Euler phi is DFT of GCD

Welcome, Guest. Please Login or Register.
Jun 8th, 2023, 12:03pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Grimbal, SMQ, Eigenray, william wu, towr, Icarus)
   Euler phi is DFT of GCD
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Euler phi is DFT of GCD  (Read 2261 times)
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Euler phi is DFT of GCD  
« on: Jan 27th, 2009, 11:53am »
Quote Quote Modify Modify

I saw this cute result on the Wikipedia:
 
(n) = k=1n  gcd(k,n) cos(2k/n)
« Last Edit: Jan 30th, 2009, 12:05pm by Eigenray » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Euler phi is DFT of GCD  
« Reply #1 on: Jan 27th, 2009, 12:19pm »
Quote Quote Modify Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
ThudnBlunder
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Euler phi is DFT of GCD  
« Reply #2 on: Jan 27th, 2009, 12:56pm »
Quote Quote Modify Modify

on Jan 27th, 2009, 11:53am, Eigenray wrote:
I saw this cute result on the Wikipedia:
 
(n) = k=1n (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 30th, 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: male
Posts: 92
Re: Euler phi is DFT of GCD  
« Reply #3 on: Jan 30th, 2009, 10:36am »
Quote Quote Modify Modify

Here  is an interesting article.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Euler phi is DFT of GCD  
« Reply #4 on: Jan 30th, 2009, 12:14pm »
Quote Quote Modify Modify

on Jan 27th, 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 30th, 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 m-th roots unity?
IP Logged
balakrishnan
Junior Member
**





   


Gender: male
Posts: 92
Re: Euler phi is DFT of GCD  
« Reply #5 on: Jan 30th, 2009, 12:42pm »
Quote Quote Modify Modify

Oh, sorry: I was referring to ."The Fourier Transform of Functions of the Greatest Common Divisor "  by Wolfgang Schramm
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board