Formule peu utilisée pour le PGCD.

[M.Floquet]

Bonsoir, voici l'énoncé, j'étais vraiment surpris par cette formule.

Il faut montrer que , où représente la partie entière.

Bonne chance

[Ben314]

Salut,
On en avait déjà parlé il y a de cela quelque temps (donc si les nouveaux veulent chercher....)

Je m'était d'ailleurs (comme d'habitude...) un peu énervé vu que celui qui avait parlé de cette formule l'avait présenté comme un résultat "récent" (théorème de Polezzi, 1997) alors ça doit être connu depuis la nuit des temps (vu la simplicité de la preuve) et que le raisonnement sous-jacent apparait clairement dans de multiples preuves de la loi de réciprocité quadratique (dont la 3em de Gauss vers 1820).

Je préciserais pour ceux qui veulent chercher qu'il ne faut pas chercher midi à 14h : c'est archi simple, très court, quasi sans calculs et ca ne demande que peu de connaissances. Le tout c'est de "voir" le truc comme il faut...

[nodgim]

Bon je vois à peu près le truc.
Aligner n marques espacées de m, et en dessous m marques espacées de n.
Une partie entière de k*m/n, c'est compter le nombre de marques n visibles à gauche de k*m. Vu qu'on fait ça pour tout k jusqu'à m-1, on est pas loin de la moitié du produit n*m. Vu que si on le fait de la droite vers la gauche, ou de la gauche vers la droite , c'est pareil si on compte les marques à droite au lieu des marques à gauche. Le problème est que :
-on se retrouve à compter 2 fois les coïncidences, qui correspondent au PGCD.
-on ne compte pas les extrémités, puisqu'on ne compte que jusqu'à m-1 (ou n-1).
De tout ça, on en tire l'égalité annoncée.

[Ben314]

Ca marche aussi comme ça.
Sinon, la preuve classique, ça consiste à regarder les points à coordonnées entières du rectangle [1,n-1]x[1,m-1] et à compter ceux qui sont en dessous au sens large de la droite .
Il y en a évidement et, par symétrie, il y en a autant au dessus au sens large de la droite.
Donc est égal au nombre de points du rectangle plus le nombre de points situés sur la droite vu que ces derniers ont été compté deux fois.
Or, si d=pgcd(m,n), et si on a :
est sur la droite divise (Lemme de Gauss)
Donc

Mais, perso, ça me semble quand même d'un intérêt douteux vu que tant qu'à faire de calculer les différents avec , autant écrire directement que .

[zygomatique]

salut

je cherchais ... je cherchais ... mais ne voyais rien ...

merci à vous deux ...

effectivement il me semble avoir déjà vu le dernier résultat (éventuellement sous une forme différente dans la question mais ça revient au même)

merci

[Dacu]

Bonsoir, voici l'énoncé, j'étais vraiment surpris par cette formule.

Il faut montrer que , où représente la partie entière.

Bonne chance

Bonjour,

Peut être ?Quel genre de nombres peut être et ?

Cordialement!

[nodgim]

L'intérêt éventuel d'une telle formule n'est pas la recherche du PGCD, qu'on sait calculer facilement par ailleurs, mais l'expression de la somme des parties entières des divisions de i*m par n.