In rete http://www.elegio.it/omnia/js/primi-pitagorici.html

Chiamo pitagorici ( come ad esempio 1000003 che è facile da ricordare ) i numeri primi esprimibili nella forma 4*N*N+3

In pratica li chiamo pitagorici se i primi sono congrui a 3 modulo 4 ossia, in stile Javascript, se il primo Pr è tale per cui  Pr%4 = 3

Li chiamo primi pitagorici perché usando loro come modulo, la somma di due quadrati di numeri non entrambi nulli o multipli del modulo usato, dunque nulli a livello modulare, NON DÀ MAI UN RISULTATO NULLO !

[1] Ora 19 Cliccami

0. ...Attivare Javascript per vedere...

La ragione per cui trovo interessante questi tipi di numeri primi

La mia congettura ( dovrei trovare chi me la dimostri rigorosamente ) viene qui verificata con tanti numeri primi esprimibili nella forma  pr = 4·N2 + 3  per cui è ragionevole giudicarla ben fondata.

La congettura è questa:

(X2 + Y2)%(4·N2 + 3) > 0 ;
se X ed Y non sono entrambi congrui a 0 e se (4·N2 + 3) è un numero primo.

Questa proprietà NON VALE PER QUALUNQUE NUMERO PRIMO ma è molto utile che valga almeno per questi tipi di numeri primi perché in questo modo l'algebra modulare conserva una proprietà evidente ed importante dell'algebra dei numeri reali.

Questa proprietà ( per quanto ne so ) non vale se i quadrati sommati sono più di due e questa è una importante differenza di comportamento dell'algebra modulare rispetto a quella classica dei numeri reali.

Detto F un qualsiasi intero che potrebbe essere il risultato del calcolo di una qualsiasi funzione, vale allora questa disuguaglianza:

((F + 2·N)2 + 22)%(4·N2 + 3) = (F2 + 4·F·N + 4·N2 + 4)%(4·N2 + 3) > 0 ;
ossia
(F2 + 4·N·F + 1)%(4·N2 + 3) > 0 ;

Se dunque  F  è molto piccolo rispetto ad  N  diventa irrilevante il termine  F2  e quell' 1 usato per garantire il non annullamento dell'intera espressione.

Per esempio la  F  potrebbe essere il quadrato di una distanza ossia:

F = X2 + Y2 + Z2 dove purtroppo nasce il problema di fare la radice quadrata in algebra modulare dato che non sempre, in algebra modulare, un numero è un così detto residuo quadratico ma a questo ostacolo si potrebbe trovare un rimedio sottraendo alla  F  il più piccolo intero che trasformi l'espressione in un residuo quadratico ( https://it.wikipedia.org/wiki/Residuo_quadratico ).

Per capire se un numero è un residuo quadratico basta usare il criterio di Eulero ossia vedere qui: https://it.wikipedia.org/wiki/Criterio_di_Eulero ossia bisogna disporre di una funzione capace di fare la potenza modulare di una data base.

Per esempio, scrivendo nel linguaggio di wxMaxima ( http://www.elegio.it/max/ )

   pr:1000003;
   primep(pr);
   mod(pr,4);
   ini:random((pr-1)/2);
   lista: [ini+1,ini+2,ini+3,ini+4,ini+5,ini+6,ini+7,
   ini+8,ini+9,ini+10,ini+11,ini+12]$
   map(lambda([a],jacobi(a,pr)),lista);

ossia se si usa la funzione jacobi(a,pr) applicata a tutti gli elementi della lista, si ottiene un risultato di questo tipo:

   1000003
   true
   3
   [1,-1,1,-1,1,-1,1,-1,-1,1,-1,1]

dove gli 1 indicano che il numero è un residuo quadratico mentre se il risultato è -1 il numero NON è un residuo quadratico ossia non esiste un intero che, elevato al quadrato, sia uguale a lui modulo il numero primo usato, in questo caso 1000003.

Con i primi pitagorici ed usando la funzione di elevamento a potenza modulare è molto facile fare la radice quadrata:

   base:1+random(1000)$
   print("Uso questa base ",base)$
   primo:1000003$
   eulertest:power_mod(base,(primo-1)/2,primo)$
   print("Test di Eulero ",eulertest,
   " ( se vale 1 la base ha una radice quadrata )")$
   rbase:power_mod(base,(primo+1)/4,primo)$
   nrbase:mod(rbase*(primo-1),primo)$
   if is(eulertest=1) then(
   print(rbase," uso la prima radice e ottengo ",
   mod(rbase*rbase,primo)),
   print(nrbase," uso la seconda radice e ottengo ",
   mod(nrbase*nrbase,primo)))
   else(print("La base ",base," non ha radice quadrata"))$

Dunque si vede che i numeri che hanno radice quadrata sono piuttosto frequenti e dunque basta modificare di un piccolo intero un numero che non ha radice quadrata per trovarne uno che la ha.

Importante funzione da usare è la funzione che effettua l'elevamento a potenza modulare ossia in wxMaxima la power_mod(ba,es,pr).

In Javascript la inversamod e la pover_mod ribattezzata potemod si fa così:

//
// Inversa modulare ( L'algoritmo di Euclide )
//
function inversamod(a,bprimo){
    var p,d,t,q=0;
    var x=0,y=1,z=0,v=1,w=0;
    p=Math.round(Math.abs(bprimo));
    t=p;d=Math.round(Math.abs(a))%p;
    while(t!=0){
        z=d%t; q=(d-z)/t; d=t; t=z;
        z=x; x=v-q*x; v=z;
        z=y; y=w-q*y; w=z;
        }
    return ((v+p)%p);}
//
// Potenza modulare. La base elevata all'espon
// lavorando modulo il primo.
//
function potemod(base,espon,primo){
   var j,a,n,resto,v=1,p=Math.round(Math.abs(primo));
   a=Math.round(Math.abs(base));
   n=Math.round(espon);
   if(0>n){n=(n+(p-1)*(p-1))%(p-1);}
   else{n=n%(p-1)};
   for(j=0;p>j;j++){
      resto=n%2;
      if(resto==1) v=(a*v)%p;
      a=(a*a)%p;
      n=(n-resto)/2;
      if(n==0) break;
      }
   return v;}

Trascrivo qui anche la funzione che calcola la coppia di radici quadrate, se esistono:

function sqrtmod(nq,npr){
   var pr,bs,eulertest,rbs,nrbs;
   var powmod=function(base,espon,primo){
       var j,a,n,resto,v=1,
           p=Math.round(Math.abs(primo));
       a=Math.round(Math.abs(base));
       n=Math.round(espon);
       if(0>n){n=(n+(p-1)*(p-1))%(p-1);}
       else{n=n%(p-1)};
       for(j=0;p>j;j++){
          resto=n%2;
          if(resto==1)v=(a*v)%p;
          a=(a*a)%p;
          n=(n-resto)/2;
       if(n==0)break;}
       return v;}
   bs=Math.round(Math.abs(nq));
   pr=Math.round(Math.abs(npr));
   if(pr%4!=3)return[false,1,1,bs,pr,
     "Il primo "+pr+" non \u00e8 congruo a 3 modulo 4 "];
   eulertest=powmod(bs,(pr-1)/2,pr)
   if(eulertest!=1)return[false,1,1,bs,pr,
     "Il numero "+bs+" non \u00e8 un residuo quadratico "];
   rbs=powmod(bs,(pr+1)/4,pr);
   nrbs=(rbs*(pr-1))%pr;
   return [true,rbs,nrbs,bs,pr," Fatto! Riottiene: "+
     ((rbs*rbs)%pr)+" e "+((nrbs*nrbs)%pr)]
   }

Ho evidenziato questa funzione a scopo didattico di Javascript non per essere inutilmente prolisso ma per una ragione precisa. Va notato che la funzione sqrtmod contiene, a sua volta la definizione della funzione powmod ossia, in Javascript è possibile creare funzioni che contengono funzioni che dunque possono essere anche varianti di funzioni già definite nell'ambiente globale ma personalizzate per l'uso che ne fa la funzione che contiene quella sua variante.

E questo piccolo documento potrebbe essere ritenuto interessante come applicazione di una tecnica di programmazione di Javascript applicata a calcoli lunghi anche di parecchie ore...
Qui l'eventuale calcolo lungo viene spezzato in molte fasi brevi in modo da cedere temporaneamente il controllo al browser ed evitare che il PC resti bloccato fino al termine del calcolo lungo, magari, varie ore...