Nella teoria computazionale dei numeri, l'algoritmo di Cornacchia è un algoritmo per risolvere l'equazione diofantea , dove e e sono coprimi. L'algoritmo è stato descritto nel 1908 da Giuseppe Cornacchia.
L'algoritmo Descriviamo l'algoritmo per trovare soluzioni nel caso in cui Infatti, se una di queste quantità fosse , ci si potrebbe ricondurre ad un'altra equazione della stessa forma con soluzioni tali che e . Ponendo infatti l'equazione
con la sostituzione diventa
Infine con la sostituzione si ottiene
Posta la condizione
riducendo l'equazione modulo , si ottiene
e quindi
Essendo e coprimi, si può dividere per ottenendo
Si cerca ora una soluzione a (utilizzando uno degli algoritmi per determinare i residui quadratici): se non esiste tale , non può esserci una soluzione primitiva all'equazione originale.
Senza perdita di generalità, assumiamo che sia la radice più piccola dell'equazione (e quindi ). Ricordando la definizione di , bisogna risolvere la congruenza lineare . Utilizzando l'algoritmo di Euclide fermandosi non appena , una possibile soluzione è
supponendo che entrambi i valori siano interi. Se ciò non fosse, bisogna eseguire nuovamente l'algoritmo con un'altra radice quadrata di : se dopo averle provate tutte comunque non si trova una soluzione, allora questa non esiste.
Esempio Consideriamo l'equazione .
Risulta
quindi . Risolvendo
usando l'algoritmo di Euclide, si ottiene che soddisfa ; di conseguenza
Quindi la coppia è soluzione.
Note
Collegamenti esterni
Categoria:Algoritmi