Teorema di Fermat sulle somme di due quadrati
Date le quadruple Pitagoriche
$d=36*m^2+18*m+4*n^2+2*n+3$
,
$a=24*m*n+6*m+6*n+1$
,
$b=2*(3*m+n+1)*(6*m-2*n+1)$
,
$c=2*(3*m+n+1)$
,
$a^2+c^2=d^2-b^2=p$
,
$n=0$
per $n=0$ al variare di $m$ avremo potenziali numeri primi $p$ nella forma $p=4*h+1=d^2-b^2$ (poichè $d-b=1$ e $d$ è dispari e $b$ è pari)
dei quali conosciamo come si scrive come somma di due quadrati $p=a^2+c^2$
la mia domanda è:
si può determinare se tale scrittura è unica ?
$d=36*m^2+18*m+4*n^2+2*n+3$
,
$a=24*m*n+6*m+6*n+1$
,
$b=2*(3*m+n+1)*(6*m-2*n+1)$
,
$c=2*(3*m+n+1)$
,
$a^2+c^2=d^2-b^2=p$
,
$n=0$
per $n=0$ al variare di $m$ avremo potenziali numeri primi $p$ nella forma $p=4*h+1=d^2-b^2$ (poichè $d-b=1$ e $d$ è dispari e $b$ è pari)
dei quali conosciamo come si scrive come somma di due quadrati $p=a^2+c^2$
la mia domanda è:
si può determinare se tale scrittura è unica ?
Risposte
Si’ la scrittura di un primo come somma di quadrati e’ unica (a meno di scambiare gli addendi ovviamente) perché scrivere un primo $p$ come somma di quadrati equivale a cercare un intero gaussiano di norma $p$, e una volta che ne hai trovato uno, chiamalo $x$, tutti gli altri sono $\pm x$ e $\pm\bar{x}$, che danno luogo alla stessa scrittura.
La domanda era un'altra:
Per $n =0$ variando $m$ nei naturali quella quadrupla ci da un numero $p=4*h+1=a^2+c^2=d^2-b^2$ che non sappiamo se è primo o no.
esempio per $m=1 -> p=113=7^2+8^2$
La domanda è :
come facciamo a sapere se questa scrittura è unica senza sapere che $p$ è primo?
Per $n =0$ variando $m$ nei naturali quella quadrupla ci da un numero $p=4*h+1=a^2+c^2=d^2-b^2$ che non sappiamo se è primo o no.
esempio per $m=1 -> p=113=7^2+8^2$
La domanda è :
come facciamo a sapere se questa scrittura è unica senza sapere che $p$ è primo?
Se $p$ non è primo e non è un quadrato la scrittura non è mai unica.
"hydro":
Se $p$ non è primo e non è un quadrato la scrittura non è mai unica.
$117=6^2+9^2$
Scusami ho detto una stupidaggine: la scrittura è unica se e solo se esiste al più un primo $\equiv 1\mod 4$ che divide $n$ e lo fa con esponente $1$. Comunque sta tutto scritto qua.
è vero che non esiste un numero non primo nella forma $4*k+1=a^2+b^2$ dove $a$ e $b$ sono unici o se sono unici il massimo comun divisore di $a$ e $b$ è diverso da $1$ ?
"hydro":
Si’ la scrittura di un primo come somma di quadrati e’ unica (a meno di scambiare gli addendi ovviamente) perché scrivere un primo $p$ come somma di quadrati equivale a cercare un intero gaussiano di norma $p$, e una volta che ne hai trovato uno, chiamalo $x$, tutti gli altri sono $\pm x$ e $\pm\bar{x}$, che danno luogo alla stessa scrittura.
Gentilmente mi faresti un esempio
$113=7^2+8^2$
$365=13^2+14^2$
Un esempio di cosa?
"hydro":
Un esempio di cosa?
un esempio di come si procede per vedere se la somma dei quadrati è unica.
(senza conoscere la primalità di p)
O non si può verificare?
Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.
"hydro":
Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.
Grazie
C'è un altro modo ma usa i residui quadratici:
L'algoritmo di Cornacchia
ho scritto tutto quello che so su questo argomento qui:
https://www.academia.edu/115482663/Pyth ... torizazion
https://www.academia.edu/115482663/Pyth ... torizazion
"P_1_6":
[quote="hydro"]Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.
Grazie
C'è un altro modo ma usa i residui quadratici:
L'algoritmo di Cornacchia[/quote]
Quello ti dice solo se esiste una soluzione, non se la soluzione è unica.
"hydro":
[quote="P_1_6"][quote="hydro"]Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.
Grazie
C'è un altro modo ma usa i residui quadratici:
L'algoritmo di Cornacchia[/quote]
Quello ti dice solo se esiste una soluzione, non se la soluzione è unica.[/quote]
Non solo ti dice se ci sono più soluzioni ma ti dice anche quali sono
$x^2 \equiv -1 (mod 365)$ $-> x=27$
$x \equiv 365 (mod 27) $ $ -> x=14$
$[14,sqrt(365-14^2)]=(14,13)$
$x^2 \equiv -1 (mod 365)$ $-> x=173$
$x \equiv 365 (mod 173)$ $-> x=19 $
$[19,sqrt(365-19^2)]=(19,2)$
No, non funziona così. L'algoritmo di Cornacchia prende in input una radice di $-1$ modulo $p$ e ti restituisce, se esiste, una soluzione di $x^2+y^2=p$. Nessuno ti garantisce che ogni radice di $-1$ dia luogo ad una soluzione diversa, nessuno ti garantisce che ogni soluzione si possa trovare tramite l'algoritmo e oltretutto se $p$ è composito conoscere le radici di $-1$ modulo $p$ è essenzialmente equivalente a conoscere la fattorizzazione di $p$. Questo è spiegato anche sulla pagina di Wikipedia, ma l'idea è semplice: se $x^2=y^2=-1\mod p$ allora $(x-y)(x+y)=0 \mod p$ e quindi $\gcd(p,x-y)\ne 1$, a patto ovviamente che $x\ne \pm y$.
"hydro":
No, non funziona così. L'algoritmo di Cornacchia prende in input una radice di $-1$ modulo $p$ e ti restituisce, se esiste, una soluzione di $x^2+y^2=p$. Nessuno ti garantisce che ogni radice di $-1$ dia luogo ad una soluzione diversa, nessuno ti garantisce che ogni soluzione si possa trovare tramite l'algoritmo e oltretutto se $p$ è composito conoscere le radici di $-1$ modulo $p$ è essenzialmente equivalente a conoscere la fattorizzazione di $p$. Questo è spiegato anche sulla pagina di Wikipedia, ma l'idea è semplice: se $x^2=y^2=-1\mod p$ allora $(x-y)(x+y)=0 \mod p$ e quindi $\gcd(p,x-y)\ne 1$, a patto ovviamente che $x\ne \pm y$.
Grazie
Ho imparato un'altra cosa
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo