E' possibile trovare la soluzione di \(\displaystyle x^2 + n = y^2 \) ?
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 :
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 :
[*:3uewfhox] per \(\displaystyle x = 1 \) la relazione fornisce \(\displaystyle 1^2 + 247 = 248 \), che non è un quadrato perfetto[/*:3uewfhox]
[*:3uewfhox] per \(\displaystyle x = 2 \) la relazione fornisce \(\displaystyle 2^2 + 247 = 251 \), che non è un quadrato perfetto[/*:3uewfhox]
[*:3uewfhox] per \(\displaystyle x = 3 \) la relazione fornisce \(\displaystyle 3^2 + 247 = 256 = 16^2 \), stavolta abbiamo trovato il valore di \(\displaystyle x \) corretto[/*:3uewfhox]
[/list:u:3uewfhox]
esiste un metodo che mi consente di determinare il valore di \(\displaystyle x \) più velocemente rispetto al metodo per tentativi?
Risposte
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.
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.
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.
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.
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).
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} \)
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.
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.
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$
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$
Forse la questione è più semplice di quello che sembra ...
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":
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
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 :
si tratta di risolvere la seguente equazione :
che ci restituisce le soluzioni banali ipotizzate prima. Tuttavia se procediamo in modo diverso (come nel primo post) vediamo che per :
ed in tal caso l'equazione diventa :
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.
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.
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
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
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$.
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$.
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 :
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 :
la prima è la soluzione banale, mentre la seconda è la soluzione particolare. Questa ci consente di scrivere :
che è la fattorizzazione cercata.
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo