Ben oui, faut bien le faire vivre un peu ce site.....
Tout le problème est de proposer des énigmes pas trop faciles, pas trop difficiles, pas trop mathématiques,....

Pour en revenir à l'énigme, oui c'est bien cela, Ebichu. Je voulais qu'on propose un truc plus court, tu n'en as pas eu besoin, malgré les grands nombres en jeu.

Et si je demandais, en généralité, le PGCD de (a*n + b) et (c*n+d), que répondrais tu ?

Et bien voila, le temps est écoulé.

J'avais promis une réponse plus simple pour la recherche du PGCD dans ce genre de figure. La voici donc :

Si P = pgcd

a * n + b = k* P
c * n + d = j * P

n = ( ( k * P ) - b ) / a = ( ( j * P ) - d ) / c

c * k * P - b * c = a * j * P - a * d
P ( c * k - a * j ) = b * c  - a * d

P existe et est max quand c * k - a * j = +- 1 , ce qui est toujours possible si a et c sont premiers entre eux. Dans ce cas P = I  b * c - a * d  I 

C'est donc tout de même plus court que l'algorithme d'Euclide.

Remarque : Si a et c ont un facteur commun, P = 1 sauf si ce facteur commun est aussi dans b et d.


Peu de participants à cette petite énigme pourtant pas bien méchante. Trop scolaire ?