EQUAZIONE DIOFANTEA P = x² + y²

EQUAZIONE  P = x² + y²  con P numero primo ed x ed y numeri interi positivi.

Possiamo dividere i numeri primi in due grandi famiglie: quelli della forma 4n + 1 e quelli della forma 4n + 3. I primi possono essere rappresentati in uno ed un solo modo come somma di due quadrati esatti, i secondi in nessun modo. Ad esempio il numero primo 89 è della forma 4n + 1, infatti  89 = 4*22 + 1. Esso è esprimibile in un solo modo come somma di due quadrati esatti, infatti  89 = 5² + 8². Il numero 71 invece è della forma 4n + 3 (71 = 4*17 +3) e non può essere rappresentato in nessun modo come somma di due quadrati esatti.
Per risolvere l’equazione diofantea  P = x² + y² bisogna prima risolvere la congruenza:
z² ≡ -1  (mod. P). (1)
Questa congruenza ha soluzioni solo se P è della forma 4n + 1. Le soluzioni sono due e, se le chiamiamo A e B, sono tali che  A + B = P.
Ad esempio se  P = 29, le due soluzioni della congruenza sono 12 e 17, infatti:
12² + 1 = 145 divisibile per 29
17² + 1 = 290 divisibile per 29
Inoltre  12 + 17 = 29
Nelle considerazioni che seguono assumiamo che P sia sempre un numero primo della forma 4n + 1.
Una soluzione della (1) è data da:
A = ((p-1)/2)! Modulo P dove ! è il simbolo del fattoriale (es. 7! = 7*6*5*4*3*2*1).
Ad esempio se p = 29 si ha:
14! = 87178291200
Il resto della divisione di 87178291200 per 29 è 12 che è una soluzione della (1). L’altra soluzione si trova facilmente: B = P – A = 29 – 12 = 17.
Una soluzione della (1) che coinvolge numeri un po’ meno grandi è:
t^((p-1)/4)  Modulo P
dove t è un qualsiasi non residuo quadratico di P ed il simbolo ^ indica elevato a.
sempre nel caso di P = 29, un suo non residuo quadratico è 2. avremo:
2^7 = 128
Il resto della divisione di 128 per 29 è anche qui 12.
Ricordiamo che un residuo quadratico di un numero primo P è il resto della divisione di un quadrato esatto per P e che tutti i numeri primi hanno (P-1)/2 residui quadratici e (P-1)/2 non residui quadratici.
Una volta trovate le soluzioni A e B della (1) si può facilmente risolvere l’ equazione  P = x² + y² procedendo in questo modo:
Sia A il maggiore tra A e B. Si calcola il resto R della divisione di A per B. Se R*R <P allora l’equazione è già risolta:
x = R ; y = sqr(P- R*R)   (sqr indica la radice quadrata).
Se invece R*R > P allora bisogna reiterare il processo: si calcola il resto della divisione di B per R e così via.
Facciamo un esempio pratico:
Si vuole risolvere l’equazione diofantea  241 = x² + y².
241 = 4*60 + 1 quindi l’equazione ha soluzioni.
Dobbiamo risolvere la congruenza:
z² ≡ -1  modulo P
Usando il primo metodo, una soluzione sarà:
((P-1)/2)!  Modulo P:
120! Modulo P = 64.
L’altra soluzione sarà:
241 – 64 = 177
Usando il secondo metodo, essendo 7 un non residuo quadratico di 241, si avrà:
7^((P-1)/4)  modulo p  =  7^60  modulo P  =  177
L’altra soluzione sarà  241 – 177 =  64
Dunque le due soluzioni sono 64 e 177.
Possiamo ora procedere col metodo delle divisioni successive:
Il resto della divisione di 177 per 64 è 49.
49*49 >241
Il resto della divisione di 64 per 49 è 15
15*15 = 225 < 241
Allora:
x = 15
y = sqr(241 – 15*15) = sqr(241 – 225) = sqr(16) = 4
Dunque:
241 = 4² + 15²
Infatti:
4² + 15² = 16 + 225 = 241
Per chi fosse allergico a congruenze, residui e non residui quadratici vediamo in pratica come risolvere l’equazione diofantea  P = x² + y² con P numero primo della forma 4n + 1 ed x ed y numeri interi:
Si calcoli ((P-1))/2)! e lo si divida per P. Sia A il resto di questa divisione. Sia B = P-A.
Sia A il maggiore tra A e B. Si calcola il resto R della divisione di A per B. Se R*R <P allora l’equazione è già risolta:
x = R ; y = sqr(P- R*R)   (sqr indica la radice quadrata).
Se invece R*R > P allora bisogna reiterare il processo: si calcola il resto della divisione di B per R e così via.
Attenzione che se P non è della forma 4n +1 (P = 4n + 3) l’equazione non ha soluzioni ed il metodo darebbe quindi risultati sballati!
Il problema è che ((P-1)/2)! È un numero enorme, allora conviene procedere così:
Si può calcolare direttamente il resto della divisione di ((p-1)/2)! Per P:
Si comincia a calcolare 1*3*4*5….. fino a che il suo valore supera P. Appena questo valore ha superato P si calcola il resto R della divisione per P. Poi si ricomincia a calcolare il fattoriale senza i termini già calcolati partendo da R:
R*m*(m+1)*(m+2)…. E non appena questo valore ha superato P, ci si ferma e si calcola il resto della divisione per P e così via.
Esempio: si calcoli il resto della divisione di ((29-1)/2)! Per 29:
1*2*3*4*5 = 120>29
Il resto della divisione di 120 per 29 è 4.
4*6*7 = 168>29
Il resto della divisione di 168 per 29 è 23.
23*8 = 184>29
Il resto della divisione di 184 per 29 è 10.
10*9 = 90 > 29
Il resto della divisione di 90 per 29 è 3.
3*10 = 30>29
Il resto della divisione di 30 per 29 è 1.
1*11*12 = 132>29
Il resto della divisione di 132 per 29 è 16.
16*13 = 208>29
Il resto della divisione di 208 per 29 è 5.
5*14 = 70>29
Il resto della divisione di 70 per 29 è 12.
In definitiva il resto della divisione di 14! Per 29 sarà 12, come già visto precedentemente.
Ovviamente questi calcoli non si fanno manualmente ma con appositi programmi al computer.