(Provando a relação inversa entre f e g): Para mostrar que a função de decodificação g desfaz o trabalho da função de codificação f, devemos verificar que g(f(x)) = x, isto é,

x^(ed)(mod m) = x.

Para tal, precisamos do pequeno teorema de Fermat que nos diz o seguinte:
Pequeno Teorema de Fermat: Seja p um n ́umero primo. Então para cada inteiro positivo a,

a^(p) ≡ a(mod p).