Con riferimento intanto alla notazione X(mod m)=R, con D pari a una costante, è:

- DX(mod m)=DR(mod m), e cioè: una data uguaglianza modulare rimane tale anche se si moltiplicano entrambi i membri per una stessa quantità

- (D+X)(mod m)=(D+R)(mod m) e cioè: una data uguaglianza modulare rimane tale anche se si aggiunge ad entrambi i membri una stessa quantità.

Applicando infatti rispettivamente le proprietà sul resto di un prodotto e sul resto di una somma è:

- DX(mod m)=D(mod m) X(mod m)=D(mod m) R=DR(mod m)

- (D+X)(mod m)=D(mod m)+X(mod m)=D(mod m)+R=
(D+R)(mod m).

Consideriamo allora la funzione modulare C=EP(mod m).

Per quanto appena detto sono dunque giustificati i passaggi:

Vediamo qualche esempio.

Se consideriamo la funzione vista nel precedente paragrafo, ovvero C=4P(mod 7). Essendo 4 e 7 primi fra loro, per poterla invertire basta trovare una D tale che: 4D(mod 7)=1.

Come può essere facilmente verificato è D=2, per cui è:
P=2C(mod 7).

Consideriamo ora la funzione C=11P(mod 10800).

Essendo 11 e 10800 primi fra loro, per poterla invertire basta trovare una D tale che: 11D(mod 10800)=1.

Come può essere facilmente verificato è D=5891, per cui è:
P=5891C(mod 10800).

Nel primo caso la determinazione di D è intuitiva ed immediata.

Nel secondo caso no.

Esiste un algoritmo che consenta di giungere alla determinazione di D con tempi di elaborazione ragionevoli, anche quando il modulo ha un enorme numero di cifre ?

La risposta è "Si".

Sappiamo che D, numero naturale, deve sottostare alla condizione DE(mod m)=1.

Se indichiamo con QUOZ il risultato della divisione fra DE e m, dovendo essere: DE=m QUOZ+1, possiamo implementare un'iterazione con QUOZ che avanza a partire da 1, arrestando l'algoritmo non appena il risultato (e non il resto) della divisione: