Arte del Problem Solving

Un’equazione diofantina è un’equazione che mette in relazione quanititi intere (o talvolta numeri naturali o numeri interi).

Trovare la soluzione o le soluzioni di un’equazione diofantina è strettamente legato all’aritmetica modulare e alla teoria dei numeri. Spesso, quando un’equazione diofantina ha infinite soluzioni, si usa la forma parametrica per esprimere la relazione tra le variabili dell’equazione.

Le equazioni diofantine prendono il nome dall’antico matematico greco/alessandrino Diofanto.

Combinazione lineare

Un’equazione diofantina nella forma è nota come combinazione lineare. Se due numeri interi relativamente primi e sono scritti in questa forma con , l’equazione avrà un numero infinito di soluzioni. Più in generale, ci sarà sempre un numero infinito di soluzioni quando . Se , allora non ci sono soluzioni dell’equazione. Per vedere perché, considerate l’equazione . è un divisore del LHS (si noti anche che deve essere sempre un intero). Tuttavia, non sarà mai un multiplo di , quindi non esistono soluzioni.

Si consideri ora il caso in cui . Quindi, . Se e sono relativamente primi, allora tutte le soluzioni sono ovviamente nella forma per tutti gli interi . Se non lo sono, semplicemente le dividiamo per il loro massimo comune divisore.

Tripli pitagorici

Articolo principale: Tripla pitagorica

Una tripla pitagorica è un insieme di tre numeri interi che soddisfano il Teorema di Pitagora, . Ci sono tre metodi principali per trovare le triple pitagoriche:

Metodo di Pitagora

Se è un numero dispari, allora è una tripla pitagorica.

Metodo di Platone

Se , è una tripla pitagorica.

Metodo di Babilonia

Per qualsiasi , abbiamo è una tripla pitagorica.

Somma delle quarte potenze

Un’equazione di forma non ha soluzioni intere, come segue:Supponiamo che l’equazione abbia soluzioni intere, e consideriamo la soluzione che minimizza . Sia questa soluzione . Se allora il loro GCD deve satificare . La soluzione sarebbe allora una soluzione minore di , che contraddice la nostra ipotesi. Quindi, questa equazione non ha soluzioni intere.

Se , procediamo allora con il caso, in .

Nota che ogni quadrato, e quindi ogni quarta potenza, è o o . La prova di questo è abbastanza semplice, e puoi mostrarla tu stesso.

Caso 1:

Questo implicherebbe , una contraddizione.

Caso 2:

Questo implicherebbe , una contraddizione poiché abbiamo assunto .

Caso 3: , e

Sappiamo anche che i quadrati sono o o . Quindi, tutte le quarte potenze sono o o .

Con un approccio simile, dimostriamo che:

, quindi .

Questa è una contraddizione, poiché implica che sia dispari, e implica che sia pari. QED

Equazioni di Pell

Articolo principale: Equazione di Pell

Un’equazione di Pell è un tipo di equazione diofantina nella forma per il numero naturale . Le soluzioni dell’equazione di Pell quando non è un quadrato perfetto sono collegate all’espansione in frazione continua di . Se è il periodo della frazione continua e è la esima convergenza, tutte le soluzioni dell’equazione di Pell sono nella forma per il numero intero positivo .

Metodi di risoluzione

Piano delle coordinate

Nota che qualsiasi combinazione lineare può essere trasformata nell’equazione lineare , che è solo l’equazione dell’intercetta della pendenza di una linea. Le soluzioni dell’equazione diofantina corrispondono ai punti del reticolo che giacciono sulla retta. Per esempio, consideriamo l’equazione o . Una soluzione è (0,1). Se si traccia il grafico della retta, è facile vedere che la retta interseca un punto di reticolo quando x e y aumentano o diminuiscono dello stesso multiplo di e , rispettivamente (parola?). Quindi, le soluzioni dell’equazione possono essere scritte parametricamente (se pensiamo a come “punto di partenza”).

Aritmetica modulare

A volte, l’aritmetica modulare può essere usata per dimostrare che non esistono soluzioni a una data equazione diofantina. In particolare, se dimostriamo che l’equazione in questione non è mai vera mod , per qualche intero , allora abbiamo dimostrato che l’equazione è falsa. Tuttavia, questa tecnica non può essere usata per mostrare che le soluzioni di un’equazione diofantina esistono.

Induzione

A volte, quando sono state trovate poche soluzioni, l’induzione può essere usata per trovare una famiglia di soluzioni. Tecniche come la Discesa infinita possono anche dimostrare che non esistono soluzioni a una particolare equazione, o che non esistono soluzioni al di fuori di una particolare famiglia.

Soluzioni generali

È naturale chiedersi se esiste una soluzione generale per le equazioni diofantine, cioè un algoritmo che troverà le soluzioni per qualsiasi equazione diofantina data. Questo è noto come il decimo problema di Hilbert. La risposta, tuttavia, è no.

L’ultimo teorema di Fermat

Articolo principale: L’ultimo teorema di Fermat

è noto come ultimo teorema di Fermat per la condizione . Nel 1600, Fermat, mentre stava lavorando su un libro sulle equazioni diofantine, scrisse un commento a margine del tipo “Ho una prova veramente meravigliosa di questa proposizione che questo margine è troppo stretto per contenere”. Fermat in realtà fece molte congetture e propose molti “teoremi”, ma non era uno che scriveva le prove o molto altro che commenti scarabocchiati. Dopo la sua morte, tutte le sue congetture sono state ri-provate (false o vere) tranne l’Ultimo Teorema di Fermat. Dopo oltre 350 anni di fallimenti, il teorema fu finalmente dimostrato da Andrew Wiles dopo aver passato più di 7 anni a lavorare sulla dimostrazione di 200 pagine, e un altro anno a correggere un errore nella dimostrazione originale.

Problemi

Introduzione

Due agricoltori concordano che i maiali valgono dollari e le capre dollari. Quando un contadino è in debito con l’altro, paga il debito in maiali o capre, con il “resto” ricevuto sotto forma di capre o maiali a seconda delle necessità. (Per esempio, un debito di dollari potrebbe essere pagato con due maiali, con una capra ricevuta come resto). Qual è l’ammontare del più piccolo debito positivo che può essere risolto in questo modo?