L'équation ax≡b modulo n admet une solution exactement lorsque d=pgcd(a,n) divise b. Si tel est le cas, diviser a, b et n par d pour obtenir une équation à coefficient inversible. Elle possède une solution de résidu modulo n/d et d solutions distinctes modulo n. Diviser le coefficient tout en conservant le module original conduit généralement à perdre des solutions. La décomposition en facteurs premiers offre un autre outil de divisibilité : si n^k doit être divisible par un produit de puissances de premiers p^a, chaque exposant premier dans n doit être au moins ceil(a/k). Ces exposants minimaux indépendants produisent le plus petit entier admissible positif n. Pour n⁴ divisible par 2⁷·3⁵, n doit contenir 2² et 3², donc la valeur minimale est 36. Il s'agit d'une condition sur les exposants de premiers, et non d'une congruence résolue par division modulaire.
L'algorithme étendu d'Euclidean exprime gcd(a,n) sous la forme ua+vn. Lorsque le pgcd est 1, u est l'inverse de a modulo n. Choisir un représentant dans l'intervalle requis après réduction. Pour 7 et 26, 1=15·7−4·26, donc 15 est l'inverse de 7 modulo 26 ; vérifier le produit pour détecter une erreur de signe.
Pour des modules positifs m,n premiers entre eux, le théorème chinois des restes donne exactement une solution modulo mn pour chaque paire de conditions de résidu. Substituer x=r+mk dans la seconde congruence et résoudre pour k. Si les modules ne sont pas premiers entre eux, leurs valeurs de résidu doivent coïncider modulo pgcd(m,n) ; lorsqu'elles sont cohérentes, l'unicité est modulo le plus petit commun multiple, et non le produit.
Le totient d'Euler phi(n) compte les résidus premiers avec n. Pour des diviseurs premiers distincts p, phi(n)=n multiplié par le produit de (1−1/p). Le théorème d'Euler donne a^phi(n)≡1 seulement lorsque pgcd(a,n)=1. Le cas premier correspond au petit théorème de Fermat. Réduire les exposants uniquement après avoir vérifié cette condition ; un élément non-unitaire peut devenir nul sous des puissances répétées.
