A equação ax≡b modulo n tem solução exatamente quando d=gcd(a,n) divide b. Se sim, divida a,b,n por d para obter uma equação com coeficiente invertível. Ela possui uma solução de resíduo modulo n/d e d soluções distintas modulo n. Dividir o coeficiente mas manter o módulo original geralmente perde soluções. A fatoração prima fornece outra ferramenta de divisibilidade: se n^k deve ser divisível por um produto de potências primas p^a, cada expoente primo em n deve ser pelo menos ceil(a/k). Esses expoentes mínimos produzem independentemente o menor n admissível positivo. Para n⁴ divisível por 2⁷·3⁵, n deve conter 2² e 3², logo o menor valor é 36. Esta é uma condição de expoente primo, não uma congruência resolvida por divisão modular.
O algoritmo estendido de Euclidean expressa gcd(a,n) como ua+vn. Quando o gcd é 1, u é um inverso de a modulo n. Escolha um representante no intervalo necessário após a redução. Para 7 e 26, 1=15·7−4·26, assim 15 é o inverso de 7 modulo 26; verifique o produto para capturar erros de sinal.
Para módulos positivos coprimos m,n, o teorema chinês do resto dá exatamente uma solução modulo mn para cada par de condições de resíduo. Substitua x=r+mk na segunda congruência e resolva para k. Se os módulos não forem coprimos, seus valores de resíduo devem concordar modulo gcd(m,n); quando consistente, a unicidade é modulo o mínimo múltiplo comum, não o produto.
A função totiente de Euler φ(n) conta resíduos coprimos a n. Para divisores primos distintos p, φ(n)=n vezes o produto de (1−1/p). O teorema de Euler dá a^φ(n)≡1 apenas quando gcd(a,n)=1. O caso primo é o pequeno teorema de Fermat. Reduza expoentes apenas após verificar esta condição; um não-unitário pode se tornar zero sob potências repetidas.
