Apparentemente l'esercizio richiede la risoluzione di dieci equazioni congruenziali (cinque per determinare gli inversi nella prima parte dell'esercizio e cinque esplicitamente indicate nella seconda). In realtà è richiesta la risoluzione di due sole equazioni congruenziali, una delle quali banale.

Iniziamo dalla prima. È richiesto il calcolo di a^-1 mod (pq ). Per definizione, con questa espressione ci si riferisce all'unico intero n tale che 0≤n<pq e an sia congruo a 1 modulo pq. Questo significa che [n]_pq è l'inverso di [a]_pq nell'anello Z_pq e che, inoltre, n è scelto tra tutti gli elementi della sua classe di resto come l'unico numero naturale minore del modulo pq, cioè come il resto comune a tutti gli elementi della stessa classe nella divisione per pq. Detto (ancora) diversamente, l'intero richiesto è una soluzione dell'equazione congruenziale ax ≡_pq1 che abbia la proprietà di essere compresa tra 0 e pq-1.

Deve essere chiaro allo studente perché questo intero esiste (?) e perché è unico (??).

Per trovare l'intero cercato risolviamo l'equazione congruenziale ax ≡_pq1 in modo standard, utilizzando l'algoritmo euclideo. Ricordando che pq=3131 e a=3000, i relativi calcoli si possono eseguire così:

3131 = 3000 (1)  + 131
3000 = 131  (22) + 118
131  = 118  (1)  + 13
118  = 13   (9)  + 1

oppure, più rapidamente,

3131 = 3000 (1)   + 131
3000 =  131 (23)  + (-13)
 131 = (-13)(-10) + 1

e quindi 1 = (1)131 + (10)(-13) = (10)3000 + (-229)131 = (-229)3131 + (239)3000, da cui si ottiene che 239 è una soluzione della nostra equazione congruenziale. Poiché 239 è compreso tra 0 e pq-1, concludiamo che 239 è il numero cercato:
a^-1 mod (pq ) = 239.

Non occorre ripetere il procedimento per calcolare a^-1 mod p   e  a^-1 mod q. Infatti, dal momento che 239a è congruo a 1 modulo pq, a maggior ragione esso sarà congruo a 1 modulo ciascun divisore di pq, quindi anche modulo p e modulo q. Questo vuol dire che 239 è soluzione di ax ≡_p1 e di ax ≡_q1. Per calcolare a^-1 mod p   e   a^-1 mod q serve solo "ridurre" 239 modulo p e modulo q. Abbiamo così:   a^-1 mod p = 239 mod p = 37   e    a^-1 mod q = 239 mod q = 22.

Il calcolo di c^-1 mod  q, va invece eseguito separatamente dai calcoli effettuati per a (questa è la seconda e ultima equazione congruenziale da risolvere nell'esercizio). Non abbiamo neanche bisogno dell'algoritmo euclideo: poiché c=5 e q=31=6c+1, abbiamo 6c≡_q-1, quindi -6 è una soluzione di cx≡_q1. Dunque c^-1 mod q = -6 mod q = 25.

L'inverso (in Z_q) di [ac]_q (che è il prodotto di [a]_q e [c]_q) è il prodotto degli inversi delle classi [a]_q e [c]_q, quindi (ac)^-1 mod q si può calcolare moltiplicando i risultati 22 e 25 trovati sopra (o, più facilmente, 22 e -6) e riducendo il risultato modulo q; si ottiene così (ac)^-1 mod q = 23. Se ciò risulta poco chiaro (ma non dovrebbe…) si osservi che 22·25ac≡_q(22a)(25c)≡_q1·1≡_q1.

Passiamo ora alla seconda parte dell'esercizio: le cinque equazioni congruenziali esplicitamente indicate come tali. Come accennato sopra, non abbiamo da eseguire di nuovo il procedimento standard (che utilizza l'algoritmo euclideo) per risolvere queste equazioni, abbiamo infatti già eseguito (quasi) tutti i conti necessari.

Per risolvere la prima equazione il procedimento standard richiederebbe la ricerca preliminare di una soluzione di ax≡_pq1 e la moltiplicazione di questa soluzione per b. Ma abbiamo già risolto l'equazione appena indicata per calcolare l'inverso di a modulo pq:    239=a^-1 mod pq è una soluzione di questa equazione. Dunque una soluzione dell'equazione congruenziale numero 1 è data da 239b=717. Poiché il coefficiente dell'indeterminata (a) ed il modulo (pq) dell'equazione sono coprimi, l'insieme di tutte le soluzioni dell'equazione sarà la classe di 717 modulo pq, cioè [717]_pq, ovvero, se si preferisce quest'altra notazione, 717 + pqZ.

La seconda e la terza equazione si ottengono dalla prima sostituendo il modulo pq con un suo divisore (p o q). Ogni soluzione della prima equazione è quindi soluzione di ciascuna delle altre due, queste ultime avranno però anche altre soluzioni. L'insieme di tutte le soluzioni della seconda equazione è la classe di 717 modulo p, quindi [717]_p = [10]_p; l'insieme delle soluzioni della terza equazione è invece la classe di 717 modulo q, quindi [717]_q = [4]_q.

Come si può notare, l'osservazione che le soluzioni della seconda e terza equazione si ottengono immediatamente dalla prima è analoga a quella già fatta per ottenere gli inversi di a modulo p e modulo q dall'inverso modulo pq. In effetti avremmo anche potuto seguire quast'altra strada per risolvere la seconda equazione (e similmente la terza): poiché 37 è l'inverso di a modulo p, cioè 37a≡_p1, allora 37b=111 è soluzione della seconda equazione (si noti che [111]_p = [10]_p).

Infine, la quarta e la quinta equazione non richiedono alcuno sforzo ulteriore. Dalla quarta, dividendo modulo e coefficienti per c, si ottiene la seconda, quindi la quarta equazione ha lo stesso insieme di soluzioni della seconda. Per quanto riguarda la quinta, invece, basta osservare che c è invertibile, dunque cancellabile, modulo q (che è il modulo dell'equazione; perché c è invertibile?), quindi è possibile dividere i due coefficienti ca e cb dell'equazione per c (lasciando inalterato il modulo q) ottenendo così un'equazione equivalente a quella data. ma l'equazione così ottenuta è la terza, dunque la quinta e la terza equazione hanno lo stesso insieme di soluzioni.

Considerazioni finali e osservazioni sugli errori riscontrati

Lo svolgimento riportato sopra mostra quanta differenza ci sia tra il risolvere (o cercare di risolvere) un problema in modo meccanico e acritico, utilizzando in modo cieco un algoritmo imparato senza capirlo a fondo, e risolvere lo stesso problema ragionandoci sopra e applicando in modo consapevole i metodi studiati, dopo avere capito le ragioni che li giustificano.

Molti studenti hanno affrontato l'esercizio svolgendone separatamente le varie parti, quindi moltiplicando in modo irragionevole il numero dei calcoli necessari e dunque il tempo per completare l'esercizio, e rendendo anche molto più probabile l'inciampo in qualche banale errore.

Pochissima dimestichezza con la materia ha, ad esempio, dimostrato chi ha fornito soluzioni (giuste o sbagliate che fossero, importa di meno) alle equazioni congruenziali ma non ha fornito risposte a quanto richiesto nella prima parte (gli inversi), non essendosi reso conto che calcolando le soluzioni delle equazioni stava anche calcolando le risposte alle domande precedenti.

Altrettanta poca cognizione di causa hanno dimostrato coloro che, non accorgendosi del fatto che la soluzione di tutte le equazioni si otteneva dalla soluzione della prima, hanno ripetuto più volte procedimento e calcoli analoghi per le cinque equazioni.

Un problema diverso è quello di chi ha, nella prima parte, fornito come risposta dei numeri non interi. Questo significa non aver nessuna confidenza con l'aritmetica, o quanto meno con la terminologia qui utilizzata.