A useful template for functions gcd() and totient().

[JM Montolio A]

For ANY function f(),

SUM( for i on [1,n] , of f(gcd(i,n) ) ) = SUM( for all d|n, of (f(d)*totient(n/d)) ).


great!

JM M

[VBCurtis]

If you'd stop calling your trivial observations "useful", you (and the forum) would be much better off.

[Batalov]

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.

[CRGreathouse]

Neat!

[JM Montolio A]

JA JA!

But, backing to work, ¿ "the observation" is really trivial ?

JM M

[Nick]

It follows from proposition 11 and proposition 88/corollary 89 in our Number Theory Discussion group.

[JM Montolio A]

Oh, sorry.

JM M

[JM Montolio A]

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
--------------------------

[Nick]

Originally Posted by JM Montolio A

sorry, i think your work only is for f(m)=m.
I tested my "template" with many functions f().

There is no need to try different functions.
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 n-1 (or from 1 to n if you prefer it) is given by Euler's totient function \(\phi(n)\).