Cosa devi sapere sui numeri primi

Congruenza

Se dividiamo un numero intero n per 3 i possibili resti della divisione sono tre: 0 oppure 1 oppure 2. Ad esempio, 8 diviso 3 dà resto 2, anche 5 diviso 3 dà resto 2. Per indicare che 8 e 5 danno lo steso resto quando sono divisi per 3, Gauss (1777-1855) introdusse la notazione

8 ≡ 5 (mod 3)

che si legge 8 è congruo a 5 modulo 3. Pertanto, se consideriamo le congruenze modulo 3, l'insieme di tutti i numeri interi risulta diviso in 3 sottoinsiemi disgiunti e ciascuno di tali insieme è detto classe resto oppure classe di congruenza.

In generale:

Se a e b sono due numeri interi e d un numero positivo viene detto che a è congruo a b modulo d se a e b divisi per d danno lo stesso resto e si scrive

a ≡ b (mod d)

Questo significa che

a = nd + r, b = md + r

dove m e n sono opportuni interi e 0 ≤ r ≤ d - 1. Ne segue che a - b è divisibile per d. Infatti,

a - b = nd + r - md - r = (n - m)d

Possiamo anche dire che ogni numero è congruo modulo d al suo resto nella divisione per d ad esempio, 20 è congruo a 6 modulo 7 essendo 6 il resto della divisione 20:7, e si scrive

20 ≡ 6 (mod 7)

L'utilità della relazione di congruenza consiste nel fatto che soddisfa molte delle proprietà formali dell'uguaglianza. Ad esempio:

1. a ≡ a (mod d);

2. Se a ≡ b (mod d) allora b ≡ a (mod d);

3. Se a ≡ b (mod d) e b ≡ c (mod d) allora a ≡ c (mod d);

4. Se a ≡ a' (mod d) e b ≡ b' (mod d) allora a + b ≡ a' + b' (mod d);

5. Se a ≡ a' (mod d) e b ≡ b' (mod d) allora a - b ≡ a' - b' (mod d);

6. Se a ≡ a' (mod d) e b ≡ b' (mod d) allora a ⋅ b ≡ a' ⋅ b' (mod d);

Nella nostra vita quotidiana spesso, senza renderci conto, abbiamo a che fare con la congruenza. Vediamo tre semplici situazioni:

• Sono le 21 e ho preso l'antibiotico dovrò riprenderlo tra 10 ore e quindi devo riprenderlo alle 7.

  21 + 10 ≡ 7 (mod 24)

  Le ore si ripetono ciclicamente ogni 24 ore e quindi si ripetono modulo 24.

• Oggi è martedí ci rivediamo tra 10 giorni e quindi ci vediamo Venerdí della prossima settimana.

  2 + 10 ≡ 5 (mod 7)

  

  I giorni della settimana si ripetano ciclicamente ogni sette giorni e quindi si ripetono modulo 7.

• Le ore di un normale orologio si ripetono ogni 12 ore e quindi si ripetono modulo 12.

Con le congruenze risulta facile spiegare i famosi criteri di divisibilità tenendo presente che un numero è divisibile per n se è congruente a zero modulo n.

• Un numero n è divisibile per 3 se lo è la somma delle sue cifre.
  
  Per semplicità supponiamo che il numero sia di tre cifre, ma il ragionamento può facilmente estendersi a tutti gli altri casi. Indichiamo con a la cifra delle centinaia del nostro numero, con b quella delle decine e con c quelle delle unità: quindi

  n = a⋅10² + b⋅10 + c

  Ora, poichè tutte le potenze di 10 maggiori di 1 sono congrue a 1 modulo tre

  10 ≡ 1 (mod 3); 10² ≡ 1 (mod 3)

  si ha:

  a⋅10² + b⋅10 + c ≡ a + b + c (mod 3)

  E quindi il numero n = a⋅10² + b⋅10 + c è divisibile per 3 se:

  a + b + c ≡ 0 (mod 3)

  Ad esempio, il numero 532 non è divisibile per 3 perchè

  5 + 3 + 2 ≡ 1 (mod 3)

  Mentre il numero 531 è divisibile per 3 perchè

  5 + 3 + 1 ≡ 0 (mod 3)

• Un numero n è divisibile per 2 se termina con una cifra pari.
  
  Consideriamo ancora, per semplicità, un numero con tre cifre:

  n = a⋅10² + b⋅10 + c

  Ora, poichè tutte le potenze di 10 maggiori di 1 sono congrue a 0 modulo due

  10 ≡ 0 (mod 2); 10² ≡ 0 (mod 2)

  si ha:

  a⋅10² + b⋅10 + c ≡ c (mod 2)

  E quindi il numero n = a⋅10² + b⋅10 + c è divisibile per 2 se:

  c ≡ 0 (mod 2)

  Ad esempio, il numero 536 è divisibile per 2 perchè

  6 ≡ 0 (mod 2)

  Mentre il numero 537 non è divisibile per 2 perchè

  7 ≡ 1 (mod 2)

• Un numero n è divisibile per 5 se termina con 0 o con 5.
  
  Consideriamo ancora, per semplicità, un numero con tre cifre:

  n = a⋅10² + b⋅10 + c

  Ora, poichè tutte le potenze di 10 maggiori di 1 sono congrue a 0 modulo cinque

  10 ≡ 0 (mod 5); 10² ≡ 0 (mod 5)

  si ha:

  a⋅10² + b⋅10 + c ≡ c (mod 5)

  E quindi il numero n = a⋅10² + b⋅10 + c è divisibile per 5 se:

  c ≡ 0 (mod 5)

  Ad esempio, il numero 735 è divisibile per 5 perchè

  5 ≡ 0 (mod 5)

  Mentre il numero 838 non è divisibile per 5 perchè

  8 ≡ 3 (mod 5)

• Un numero n è divisibile per 11 se la somma delle sue cifre a segni alterni è divisibile per 11.
  
  Consideriamo ancora, per semplicità, un numero con tre cifre

  n = a⋅10² + b⋅10 + c

  E consideriamo le potenze di 10 modulo 11

  10⁰ ≡ 1 (mod 11); 10¹ ≡ -1 (mod 11); 10² ≡ 1 (mod 11)

  Cioè le potenze pari di 10 sono congrue a 1 mentre quelle dispari sono congrue a -1 modulo 11. E quindi:

  a⋅10² + b⋅10 + c ≡ a - b + c (mod 11)

  E quindi il numero n = a⋅10² + b⋅10 + c è divisibile per 11 se:

  a - b + c ≡ 0 (mod 11)

  Ad esempio, il numero 253 è divisibile per 11 perchè

  2 - 5 + 3 ≡ 0 (mod 11)

  Mentre il numero 534 non è divisibile per 11 perchè

  5 - 3 + 4 ≡ 6 (mod 11)