L'ultimo teorema di Fermat/Appendice: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
Riga 70: Riga 70:
Il punto 1 è generalmente chiamato '''base dell'induzione''', il punto 2 '''passo induttivo'''.
Il punto 1 è generalmente chiamato '''base dell'induzione''', il punto 2 '''passo induttivo'''.


Un modo intuitivo con cui si può guardare a questo tipo di dimosrazioni è il seguente: se disponiamo di una dimostrazione della ''base'' <math>P(0)</math> e del ''passo induttivo'' <math>P(n) \Rightarrow P(n+1)</math> allora chiaramente possiamo sfruttare queste dimostrazioni per dimostrare <math>P(1)</math> usando la regola logica modus ponens su <math>P(0)</math> (la base) e <math>P(0) \Rightarrow P(1)</math> (che è un caso particolare del passo induttiuvo per <math>n=0</math>), poi possiamo dimostrare <math>P(2)</math> poiché adesso usiamo il modus ponens su <math>P(1)</math> e <math>P(1) \Rightarrow P(2)</math>, così per <math>P(3)</math>, <math>P(4)</math>, eccetera... è chiaro a questo punto che possiamo produrre una dimostrazione in un numero finito di passi (eventualmente lunghissimo) di <math>P(n)</math> per qualunque numero naturale <math>n</math>, da cui deduciamo che <math>P(n)</math> è vero per ogni <math>n \in \N</math>.
Un modo intuitivo con cui si può guardare a questo tipo di dimostrazioni è il seguente: se disponiamo di una dimostrazione della ''base'' <math>P(0)</math> e del ''passo induttivo'' <math>P(n) \Rightarrow P(n+1)</math> allora chiaramente possiamo sfruttare queste dimostrazioni per dimostrare <math>P(1)</math> usando la regola logica modus ponens su <math>P(0)</math> (la base) e <math>P(0) \Rightarrow P(1)</math> (che è un caso particolare del passo induttiuvo per <math>n=0</math>), poi possiamo dimostrare <math>P(2)</math> poiché adesso usiamo il modus ponens su <math>P(1)</math> e <math>P(1) \Rightarrow P(2)</math>, così per <math>P(3)</math>, <math>P(4)</math>, eccetera... è chiaro a questo punto che possiamo produrre una dimostrazione in un numero finito di passi (eventualmente lunghissimo) di <math>P(n)</math> per qualunque numero naturale <math>n</math>, da cui deduciamo che <math>P(n)</math> è vero per ogni <math>n \in \N</math>.
=== Un esempio ===
=== Un esempio ===

Versione delle 21:21, 24 ago 2007

Indice del libro

Questa appendice raccoglie alcune dimostrazioni e approfondisce alcuni concetti matematici che possono essere interessanti per approfondire alcuni aspetti del libro. Si è cercato di mantenere un approccio semplice ma essendo delle dimostrazioni corrette in alcuni casi si è dovuto far ricorso comunque ad alcuni concetti e passaggi non immediati che comunque sono state specificate e chiarificate ove possibile.

Teorema di Pitagora

Essendo il teorema uno dei più noti della storia della matematica, esistono molte dimostrazioni, opera di astronomi, agenti di cambio, e anche una di Leonardo da Vinci. Probabilmente, insieme alla reciprocità quadratica, si contende la palma del teorema con più dimostrazioni in assoluto. Lo si dimostrerà in modo grafico utilizzando solamente concetti di geometria elementare. Non verrà riportata la dimostrazione di Pitagora essendo molto complessa e non immediata.

La dimostrazione è molto semplice, come si vede dal grafico si costruisce un primo quadrato formato da quattro triangoli e da due quadrati, uno di lato a e il secondo di lato b. L'area di un quadrato si calcola moltiplicando il lato per se stesso o con notazione moderna l'area è il lato elevato al quadrato. L'area del quadrato grande è quindi la somma delle aree dei quadrati che valgono a2 e b2 più la somma dei quattro triangoli. Nel secondo quadrato abbiamo nuovamente quattro triangoli e un quadrato di area c2. Essendo i quattro triangoli presenti sia a destra dell'uguaglianza che a sinistra dell'uguaglianza si possono eliminare. Quindi nell'equazione rimane:

a2+b2=c2

Come si voleva dimostrare. É da notare che la dimostrazione è generica ed effettivamente copre ogni triangolo rettangolo possibile dato che nella dimostrazione non si sono utilizzati numeri o altro ma solo generici segmenti lunghi a, b e c. La dimostrazione dipende unicamente dal fatto che i triangoli siano rettangoli e dal fatto che si sta utilizzando la geometria di Euclide.

Questa è una piccola galleria di alcune dimostrazioni geometriche del teorema anche se come si è detto sopra le dimostrazioni sono moltissime e difatti vi sono anche dimostrazioni puramente algebriche, dimostrazioni che utilizzano i numeri complessi e perfino dimostrazioni scritte sotto forma di sonetti.

Teorema fondamentale dell'aritmetica

Il Teorema fondamentale dell'aritmetica afferma che ogni numero naturale che non sia 1 ammette una ed una sola fattorizzazione in numeri primi pur di non tener conto dell'ordine dei fattori. (L'esclusione di 1 è dovuta al fatto che esso non ha fattori primi.) Questo teorema era alla base delle dimostrazioni di Gabriel Lamé e Augustin Luis Cauchy e come si è detto in generale non vale nei numeri complessi quindi non può essere utilizzato per il teorema di Fermat ma data la sua importanza si è deciso di includere comunque la dimostrazioni nell'appendice.

L'enunciato è facilmente verificabile per numeri naturali "piccoli": è facile scoprire che 70 è pari a 2*5*7 mentre 100 equivale a 2*2*5*5 ovvero 22*52, ed è altrettanto facile verificare che per questi numeri non possono esistere altre scomposizioni in fattori primi. Viceversa la dimostrazione generale è piuttosto lunga: eccone una traccia. Si tratta di una dimostrazione per assurdo: si parte cioè dall'ipotesi contraria a quella dell'enunciato per poterne dimostrare l'infondatezza.

Si supponga che esistano dei numeri scomponibili in fattori primi in più di un modo, e si chiami m il più piccolo. Innanzitutto si dimostra che, date due fattorizzazioni di m, i numeri primi che si presentano nella prima fattorizzazione sono tutti distinti da quelli della seconda fattorizzazione. Siano infatti due diverse fattorizzazioni:

dove i e i sono primi. (Nota: all'interno di una singola fattorizzazione ci possono essere fattori ripetuti, naturalmente: ad esempio, 100 = 2*2*5*5). Se ci fosse un fattore identico , potremmo dividere m per tale fattore e ottenere un numero , minore di m, che avrebbe anch'esso due fattorizzazioni distinte.

A questo punto sappiamo che è diverso da ; senza perdita di generalità possiamo supporre che . Poniamo allora

Evidentemente, , dato che la si può scrivere come

.

Dimostriamo ora che n ammette almeno due fattorizzazioni distinte.

Iniziamo considerando che il primo fattore di n, , può o no essere primo; nel caso non lo fosse, supponiamo di fattorizzarlo. La fattorizzazione di n così ottenuta non ammette tra i suoi fattori. Infatti, per la prima parte della dimostrazione, sappiamo che è diverso da ; ma non può nemmeno comparire nella eventuale fattorizzazione di . Se infatti accadesse ciò significherebbe che

e quindi sarebbe divisibile per , il che non è possibile in quanto è un numero primo.

Prendendo ora l'ultima uguaglianza della e sostituendo per m il valore della , otteniamo

In qualunque modo sia fattorizzabile il secondo fattore nella , avremo ottenuto una fattorizzazione di n che contiene , e che pertanto è diversa da quella nella , contrariamente all'ipotesi che m fosse il numero più piccolo che ammettesse più di una fattorizzazione.

Il teorema è pertanto dimostrato.

Principio di Induzione

Il Principio di induzione afferma che

Se è un sottoinsieme dell'insieme dei numeri naturali che verifica le seguenti due proprietà:

  • contiene lo ,
  • ogni volta che contiene un numero contiene anche il numero successivo ,

allora coincide con tutto l'insieme dei numeri naturali

Esso viene collocato in genere all'interno degli assiomi di Peano e fornisce un potente strumento per le dimostrazioni in tutti i settori della matematica. Nel libro viene richiamato più volte dato che molti matematici hanno cercato di dimostrare un caso base del teorema di Fermat e poi di generalizzare la soluzione per potervi includerne i casi successivi tramite questo principio.

Dimostrazioni per induzione

Per dimostrare che un certo asserto in cui compare un numero naturale vale per qualunque si può sfruttare il principio di induzione nel seguente modo:

Si pone ,

  1. si dimostra che vale , cioè che è nell'insieme dei numeri naturali per cui vale ;
  2. si assume come ipotesi che l'asserto valga per un generico e da tale assunzione si dimostra che vale anche (cioè che )

e quindi si conclude che l'insieme dei numeri per cui vale coincide con tutto l'insieme dei numeri naturali. Il punto 1 è generalmente chiamato base dell'induzione, il punto 2 passo induttivo.

Un modo intuitivo con cui si può guardare a questo tipo di dimostrazioni è il seguente: se disponiamo di una dimostrazione della base e del passo induttivo allora chiaramente possiamo sfruttare queste dimostrazioni per dimostrare usando la regola logica modus ponens su (la base) e (che è un caso particolare del passo induttiuvo per ), poi possiamo dimostrare poiché adesso usiamo il modus ponens su e , così per , , eccetera... è chiaro a questo punto che possiamo produrre una dimostrazione in un numero finito di passi (eventualmente lunghissimo) di per qualunque numero naturale , da cui deduciamo che è vero per ogni .

Un esempio

Dimostriamo che vale la seguente formula:

per ogni :

Abbiamo in questo caso .

  • Base dell'induzione: dobbiamo dimostrare che l'affermazione è vera per , cioè, sostituendo, che , e in effetti c'è ben poco da lavorare, si tratta di un calcolo elementare;
  • Passo induttivo: dobbiamo mostrare che per ogni n vale l'implicazoione , cioè, sostituendo:

Dunque dobbiamo assumere che sia vero

,

lavorare su questa uguaglianza e concludere con l'analoga uguaglianza per : Potremmo ad esempio aggiungere a entrambi i membri dell'uguaglianza P(n):

,

poi facciamo qualche semplice passaggio algebrico:

,
,

e quest'ultima uguaglianza è esattamente . Questo conclude la dimostrazione del passo induttivo.

Avendo dunque dimostrato la base dell'induzione e il passo induttivo possiamo concludere (dal principio di induzione) che deve essere vera per ogni .

Aritmetica Modulare

L'aritmetica modulare (a volte detta aritmetica dell'orologio poiché su tale principio si basa il calcolo delle ore a cicli di 12 o 24) rappresenta un importante ramo della matematica. Essa trova applicazioni nella crittografia, nella teoria dei numeri (in particolare nella ricerca dei numeri primi), ed è alla base di molte delle più comuni operazioni aritmetiche e algebriche.

Si tratta di un sistema di aritmetica degli interi, nel quale i numeri "si avvolgono su se stessi" ogni volta che raggiungono i multipli di un determinato numero n, detto modulo. L’aritmetica modulare venne formalmente introdotta da Carl Friedrich Gauss nel suo trattato Disquisitiones Arithmeticae, pubblicato nel 1801.

L'aritmetica modulare si basa sul concetto di congruenza modulo n . Dati tre numeri interi a, b, n, con n≠0, diciamo che a e b sono congruenti modulo n se la loro differenza (a−b) è un multiplo di n. In questo caso scriviamo

e diciamo che a è congruo a b modulo n. Per esempio, possiamo scrivere

poiché 38 − 14 = 24, che è un multiplo di 12.

Nel caso entrambi i numeri siano positivi, si può anche dire che a e b sono congruenti modulo n se hanno lo stesso resto nella divisione per n. Quindi possiamo anche dire che 38 è congruo 14 modulo 12 poiché sia 38 sia 14 hanno resto 2 nella divisione per 12.

Proprietà della congruenza

La congruenza è una relazione di equivalenza tra numeri interi come si vede dalle seguenti proprietà:

  • Proprietà riflessiva: ogni numero è congruo a sé stesso modulo n, per ogni n diverso da 0 fissato.
Dimostrazione: si ha a - a = 0. Ma come è noto, ogni intero non nullo è divisore di 0. Quindi n divide (a - a)
  • Proprietà simmetrica: se a è congruo a b modulo n allora b è congruo ad a modulo n
Dimostrazione: se n divide (a - b) , allora n divide anche l'opposto (b - a) = - (a - b)
  • Proprietà transitiva: se a è congruo a b modulo n e b è congruo a c modulo n allora anche a è congruo a c modulo n.
Dimostrazione: se n divide (a - b) e n divide (a - c) allora, per la proprietà distributiva della divisione rispetto alla sottrazione, n divide anche [(a - c) - (a - b)]=[a - c - a + b] = (b - c).

Invarianza rispetto alle operazioni aritmetiche

Un'altra importante caratteristica della relazione di congruenza è il fatto di essere preservata dalle usuali operazioni aritmetiche tra interi:

  • Invarianza per addizione: aumentando o diminuendo della stessa quantità due numeri congruenti modulo n, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo n. Più sinteticamente
Dimostrazione: scriviamo (a - b) = (a - b + c - c) = (a + c) - (b + c)
  • Invarianza per moltiplicazione: moltiplicando per una stessa quantità due numeri congruenti modulo n, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo n.
Dimostrazione: se n divide (a - b) allora n divide (a - b)×c
Nota: Questa proprietà si può invertire solo se n non divide c, cioè se c non è congruo a 0 (mod n).
  • Invarianza rispetto all'elevazione a potenza: elevando due numeri congrui modulo n alla stessa potenza k, i numeri ottenuti sono ancora congrui tra loro modulo n.
Dimostrazione: se a ≡ b ≡ 0 (mod n) la proposizione è banale. Se a ≡ b (mod n) non sono nulli, supponiamo di sapere che . Moltiplicando entrambi i termini per a grazie all'invarianza per moltiplicazione, avremo . Partiamo ora dalla congruenza a ≡ b (mod n) e moltiplichiamo entrambi i membri per , sempre grazie all'invazianza per moltiplicazione. Otteniamo:. Confrontando le due espressioni, ed utilizzando le proprietà simmetrica e transitiva, si deduce che . Poiché la proposizione è vera per k = 1 e il fatto che sia vera per k-1 implica che essa è vera per k, per il principio di induzione la proposizione è vera per ogni k.
Nota: Questa proprietà si può invertire solo se k è diverso da 0.