P = x ^ 2 + y ^ 2 EQUATION P = x ² + y ² with P prime number and x and y positive integers.
We can divide the primes into two broad families: those of the form 4n + 1 and those of the form 4n + 3. The former can be represented in exactly one way as the exact sum of two squares, the latter in any way. For example, the prime number 89 is of the form 4n + 1, in fact 89 = 4 * 22 + 1. It can be expressed in one way as the sum of two squares accurate, in fact 89 = 5 ² + 8 ². The number is 71 instead of the form 4n + 3 (71 = 4 * 17 +3) and can not in any way be represented as the sum of two squares accurate.
To solve the Diophantine equation P = x ² + y ² must first solve the congruence:
z ² ≡ -1 (mod P). (1)
This congruence has solutions only if P is of the form 4n + 1. There are two solutions, and if we call them A and B, are such that A + B = P.
For example, if P = 29, the two solutions of the congruence are 12 and 17, in fact:
12 ² + 1 = 145 divisible by 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 solution is easily found: B = P - A = 29 - 12 = 17.
A solution of (1) that involves numbers a bit 'is not great:
t ^ ((p-1) / 4) Form P
where t is any non-residual square of P ^ and the symbol indicates high a.
always in the case of P = 29, its not a quadratic residue is 2. we have:
2 ^ 7 = 128
The rest of the division of 128 to 29 is here again 12.
Recall that a quadratic residue of a prime number P is the remainder of the division of an exact square with P and that all prime numbers have (P-1) / 2 quadratic residues and (P-1) / 2 quadratic residues not.
Once you find the solutions A and B (1) you can easily solve the ' equation P = x ² + y ² proceeding as follows:
Let A be the greater of A and B. We calculate the remainder R Division A to B. If R * R <>
= R x, y = sqr (P-R * R) (sqr indicates the square root).
If R * R> P then we must repeat the process: it calculates the remainder of the division of B to R and so on.
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 <>
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 and x and y integers
Compute ((P-1)) / 2)! and divide by P. Let A be the rest of this division. Let B = PA.
Let A be the greater of A and B. We calculate the remainder R Division A to B. If R * R <>
= R x, y = sqr (P-R * R) (sqr indicates the square root).
If R * R> P then we must repeat the process: it calculates the remainder of the division of B to R and so on.
Note that if P is not of form 4n +1 (P = 4n + 3) the equation has no solutions and the method results would then unpacked!
The problem is that ((P-1) / 2)! It is a huge number, then steps should be as follows:
You can directly calculate the remainder of the division of ((p-1) / 2)! For P:
Learn how to calculate 1 * 3 * 4 * 5 ... .. until its value exceeds P. As soon as this value P is calculated over the rest of the division by R P. Then you start to calculate the factorial already computed without the words starting with R:
R * m * (m +1) * (m +2) .... And as soon as this value has exceeded P, stop and calculate the rest of the division by P and so on.
Example: compute the remainder of the division of ((29-1) / 2)! For 29:
1 * 2 * 3 * 4 * 5 = 120> 29
The rest of the division of 120 to 29 is 4.
4 * 6 * 7 = 168> 29
The rest of the division of 168 to 29 is 23.
23 * 8 = 184> 29
The rest of the division of 184 to 29 is 10.
10 * 9 = 90> 29
The rest of the division of 90 to 29 is 3.
3 * 10 = 30> 29
The rest of the division of 30 to 29 is 1.
1 * 11 * 12 = 132> 29
The rest of the division of 132 to 29 and 16.
16 * 13 = 208> 29
The rest of the division of 208 to 29 is 5.
5 * 14 = 70> 29
The rest of the division of 70 to 29 is 12.
In short, the remainder of the division of 14! Will be 12 to 29, as discussed above.
Obviously these calculations are not made by hand. On the site there are many programs that are downloaded from the following steps:
http://teoriadeinumeri.blogspot.com/2009/03/103-programmi-gratis.html
