Vai al contenuto

Aritmetica modulare/Prime proprietà e applicazioni

Wikibooks, manuali e libri di testo liberi.
Indice del libro

In questo modulo saranno presentati i primi usi delle congruenze, e verrà dimostrato il teorema di Fermat e la sua generalizzazione.

Criteri di divisibilità

[modifica | modifica sorgente]

Attraverso l'uso delle congruenze è semplice dimostrare i noti criteri di divisibilità per 3 e per 11. Essi sono:

  • un numero è divisibile per 3 (o per 9) se lo è la somma delle sue cifre;
  • un numero è divisibile per 11 se lo è la differenza tra le sue cifre di posto pari e le sue cifre di posto dispari.

Sia infatti n un qualsiasi numero. Scriverlo in base 10 significa scriverlo come

Ora, , e quindi . La congruenza può essere riscritta come

Poiché inoltre essere divisibile per 3 equivale ad essere congruo a 0 modulo 3, n è quindi multiplo di 3 se e solo se lo è la somma delle sue cifre; non solo, ma questa caratteristica è un po' più forte, perché n è esattamente congruo alla somma delle sue cifre.

La stessa dimostrazione si applica nel caso della divisibilità per 9; nel caso di 11, invece, bisogna considerare i due casi

Di conseguenza

Questi risultati possono essere generalizzati se il numero n è scritto in una base b qualunque. In particolare, per i d tali che , n è divisibile per d se e solo se lo è la somma delle sue cifre quando è scritto in base b; invece, se allora la divisibilità di n è equivalente a quella della differenza tra le somme delle cifre di posto dispari e di posto pari, quando n è scritto in base b. Le dimostrazioni si possono ottenere esattamente con i metodi descritti sopra.

Il teorema di Fermat

[modifica | modifica sorgente]

Il teorema di Fermat (spesso chiamato "piccolo" per distinguerlo dall'Ultimo teorema di Fermat) è un risultato fondamentale dell'aritmetica modulare. Afferma che, dato un numero primo p, per ogni a si ha

oppure, equivalentemente, che se a non è divisibile per p allora

L'equivalenza tra le due formulazioni è ovvia, perché l'unico caso in cui la seconda forma non si applica è quando p|a, cioè quando , che verifica banalmente la prima uguaglianza.

Esistono diverse dimostrazioni del teorema; la prima non fa uso di proprietà dell'aritmetica modulare, ma procede per induzione su a, dimostrando la prima delle due forme:

  • se a =0 il teorema è ovvio;
  • sia vero il teorema per ogni numero naturale fino ad a. Allora per il teorema del binomio

Ogni coefficiente binomiale è divisibile per p: infatti

e il denominatore non può essere diviso da p, perché è un numero primo, mentre p divide il numeratore. Quindi, passando al modulo p, abbiamo

stabilendo il risultato per ogni a.

Un'argomentazione molto più trasparente e con molte più potenzialità è quella data da Eulero. Fissiamo a, e consideriamo i numeri

Se due di essi fossero uguali, ad esempio ia e ja, allora si avrebbe

e poiché a, non essendo divisibile per p, è coprimo con p, si deve avere i = j. Quindi i valori 1a, 2a, 3a, ... ,(p-1)a sono tutti diversi e non nulli, e quindi corrispondono in qualche ordine ai valori 1, 2, 3, ... p -1. Moltiplicandoli tutti tra loro abbiamo

ovvero A questo punto basta semplificare il prodotto per ottenere il teorema.

Il teorema di Eulero

[modifica | modifica sorgente]

Una generalizzazione del piccolo teorema è data dal teorema di Eulero, che coinvolge la funzione di Eulero che ricordiamo essere, per ogni n, il numero di interi coprimi con n e minori di n. Il teorema di Eulero afferma che

per ogni a coprimo con n. Questo si riduce al piccolo teorema notando che, se p è primo,

La dimostrazione è essenzialmente quella del teorema di Fermat: detti gli interi coprimi con n, i numeri

sono tutti diversi tra loro e tutti coprimi con n, e quindi sono uguali, in qualche ordine, a . Moltiplicandoli tutti tra loro si ottiene

Questo teorema è in realtà un caso particolare di una proposizione molto più generale, che riguarda ogni gruppo: se a è un elemento di un gruppo G di ordine n (ovvero con n elementi) allora , dove e è l'elemento neutro del gruppo. (Ricordiamo che l'insieme degli elementi invertibili di è un gruppo di ordine rispetto alla moltiplicazione.) La dimostrazione di questo teorema più generale può essere ottenuta ricalcando la prova qui presentata.

Fattoriali e teorema di Wilson

[modifica | modifica sorgente]

Un altro teorema importante e di facile dimostrazione è il teorema di Wilson, che riguarda il rapporto tra i fattoriali e i numeri primi. (Il fattoriale di n, indicato come n!, è il prodotto .) Afferma che

se e solo se n è primo.

Se n non è primo, allora tutti i fattori di n sono minori di n, e quindi sono fattori di (n -1)!, ovvero . Di conseguenza n non può verificare la proprietà precedente.

Sia ora n primo, n >2 (n =2 verifica banalmente il teorema), e consideriamo le coppie di inversi. Se le moltiplichiamo tutte tra loro abbiamo 1; poiché n è primo, inoltre, tutti gli elementi di , eccetto lo 0, hanno un inverso. Moltiplicandoli tutti tra loro, possiamo dunque raggruppare tutti gli elementi il cui inverso è diverso da sé stesso e semplificare le coppie. Gli elementi che coincidono con il proprio inverso devono verificare

cioè

per qualche k. Questo equivale a dire che x +1 o x -1 dividono n, cioè x è congruo a 1 o n -1 modulo n. Quindi

come volevasi dimostrare.

Usando il teorema di Wilson è facile dimostrare la seguente proprietà dei coefficienti binomiali:

per ogni p primo. Infatti, osserviamo innanzitutto che, per definizione,

Inoltre

dove si è usata la frazione per denotare la divisione, ovvero la moltiplicazione per l'inverso, possibile in quanto nessuna delle quantità coinvolte è divisibile per p. Raccogliendo -1 da ogni fattore del prodotto otteniamo e ritornando al coefficiente binomiale