mersenneforum.org A useful template for functions gcd() and totient().
 Register FAQ Search Today's Posts Mark Forums Read

 2018-02-27, 13:55 #1 JM Montolio A   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 d|n, of (f(d)*totient(n/d)) ). great! JM M Last fiddled with by CRGreathouse on 2018-02-27 at 14:36 Reason: mcd -> gcd
 2018-02-27, 15:02 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2×5×72×11 Posts If you'd stop calling your trivial observations "useful", you (and the forum) would be much better off.
 2018-02-27, 15:03 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 33×367 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.
 2018-02-27, 15:09 #4 CRGreathouse     Aug 2006 5,981 Posts Neat!
 2018-02-27, 15:26 #5 JM Montolio A   Feb 2018 5·19 Posts JA JA! But, backing to work, ¿ "the observation" is really trivial ? JM M
 2018-02-27, 16:13 #6 Nick     Dec 2012 The Netherlands 5·353 Posts It follows from proposition 11 and proposition 88/corollary 89 in our Number Theory Discussion group.
 2018-02-27, 16:23 #7 JM Montolio A   Feb 2018 5F16 Posts Oh, sorry. JM M
 2018-02-28, 11:58 #8 JM Montolio A   Feb 2018 10111112 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 --------------------------
2018-02-28, 15:23   #9
Nick

Dec 2012
The Netherlands

5·353 Posts

Quote:
 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)$$.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 5 2017-03-09 05:45 ewmayer Programming 4 2013-04-13 17:45 vector Miscellaneous Math 3 2007-11-20 18:50 toilet Math 1 2007-04-29 13:49 Dougy Miscellaneous Math 4 2006-02-22 20:59

All times are UTC. The time now is 10:32.

Fri Aug 19 10:32:59 UTC 2022 up 1 day, 8:01, 0 users, load averages: 0.72, 0.89, 1.01