L'Atelier Monstre

Théorie des nombres Algorithme d'Euclide pour le PGCD Soient deux entiers positisf \(m,n\) avec \(m > n\). Le plus grand commun diviseur \(\gcd(m,n)\) satisfait la propriété \(\gcd(m,n) = \gcd(n, m \mod n)\). Cette propriété permet de calculer le PGCD par réduction successive jusqu'à obtenir un reste nul. def pgcd(a, b): while b != 0: ...

Équations de congruence linéaires L'équation de congruence de base s'exprime sous la forme \(ax \equiv c \pmod b\). Cette expression est mathématiquement équivalente à l'existence d'un entier \(y\) tel que : \[ax + by = c\] Cette forme est une équation diophantienne linéaire, laquelle peut être résolue efficacement en utilisant l'algorithme d'E ...