E' possibile trovare la soluzione di \(\displaystyle x^2 + n = y^2 \) ?

[Martino]

Penso che Oiram92 sia interessato a trovare *tutte* le soluzioni (non solo una). Il problema è (sostanzialmente) equivalente al problema della fattorizzazione $zw=n$, che ammette sempre le soluzioni "banali" ($(z,w)=(1,n)$ e $(z,w)=(n,1)$) quindi in realtà si stanno cercando le soluzioni "non banali".

Dico "sostanzialmente" perché in effetti scrivendo $n = y^2-x^2 = (y-x)(y+x) = z w$ si stanno considerando fattorizzazioni i cui due fattori sono congruenti modulo $2$.

[Oiram92]

Scusatemi se sono stato poco chiaro (anche se vedo che @Martino ha intuito cosa vorrei dire nonostante ciò che scrivo sia fraintendibile). Mi sono imbattutto nella fattorizzazione dei numeri coprimi così per caso ed iniziando a giocarci sono giunto a quella relazione "risolutiva". Conosco poco e niente la teoria dei numeri (anche se mi sto facendo un pò le ossa da autodidatta) e sicuramente per questo motivo ciò che dico (o meglio scrivo) vi risulta strano e/o senza senso.

Tornando alla questione..\(\displaystyle n \) non è (e non può essere) un numero pari perchè prodotto tra due numeri primi (quindi dispari). Il fatto che quella relazione (per \(\displaystyle n \) dispari) ammette sicuramente soluzione (banale) che deriva dalla terna pitagorica lo conosco, ma quella non è l'unica soluzione! Esiste (e probabilmente è l'unica "alternativa") un'altra soluzione non banale in quella equazione ed è proprio quella che risolve definitivamente il problema della fattorizzazione dei numeri primi. Sicuramente non sono nè il primo nè sarò l'ultimo a giungere a questa conclusione. E tra l'altro non è una cosa nuova...risistemando la relazione si ha :

\(\displaystyle n = y^2 - x^2 \)

e questo era già stato scritto da Fermat. Proprio da questo deriva il mio interesse nel conoscere le soluzioni dell'equazione. Tramite software finora sono sempre riuscito a determinare sempre e soltanto due valori interi di \(\displaystyle x,y \) tali da soddisfare quella relazione (quella "banale" e quella "particolare"). Tuttavia, mentre il calcolo della soluzione "banale" è rapido ed immediato, quello della soluzione "particolare" richiede necessariamente il calcolo per tentativi. Il procedimento è semplice (come descritto nel primo post) : si fissa \(\displaystyle x=1 \) e si calcola \(\displaystyle x^2+n \), se il valore numerico ottenuto è un quadrato allora l'algoritmo è terminato, altrimenti si incrementa \(\displaystyle x++ \) e riprova fino a determinare la soluzione particolare. Il metodo è efficace perchè così facendo si ha la certezza di trovare (alla fine) il valore esatto della soluzione non "banale" tuttavia più è grande il numero e più tentativi si dovranno fare prima giungere alla soluzione. Per questo chiedevo se ci fosse qualche considerazione da fare sui possibili valori che può assumere la \(\displaystyle x \) (o la \(\displaystyle y \)) in modo tale da ridurre il numero di tentativi e quindi il tempo necessario per determinare la soluzione finale. Ma mi sembra di capire che non c è nessuna considerazione da fare, le variabili possono assumere qualsiasi valore (intero) senza eccezioni quindi non è possibile escludere alcun valore nelle iterazioni per tentativi, o mi sbaglio?

Per dare un ulteriore esempio numerico..Vogliamo fattorizzare \(\displaystyle n=69229 \). Le uniche due soluzioni che verificano la relazione sono :

\(\displaystyle 34614^2+69229 = 34615^2 \;\;\;\;\;\;\;\;\;\;\; 270^2+69229=377^2 \)

la prima è la soluzione banale, mentre la seconda è la soluzione particolare. Questa ci consente di scrivere :

\(\displaystyle 69229 = 377^2 - 270^2 = (377 - 270) \cdot (377+270) = 107 \cdot 647 \)

che è la fattorizzazione cercata.

[Martino]

Come diceva @Stickelberger, probabilmente questo ti interessa (il crivello quadratico).