Aritmetica modulare/Prime proprietà e applicazioni: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nuova pagina: In questo modulo saranno presentati i primi usi delle congruenze, e verrà dimostrato il teorema di Fermat e la sua generalizzazione. == Criteri di divisibilità == Attraverso l'uso ... |
fermat+eulero |
||
Riga 13:
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.
:<math>10^k\equiv \begin{cases}1\mod 11 & \
Di conseguenza
:<math>n\equiv a_0-a_1+a_2-\cdots+(-1)^k a_k\mod 11</math>
Questi risultati possono essere generalizzati se il numero ''n'' è scritto in una base ''b'' qualunque. In particolare, per i ''d'' tali che <math>b\equiv 1\mod d</math>, ''n'' è divisibile per ''d'' se e solo se lo è la somma delle sue cifre quando è scritto in base ''b''; invece, se <math>b\equiv -1\mod d</math> 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 ''d''. Le dimostrazioni si possono ottenere esattamente con i metodi descritti sopra.
== Il teorema di Fermat ==
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
:<math>a^p\equiv a\mod p</math>
oppure, equivalentemente, che se ''a'' non è divisibile per ''p'' allora
:<math>a^{p-1}\equiv 1\mod p</math>
L'equivalenza tra le due formulazioni è ovvia, perché l'unico caso in cui la seconda forma non si applica è quando ''p''|''a'', cioè quando <math>a\equiv 0\mod p</math>, 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
:<math>(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots+\binom{p}{p-1}a^1+1</math>
Ogni coefficiente binomiale <math>\binom{p}{k}</math> è divisibile per ''p'': infatti
:<math>\binom{p}{k}=\frac{p!}{k!(p-k)!}</math>
e il denominatore non può essere diviso da ''p'', perché è un numero primo, mentre ''p'' divide il numeratore. Quindi, passando al modulo ''p'', abbiamo
:<math>(a+1)^p\equiv a+0+0+\cdots+1\mod p\equiv a+1\mod p</math>
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
:<math>1a, 2a, 3a,\ldots,(p-1)a</math>
Se due di essi fossero uguali, ad esempio ''ia'' e ''ja'', allora si avrebbe
:<math>ia\equiv ja\mod p\Longrightarrow (i-j)a\equiv 0\mod p</math>
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
:<math>(1a)(2a)(3a)\cdots[(p-1)a]\equiv 1\cdot 2 \cdot 3\cdots (p-1)\mod p</math>
ovvero
<math>[1\cdot 2\cdot 3\cdots (p-1)]a^{p-1}\equiv1\cdot 2\cdot 3\cdots (p-1)\mod p</math>
A questo punto basta semplificare il prodotto <math>1\cdot 2\cdot 3\cdots (p-1)</math> per ottenere il teorema.
== Il teorema di Eulero ==
Una generalizzazione del piccolo teorema è data dal teorema di Eulero, che coinvolge la funzione di Eulero <math>\phi(n)</math> che ricordiamo essere, per ogni ''n'', il numero di interi coprimi con ''n''. Il teorema di Eulero afferma che
:<math>a^{\phi(n)}\equiv 1\mod n</math>
per ogni ''a'' coprimo con ''n''. Questo si riduce al piccolo teorema notando che, se ''p'' è primo, <math>\phi(n)=n-1</math>
La dimostrazione è essenzialmente quella del teorema di Fermat: detti <math>a_1,a_2,a_3,\cdots a_{\phi(n)}</math> gli interi coprimi con ''n'', i numeri
:<math>aa_1,aa_2,aa_3,\cdots aa_{\phi(n)}</math>
sono tutti diversi tra loro e tutti coprimi con ''n'', e quindi sono uguali, in qualche ordine, a <math>a_1,a_2,a_3,\cdots a_{\phi(n)}</math>. Moltiplicandoli tutti tra loro si ottiene
:<math>(aa_1)(aa_2)(aa_3)\cdots (aa_{\phi(n)})\equiv a_1a_2a_3\cdots a_{\phi(n)}\mod n</math>
:<math>a^{\phi(n)}\equiv 1\mod n</math>
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 <math>a^n=e</math>, dove ''e'' è l'elemento neutro del gruppo. (Ricordiamo che l'insieme degli elementi invertibili di <math>\mathbb{Z}_n</math> è un gruppo di ordine <math>\phi(n)</math> rispetto alla moltiplicazione.) La dimostrazione di questo teorema più generale può essere ottenuta ricalcando la prova qui presentata.
[[categoria:Aritmetica modulare]]
| |||