Lady Bracknell: Sono in vita i genitori?
John “Jack” Worthing: Io li ho persi entrambi.
Lady Bracknell: Perderne uno, signor Worthing, può essere considerata una disgrazia. Ma perderli entrambi è sbadataggine!
Da “L’importanza di chiamarsi Ernesto”
Nella teoria dei numeri, se il numero intero m divide esattamente b, pure intero, si usa scrivere: m | b. Al contrario si scrive: m ∤ b se m non divide esattamente b. Quindi valgono le seguenti ovvie relazioni 3 | 6 e 3 ∤ 7.
Quando è importante precisare il resto in una divisione tra interi, si usa scrivere:a ≡ b mod m che si legge a congruo b modulo m per indicare che dividendo a per m si ha b come resto, ovvero: a = mk + b con k intero.
Quindi:
E:
Valgono le seguenti semplici regole intuitive: se
e
allora:
In particolare, se d = 1:
cioè la moltiplicazione per c non modifica il resto. Segue che se n è un numero intero qualunque:
Formule che si possono tutte dimostrare utilizzando la definizione di congruenza. È ovvio anche che se m ∤ b e b ∤ m, m non dividerà nessuna potenza di b, ovvero m ∤ bn qualunque sia n, perché se i fattori di m non si trovano in b, non si troveranno neppure in nessuna potenza di b.
Vediamo alcuni esempi sfruttando le proprietà delle potenze per rendere più agevoli i calcoli. Risolviamo la seguente congruenza:
Dato che: 25= 32 segue immediatamente che:
da cui:
Facciamo ora un ulteriore passo avanti nell’analisi dei resti:
domandiamoci se esiste sempre una soluzione alla seguente congruenza lineare a una incognita in x:
La risposta è che esiste una soluzione se e solo se d | b dove d=MCD(a,m). Se d = 1, la soluzione è unica. L’unicità è nel senso dell’algebra indeterminata, come spesso denominata la matematica che stiamo trattando in questo articolo. Ovvero valgono tutte le soluzioni
x = x0 * c
con c, tale che:
In caso contrario, se d ≠ 1, esistono d soluzioni. Detta x0 una soluzione, le altre sono:
con i intero e tale che 0 ≤ i ≤ d–1.
La dimostrazione si ricava dalla definizione di congruenza. L’espressione:
è un’espressione simbolica per indicare l’equazione diofantea (cioè con solo soluzioni intere):
ax = my + b
ax – my = b
che ha soluzioni, appunto, se e solo se d = MCD(a, m) | b e il numero di soluzioni è proprio d. I passaggi per raggiungere il risultato sono semplici, ma non sono immediati.
La funzione di Eulero
La funzione di Eulero associa a un numero intero positivo n il numero dei numeri interi primi con n e minori di n (compreso l’uno); detto altrimenti i p tali che MCD(n,p)=1; si tratta di una funzione basilare della teoria dei numeri, che interviene in molti teoremi come quello di Fermat-Eulero, oltre ad essere uno degli ingredienti fondamentali del cifrario RSA.
Così ci limitiamo anche solo a citare la soluzione generale della congruenza lineare. Nel caso di d = 1, si ha:
dove φ (m) è la funzione di Eulero, che esprime il numero di numeri minori di m che sono relativamente primi con m, cioè i numeri che hanno con m un minimo comune multiplo pari a 1. Esempio φ (9) = 6 perché in MCD dei numeri 1, 2, 4, 5, 7, 8 con 9, è 1. Se m è primo, si ha chiaramente φ (m) = m – 1. La funzione è talvolta chiamata totiente o indicatore.
φ (m) può essere calcolata anche mediante l’espressione:
dove p1, p2… pr sono tutti i primi che dividono m.
La formula può essere riscritta nel modo seguente:
o, se si preferisce, per tutti i primi con esponente maggiore di 1:
Come caso particolare, se p e q sono primi (o, più in generale, relativamente primi) allora
φ (p · q) = φ (q) · φ (p) = (p – 1)(q – 1).
Nella figura seguente è riportato l’andamento della funzione di Eulero che è stata calcolata utilizzando la semplice definizione. La distribuzione ha delle peculiarità molto evidenti, ma non altrettanto agilmente ricavabili.
Applichiamo le formule appena descritte .
Se m = 1, φ (m) = 1.
Se m= 2, dato che 2 è primo, φ (2) = 2 – 1 = 1.
Calcoliamo ora φ (10).
Si ha φ(10) = φ (2 · 5) = φ (2) · φ (5) = (2 – 1) · (5 – 1) = 4.
Calcoliamo φ (20):
φ(20) = φ(22· 5) = φ(22) · φ(5) = (22– 2) · (4) = 8
Ecco altri valori:
Prima di applicare la formula risolutiva delle congruenze di primo grado è utile, per semplificare, applicare alcune delle proprietà viste. Se:
allora:
Esempio:
Si noti che la congruenza potrebbe essere semplificata, ma è in una forma utile per la spiegazione)
Dato che MCD(a, m) = MCD(5, 3) = 1, la soluzione è unica.
Applicando la formula risolutiva per le congruenze di primo grado:
Oppure, semplificando l’espressione iniziale:
Da cui si ricava facilmente x = 2.
[elementor-template id=”11494″]
(26)