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

[Oiram92]

Consideriamo un numero intero \(\displaystyle n \) (coprimo) qualsiasi, ci sono metodi (non per tentativi) con i quali è possibile determinare quale quadrato sommato ad \(\displaystyle n \) mi fornisce un quadrato? L'unica condizione da rispettare è il fatto che \(\displaystyle x,n,y \in \mathbb{N} \). Aggiungo anche un esempio perchè molto probabilmente detta così risulta poco chiara.

Consideriamo \(\displaystyle n = 247 \), quello che ci chiediamo è : qual è il valore di \(\displaystyle x \in \mathbb{N} \) (probabilmente unico) per cui \(\displaystyle x^2 + n \) mi restituisce un certo quadrato \(\displaystyle y^2 \)?

Procedendo per tentativi si vede che :

• per \(\displaystyle x = 1 \) la relazione fornisce \(\displaystyle 1^2 + 247 = 248 \), che non è un quadrato perfetto
• per \(\displaystyle x = 2 \) la relazione fornisce \(\displaystyle 2^2 + 247 = 251 \), che non è un quadrato perfetto
• per \(\displaystyle x = 3 \) la relazione fornisce \(\displaystyle 3^2 + 247 = 256 = 16^2 \), stavolta abbiamo trovato il valore di \(\displaystyle x \) corretto

esiste un metodo che mi consente di determinare il valore di \(\displaystyle x \) più velocemente rispetto al metodo per tentativi?

[Martino]

Ciao! Se lo riscrivi come $n = (y-x)(y+x)$ e cambi variabili $z=y-x$ e $w=y+x$ trovi l'equazione equivalente $n=zw$ ovvero le soluzioni sono parametrizzate dalle fattorizzazioni di $n$ come prodotto di due interi.

Quindi devi studiare tutte le fattorizzazioni di $n$, nel tuo caso

$247 = 13*19 = (-13)*(-19) = 1*247 = (-1)*(-247)$,

e $y-x$ può essere uno qualsiasi dei due fattori, $y+x$ l'altro. Trovi due soluzioni (con $x$ e $y$ positivi), cioè $(x,y)=(3,16)$ e $(x,y)=(123,124)$.

Nel frattempo sposto in Teoria dei numeri.

[Oiram92]

Grazie mille per la risposta e mi scuso per aver sbagliato sezione (non ci avevo fatto caso).

Il problema è che la risoluzione di quella equazione mi consente di trovare esattamente la fattorizzazione di \(\displaystyle n \) (numero coprimo) attraverso altri calcoli successivi. Se ci fosse un metodo più veloce di quello per tentativi e che non fa uso della fattorizzazione di \(\displaystyle n \) sarebbe possibile fattorizzare qualsiasi numero coprimo (anche molto grande) soltanto nel tempo impiegato a risolvere quella equazione.

[Martino]

La tua equazione $x^2+n=y^2$ è equivalente (tramite un semplice passaggio) all'equazione $n=zw$ (e purtroppo la riformulazione non semplifica il problema della fattorizzazione) quindi la difficoltà computazionale del problema è la stessa della difficoltà computazionale di fattorizzare un numero intero. Non esiste (non è ancora stato trovato) nessun algoritmo che faccia questo in tempi polinomiali (vedi qui).

[Oiram92]

Grazie per il link, lo avevo già letto tempo fa ma una rinfrescata non fa mai male. Quindi in sostanza è un pò come il cane che si morde la coda..è un vero peccato perchè se si riuscisse a determinare il valore unico di \(\displaystyle x \) che soddisfa quella relazione allora si avrebbe già la fattorizzazione da :

\(\displaystyle n_{1,2} = y \pm \sqrt{y^2-n} \)

[Stickelberger]

Come dice @Martino, risolvere il problema di @Oiram92 e’ equivalente
al problema della fattorizzazione di $n$, nel senso che una soluzione di
uno dei due problema si trasforma subito in una soluzione dell’altro.

Nello stesso senso, il problema simile di trovare $x,y\in ZZ$ non banali tali
che $x^2\equiv y^2$ modulo $n$ e' equivalente al problema della fattorizzare di $n$.

Questa seconda equivalenza e' la base di un algoritmo efficiente per
fattorizzare $n$, vale a dire il crivello quadratico.

[superpippone]

Quella che scrivo mi sembra troppo semplice, e magari non c'entra niente. Però....

Se $n$ è dispari, basta dividerlo per 2, e arrotondare.
Mi spiego:

$247:2=123,5$ arrotondo a $123$ e $124$.

$123^2+247=124^2$


Se $n$ è pari, si divide per $4$, e si somma-sottrae $1$.

$40:4=10$ sommo-sottraggo 1, e ottengo $9$ e $11$

$9^2+40=11^2$


$42:4=10,5$ trovo $9,5$ e $11,5$

$9,5^2+42=11,5^2$

[axpgn]

Forse la questione è più semplice di quello che sembra ...

Consideriamo un numero intero \(\displaystyle n \) qualsiasi, ci sono metodi (non per tentativi) con i quali è possibile determinare quale quadrato sommato ad \(\displaystyle n \) mi fornisce un quadrato?

Ricapitolando da quanto detto da superpippone abbiamo che se $n$ è dispari, sappaimo tutti che la differnza tra due quadrati consecutivi è un numero dispari perciò se $n=2k+1$ allora $k=(n-1)/2$ da cui $(k+1)^2-k^2=k^2+2k+1-k^2=2k+1=n$.

Se invece $n$ è pari e $n/2$ è dispari allora non esiste nessun quadrato per cui quanto richiesto sia vero ...
Se la differenza tra due quadrati è pari allora i due quadrati o sono entrambi pari od entrambi dispari ...
Se pari cioè $p=2h$ e $q=2k$ allora $n=p^2-q^2=4h^2-4k^2=4(h^2-k^2)$ per cui $n$ deve essere divisibile per $4$.
Se dispari cioè $p=2h+1$ e $q=2k+1$ allora $n=p^2-q^2=(2h+1)^2-(2k+1)^2=4h^2+4h+1-4k^2-4k-1=4(h^2+h-k^2-k)$ per cui anche in questo caso $n$ deve essere divisibile per $4$.

Cordialmente, Alex

[Oiram92]

Grazie per le ulteriori risposte quello che avete proposto sono dei metodi che derivano dalle terne pitagoriche (che avevo già considerato ma non vanno bene, o perlomeno non sono il risultato corretto a cui si deve arrivare).

@Martino e @Stickelberger hanno centrato in pieno il problema. Si tratta di fattorizzare un numero coprimo (costituito dal prodotto unico di due numeri primi). Argomentando l'esempio del primo post vi spiego perchè risolvere quell'equazione è fondamentale (anche se come dicevano prima si tratta dello stesso problema dopo un cambio di variabili).

Dunque consideriamo nuovamente \(\displaystyle n = 13 \cdot 19 = 247 \). Per fattorizzarlo nel prodotto di due numeri primi non ci sono alternative se non utilizzare \(\displaystyle p=13 \) e \(\displaystyle q = 19 \) ma questo è il risultato che non conosciamo (e vogliamo determinarli per "vie secondarie"). Un secondo modo banale (che però non è una fattorizzazione in numeri primi) è quello di scrivere \(\displaystyle 247 = 1 \cdot 247 \). In tal caso usando :

\(\displaystyle x = 123 \;\;\;\;\;\;\;\;\;\; y = 124 \;\;\;\;\) in modo che \(\displaystyle \;\;\;\; 123^2 + 247 = 124^2 \)

si tratta di risolvere la seguente equazione :

\(\displaystyle (z-y)^2 = x^2 \;\;\;\;\;\;\rightarrow \;\;\;\;\;\;\;\; z_{1,2} = \left\{ 1 \;;\; 247 \right\} \)

che ci restituisce le soluzioni banali ipotizzate prima. Tuttavia se procediamo in modo diverso (come nel primo post) vediamo che per :

\(\displaystyle x = 3 \;\;\;\;\;\;\;\;\;\; y = 16 \;\;\;\;\) in modo che \(\displaystyle \;\;\;\; 3^2 + 247 = 16^2 \)

ed in tal caso l'equazione diventa :

\(\displaystyle (z-16)^2 = 3^2 \;\;\;\;\;\;\rightarrow \;\;\;\;\;\;\;\; z_{1,2} = \left\{ 13 \;;\; 19 \right\} \)

che sono i valori cercati. Inoltre, ho osservato sperimentalmente che (a parte le coppie \(\displaystyle \{123,124\} \) e \(\displaystyle \{3,16\} \)) non esistono altri valori che soddisfano quella relazione. Tuttavia se il numero inizia a crescere (anche di parecchio) i tentativi da fare per determinare l'unica coppia non banale aumentano (come è giusto che sia). Per questo motivo chiedevo se esiste un metodo diverso per determinare quella particolare coppia. Andrebbe bene anche un metodo per tentativi "discreto", nel senso che controlla solo determinati possibili valori e non che utilizzi un incremento progressivo di \(\displaystyle +1 \) come fatto nel primo post. Anche perchè l'obiettivo finale è quello di fattorizzare qualsiasi numero (a prescindere dal numero di cifre) in tempi onesti.

[axpgn]

Se hai cambiato obiettivo, ok ... ma la tua domanda iniziale era "... ci sono metodi (non per tentativi) con i quali è possibile determinare quale quadrato sommato ad \( \displaystyle n \) mi fornisce un quadrato? L'unica condizione da rispettare è il fatto che $x,y,n in NN$ ..."
Mi pare che a questa sia stata data risposta ...
Se $n$ è dispari allora c'è sempre soluzione cioè $x^2=((n-1)/2)^2$
Se $n$ è pari allora abbiamo due casi:
- se $n$ NON è divisibile per quattro allora non c'è soluzione.
- se $n$ è divisibile per quattro abbiamo due casi (e si ricomincia ...):
----- se $m=n/4$ è dispari allora c'è sempre soluzione ...
----- se $m=n/4$ è pari allora abbiamo due casi ... ecc.

Ricapitolando ... se nella scomposizione in fattori di $n$ l'esponente di $2$ è pari allora c'è soluzione, se è dispari non c'è ...

Cordialmente, Alex