20180227, 13:55  #1 
Feb 2018
5·19 Posts 
A useful template for functions gcd() and totient().
For ANY function f(),
SUM( for i on [1,n] , of f(gcd(i,n) ) ) = SUM( for all dn, of (f(d)*totient(n/d)) ). great! JM M Last fiddled with by CRGreathouse on 20180227 at 14:36 Reason: mcd > gcd 
20180227, 15:02  #2 
"Curtis"
Feb 2005
Riverside, CA
15B4_{16} Posts 
If you'd stop calling your trivial observations "useful", you (and the forum) would be much better off.

20180227, 15:03  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23405_{8} Posts 
I am nominating this user to have his own subforum.
JM Montolio A,  you are in luck! This forum has the special area for microblogs. Your posts will be perfect there. 
20180227, 15:09  #4 
Aug 2006
5987_{10} Posts 
Neat!

20180227, 15:26  #5 
Feb 2018
5F_{16} Posts 
JA JA!
But, backing to work, ¿ "the observation" is really trivial ? JM M 
20180227, 16:13  #6 
Dec 2012
The Netherlands
5×353 Posts 
It follows from proposition 11 and proposition 88/corollary 89 in our Number Theory Discussion group.

20180227, 16:23  #7 
Feb 2018
95_{10} Posts 
Oh, sorry.
JM M 
20180228, 11:58  #8 
Feb 2018
5×19 Posts 

proposition 11 and proposition 88/corollary 89
sorry, i think your work only is for f(m)=m. I tested my "template" with many functions f().Look: f(x)  1 1 1*totient(N/d) x mcd(N,i) d*totient(N/d) N/x N/mcd(N,i) d*totient(d) #d(x) #divisores(mcd(N,i)) #divisores(d)*totient(N/d) sigma sigma(mcd(N,i)) sigma(d)*totient(N/d) Nota. #d():#nro. de divisores. sigma():Suma de divisores. Ejemplo. f(x)=x. SUM mcd(N,i). SUM (d*totient(N/d)).  n 1 s 1 t 1 n 2 s 3 t 3 n 3 s 5 t 5 n 4 s 8 t 8 n 5 s 9 t 9 n 6 s 15 t 15 n 7 s 13 t 13 n 8 s 20 t 20 n 9 s 21 t 21 n 10 s 27 t 27 Ejemplo. f(x)=(N/x). SUM (N/mcd(N,i)). SUM(d*totient(d)). n 1 s 1 t 1 n 2 s 3 t 3 n 3 s 7 t 7 n 4 s 11 t 11 n 5 s 21 t 21 n 6 s 21 t 21 n 7 s 43 t 43 n 8 s 43 t 43 n 9 s 61 t 61 n 10 s 63 t 63 Ejemplo. f(x)=#divisores(x). SUM #divisores(mcd(N,i)). SUM (#divisores(d)*totient(N/d)). Sigma(N). n 1 s 1 t 1 S 1 n 2 s 3 t 3 S 3 n 3 s 4 t 4 S 4 n 4 s 7 t 7 S 7 n 5 s 6 t 6 S 6 n 6 s 12 t 12 S 12 n 7 s 8 t 8 S 8 n 8 s 15 t 15 S 15 n 9 s 13 t 13 S 13 n 10 s 18 t 18 S 18 Ejemplo f(x)=sigma(x). SUM sigma(mcd(N,i)). SUM(sigma(d)*totient(N/d)). #divisores(N). n 1 s 1 t 1 1 n 2 s 4 t 4 2 n 3 s 6 t 6 2 n 4 s 12 t 12 3 n 5 s 10 t 10 2 n 6 s 24 t 24 4 n 7 s 14 t 14 2 n 8 s 32 t 32 4 n 9 s 27 t 27 3 n 10 s 40 t 40 4  
20180228, 15:23  #9  
Dec 2012
The Netherlands
6E5_{16} Posts 
Quote:
All you have to prove is that the number of times that the function is called with a particular parameter is the same on both sides of the equation. The two key facts are: 1. for all positive integers a,b,d,n, we have gcd(a,b)=d if and only if gcd(na,nb)=nd. 2. for any positive integer n, the number of times that gcd(i,n)=1 as i runs from 0 to n1 (or from 1 to n if you prefer it) is given by Euler's totient function \(\phi(n)\). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Consecutive numbers not coprime to Euler's totient...  carpetpool  Miscellaneous Math  5  20170309 05:45 
C++ template function syntax issues  ewmayer  Programming  4  20130413 17:45 
Finding totient using discrete logarithm  vector  Miscellaneous Math  3  20071120 18:50 
euler's totient function  toilet  Math  1  20070429 13:49 
Busted functions  Dougy  Miscellaneous Math  4  20060222 20:59 