Cos'è congruenti?

Congruenza

In matematica, specialmente in algebra e teoria dei numeri, la congruenza è una relazione di equivalenza tra numeri interi. Due interi, a e b, si dicono congrui modulo n, dove n è un intero positivo chiamato modulo, se la loro differenza (a - b) è divisibile per n. In altre parole, a e b lasciano lo stesso resto quando vengono divisi per n.

Notazione:

La congruenza modulo n si scrive come:

a ≡ b (mod n)

Definizione formale:

a ≡ b (mod n) se e solo se n divide (a - b), ovvero esiste un intero k tale che a - b = kn.

Proprietà fondamentali della congruenza:

• Riflessiva: Per ogni intero a, a ≡ a (mod n). (https://it.wikiwhat.page/kavramlar/Proprietà%20Riflessiva)
• Simmetrica: Se a ≡ b (mod n), allora b ≡ a (mod n). (https://it.wikiwhat.page/kavramlar/Proprietà%20Simmetrica)
• Transitiva: Se a ≡ b (mod n) e b ≡ c (mod n), allora a ≡ c (mod n). (https://it.wikiwhat.page/kavramlar/Proprietà%20Transitiva)

Operazioni con congruenze:

Le congruenze si comportano in modo simile alle uguaglianze, permettendo alcune operazioni algebriche:

• Addizione: Se a ≡ b (mod n) e c ≡ d (mod n), allora a + c ≡ b + d (mod n).
• Sottrazione: Se a ≡ b (mod n) e c ≡ d (mod n), allora a - c ≡ b - d (mod n).
• Moltiplicazione: Se a ≡ b (mod n) e c ≡ d (mod n), allora ac ≡ bd (mod n).
• Elevamento a potenza: Se a ≡ b (mod n), allora a^k ≡ b^k (mod n) per ogni intero positivo k.

Divisione:

La divisione in congruenze è più complessa. Non sempre è possibile dividere entrambi i lati di una congruenza per un numero. La divisione è possibile se e solo se il numero per cui si divide è coprimo con il modulo n. Precisamente, se ac ≡ bc (mod n) e MCD(c, n) = 1 (cioè il massimo comun divisore di c e n è 1), allora a ≡ b (mod n). Questo è legato al concetto di inverso%20moltiplicativo%20modulare.

Applicazioni:

La congruenza trova applicazioni in:

• Crittografia: Molti algoritmi crittografici si basano sulle proprietà delle congruenze.
• Teoria dei numeri: Risoluzione di equazioni diofantine, studio delle proprietà dei numeri primi, ecc.
• Informatica: Algoritmi di hashing, generazione di numeri pseudo-casuali.
• Calendari: Calcolo dei giorni della settimana.

Esempio:

• 17 ≡ 2 (mod 5) perché 17 - 2 = 15 è divisibile per 5.
• 25 ≡ 1 (mod 8) perché 25 - 1 = 24 è divisibile per 8.

Teoremi importanti:

• Piccolo%20teorema%20di%20Fermat: Se p è un numero primo e a è un intero non divisibile per p, allora a^p-1 ≡ 1 (mod p).
• Teorema%20di%20Eulero: Se a e n sono interi coprimi, allora a^φ(n) ≡ 1 (mod n), dove φ(n) è la funzione totiente di Eulero.
• Teorema%20cinese%20del%20resto: Fornisce una soluzione a un sistema di congruenze lineari.