Shadock, c'est une suite finie : n,2n,3n,4n,....,mn. Il y a m termes.

autant que de multiples de m / pgcd(n, m) entre 1 et m ?

D'instinct : la réponse est PGCD(m,n).



Première démonstration (trouvée avec beaucoup d'efforts) :

Soit k le plus petit entier strictement positif tel que kn est divisible par m. kn, plus petit multiple de n divisible par m... kn=PPCM(m,n).

k est forcément un diviseur de m : seuls les jkn, avec j entier quelconque, sont divisibles par m, donc il existe un J tel que Jk=m.

Dans la suite susmentionnée, il y a bien entendu m/k multiples de m, soit J multiples de m. J=m/k=mn/kn=mn/PPCM(m,n)=PGCD(m,n).



Deuxième démonstration (for fun) :

Construisons un carré de côté mn. A l'intérieur, on trace une ligne verticale toutes les n unités de longueur, et une ligne horizontale toutes les m unités de longueur, scindant ainsi ce carré en mn rectangles de largeur n et de longueur m.

La question "combien y a-t-il de multiples de m dans la suite des kn (k allant de 1 a m) ?" se ramène a la question "combien de fois une des diagonales du carré décrit ci-dessus passe-t-elle par un sommet d'un des petits rectangles (en ne comptant pas le point de départ de la diagonale, mais en comptant celui d'arrivée) ?"

On divise toutes les largeurs par n et toutes les hauteurs par m ; cela devient "dans un rectangle de dimensions entières m et n, par combien de points aux coordonnées entières une diagonale passe-t-elle (en omettant un des deux sommets du rectangle) ?" et j'ai déja du passer par cette question ici.

Bonjour,
Si m=n, alors la réponse triviale est N=m=n.
Si m et n sont premiers entre eux, alors la réponse triviale est N=1.
Si m et n ne sont pas premiers entre eux, alors la réponse est leur PGCD.
On voit que dans tous les cas (que m et n soient ou ne soient pas premiers entre eux, ou même égaux), la réponse est PGCD(m;n).
Bonne journée.
Frank

Merci à tous les participants.