Un'equazione diofantea è un'equazione in cui sono ammesse solo soluzioni intere.
Il 10° problema di Hilbert si chiedeva se esiste un algoritmo per determinare se un'equazione diofantea arbitraria ha una soluzione. Un tale algoritmo non esiste per la soluzione di equazioni diofantee di primo ordine. Tuttavia, l'impossibilità di ottenere una soluzione generale è stata dimostrata
da Yuri Matiyasevich nel 1970 (Matiyasevich 1970, Davis 1973, Davis e Hersh 1973,
Davis 1982, Matiyasevich 1993) dimostrando che la relazione (dove
è il
numero di Fibonacci) è diofantea. Più specificamente, Matiyasevich
ha dimostrato che esiste un polinomio
in
,
, e altre
variabili
,
,
, ... che hanno
la proprietà di
se e solo se
esistono degli interi
,
,
, ... tali che
.
I risultati di Matiyasevich riempirono un vuoto cruciale nel precedente lavoro di Martin Davis, Hilary Putnam, e Julia Robinson. I lavori successivi di Matiyasevich e Robinson dimostrarono che anche per le equazioni a tredici variabili, non può esistere alcun algoritmo per determinare se c'è una soluzione. Matiyasevich ha poi migliorato questo risultato per le equazioni a nove variabili (Jones e Matiyasevich 1982).
Ogilvy e Anderson (1988) fornirono un numero di equazioni diofantee con soluzioni conosciute e sconosciute.
Un'equazione lineare diofantea (in due variabili) è un'equazione della forma:
![]() |
(1)
|
in cui le soluzioni si cercano con ,
, e
interi. Tali equazioni possono essere risolti completamente, e la prima soluzione nota è stato costruito da Brahmagupta. Consideriamo l'equazione
![]() |
(2)
|
Ora usiamo una variazione dell'algoritmo euclideo, lasciando e
![]() | ![]() | ![]() |
(3)
|
![]() | ![]() | ![]() |
(4)
|
![]() | ![]() | ![]() |
(5)
|
![]() | ![]() | ![]() |
(6)
|
Partendo dal basso si ha
![]() | ![]() | ![]() |
(7)
|
![]() | ![]() | ![]() |
(8)
|
quindi
![]() | ![]() | ![]() |
(9)
|
![]() | ![]() | ![]() |
(10)
|
Continuare questa procedura fino alla fine verso l'alto.
Prendiamo come esempio l'equazione
![]() |
(11)
|
e applicare l'algoritmo sopra per ottenere
![]() |
(12)
|
La soluzione è pertanto ,
.
La procedura sopra descritta può essere semplificata notando che le due colonne più a sinistra sono compensate da una entry e segni alterni, come è necessario poiché
![]() | ![]() | ![]() |
(13)
|
![]() | ![]() | ![]() |
(14)
|
![]() | ![]() | ![]() |
(15)
|
quindi i coefficienti di and
sono gli stessi e
![]() |
(16)
|
Ripetendo l'esempio precedente utilizzando queste informazioni, dunque
![]() |
(17)
|
e si recupera la soluzione sopra.
Chiamiamo le soluzioni di
![]() |
(18)
|
e
. Se i segni
davanti a
o
sono negativi, quindi risolvere l'equazione qui sopra e prendere i segni delle soluzioni dalla tabella seguente:
equazione | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
Infatti la soluzione dell'equazione
![]() |
(19)
|
è equivalente a trovare la frazione continua per , con
e
coprimi (Olds 1963). Se ci sono
termini nella frazione,
prendere i
convergnti
.
Ma
![]() |
(20)
|
così una soluzione è ,
, con una soluzione generale
![]() | ![]() | ![]() |
(21)
|
![]() | ![]() | ![]() |
(22)
|
con un intero. La soluzione in termini di piccoli interi positivi è data dalla scelta di un appropriato
.
Ora consideriamo l' equazione generale della forma
![]() |
(23)
|
Il massimo comun divisore può essere diviso ottenendo
![]() |
(24)
|
dove ,
, e
. Se
, allora
non è un intero e l'equazione non può avere una soluzione in numeri interi. Una condizione necessaria e sufficiente per l'equazione generale
di avere soluzioni in numeri interi
è pertanto
. Se questo è il caso, allora risolvere
![]() |
(25)
|
e moltiplicare le soluzioni per , poichè
![]() |
(26)
|
D. Wilson ha compilato una lista delle potenze più piccole di interi positivi che sono la somma di
potenze distinte di piccoli interi positivi. Le prime
sono 3, 5, 6, 15, 12, 25, 40, ...(Sloane's A030052):
![]() | ![]() | ![]() |
(27)
|
![]() | ![]() | ![]() |
(28)
|
![]() | ![]() | ![]() |
(29)
|
![]() | ![]() | ![]() |
(30)
|
![]() | ![]() | ![]() |
(31)
|
![]() | ![]() | ![]() |
(32)
|
![]() | ![]() | ![]() |
(33)
|
![]() | ![]() | ![]() |
(34)
|
![]() | ![]() | ![]() |
(35)
|
![]() | ![]() | ![]() |
(36)
|