Chapitre 5  Les entiers de Gauss et l’algorithme de Todd

Merci à Bernard Ycart de nous avoir envoyé le fichier de l’article de Raymond Seroul sur les formules à la machin et l’algorithme de Todd, paru en 1986 à l’IREM de Strasbourg.

5.1  ℤ[i] ou les entiers de Gauss ℤ[i]

5.1.1  La division euclidienne et le pgcd dans ℤ[i]

On rappelle que ℤ[i]={m+in, (m,n)∈ ℤ²}.
ℤ[i] est un anneau intègre euclidien.
Soient a ∈ ℤ[i] et b ∈ ℤ[i]−{0}, alors on dit que le quotient entier q de a par b est l’affixe du (ou des) point(s) le plus proche pour le module du point d’affixe a/b et alors le reste de la division euclidienne est r=a−bq.
On choisit q pour que bq soit le plus proche possible de a et on peut montrer que l’on peut choisir r=a−bq tel que |r|² ≤ |b|²/2.
Le pgcd dans ℤ[i] se calcule comme dans ℕ par l’algorithme d’Euclide.

5.1.2  Les fonctions iquo, irem iquorem et gcd de Xcas

Si a et b sont des entiers ou des entiers de Gauss :
iquo(a,b) renvoie le quotient q de la division euclidienne de a par b et
irem(a,b) renvoie le reste r de la division euclidienne de a par b.
q et r vérifient :
si a et b sont entiers a=bq+r avec 0 ≤ r<b
si a et b sont des entiers de Gauss a=bq+r avec |r|²) ≤ |b|²/2.
iquorem(a,b) renvoie la liste [q,r] du quotient et du reste de la division euclidienne de a par b .
gcd(a,b) renvoie le pgcd de a et b
Par exemple :
si a=−6+17i et si b=7+i on tape :
iquo(-6+17*i,7+i)
et on obtient : -1+3*i
irem(-6+17*i,7+i)
et on obtient : 4-3*i
iquorem(-6+17*i,7+i)
et on obtient : [-1+3*i,4-3*i]
Donc la division euclidienne de a par b a pour quotient −1+3i et pour reste 4−3i .
On tape : iquorem(7+i,4-3*i)
et on obtient : [1+i,0]
Donc 7+i est un multiple de 4−3i gcd(7+i,-6+17*i)
et on obtient : 4-3*i

5.1.3  Exercice

• Soit q∈ ℤ[i] tel que bq soit le plus proche possible de a et r=a−bq.
  Montrer que l’on peut choisir r tel que |r|² ≤ |b|²/2.
  
• Montrer que |q−a/b|² ≤ 1/2. En déduire que |a−bq|² ≤ |b|²/2 et que l’algorithme d’Euclide se termine lorsqu’on prend q comme quotient euclidien.
• Écrire un programme qui calcule le pgcd de 2 nombres de ℤ[i]. On normalisera le résultat (en multipliant le résultat par 1,-1,i ou -i) pour que le pgcd soit un nombre de partie rèelle strictement positive et de partie imaginaire positive ou nulle.

On tape :

quotient(a,b):={
local q1,q2,c;
c:=normal(a/b);
q1:=re(c);
q2:=im(c);
return round(q1)+i*round(q2);
}
:;
reste(a,b):={
local q;
q:=quotient(a,b);

return a-b*q;
}
:;

pgcdzi(a,b):={
local q,r;
tantque b!=0 faire
  q:=quotient(a,b);
  r:=a-b*q;
  a:=b;
  b:=r;
ftantque;
//on normalise
si re(a)<0 et im(a)<=0 alors retourne -a;fsi;
si im(a)<0 alors retourne i*a;fsi;
si re(a)<=0 alors retourne -i*a;fsi;
retourne a;
}:;

On tape :
pgcdzi(3+i,3-i)
On obtient :
1+i
On tape :
pgcdzi(7+i,-6+17*i
On obtient :
3+4*i

5.1.4  La fonction pa2b2 de Xcas

Théorème
Si p est un nombre premier de ℕ congru à 1 modulo 4, alors il existe deux entiers a et b tel que p=a²+b².
On tape :
pa2b2(89)
On obtient :
[5,8]
On tape :
pa2b2(317)
On obtient :
[11,14]
Idée de la preuve du théorème
Dans ce qui suit, p est un nombre premier de ℕ congru à 1 modulo 4.

• Lemme
  -1 admet une racine carrée modulo p.
  Preuve du lemme
  On rappelle le théorème de Wilson qui dit que si p≥ 3 est premier alors (p−1)!=−1 modp.
  (En effet ℤ/pℤ−{0} est un group multiplicatif donc si a=(p−1)! on a a²=1 modp car on peut associer chaque facteur de a avec son inverse dans ℤ/pℤ−{0}.Donc a²−1=(a−1)*(a+1)=k*p. Comme p est premier, p divise a−1 ou a+1.)
  Posons p=2q+1. Puisque p=1 mod4 on a q est pair.
  On a :
  q!=(q−p)(q−1−p)...(2−p)(1−p)modp=(−1)^q(q+1)(q+2)...(2q−1)(2q)modp donc :
  q!²=(1*2*...q)*((−1)^q(q+1)(q+2)...(2q−1)(2q)) modp donc puisque q est pair :
  q!²=(p−1)!modp=−1 modp On notera rac=q!modp.
  Par exemple pour p=5 rac=2, pour p=pour p=17 rac=13.
• On pose u=[1,rac] et v=[0,p] et on considère le réseau engendré par u et v : Λ=ℤ u+ℤ v. On cherche une autre base du réseau dont un vecteur est de longueur minimale. Quitte à échanger u et v, on peut supposer que v*v≤ u*u (* est le produit scalaire).
  On montre facilement que si on remplace (u,v) par (u+mv,v) avec m∈ ℤ, le réseau engendré est identique.
  On montre facilement que si w=[w₁,w₂]∈ Λ=ℤ u+ℤ v alors le produit scalaire w*w est divisible par p (on a en effet 1+rac²=0 modp donc :
  w*w=w₁²(1+rac²)+w₂²(p²)+2w₁w₂p*rac=0 modp).
  On montre facilement que tous les parallélogrammes engendrés par une base u₁ et v−1 du réseau ont une aire égale à p (car le produit vectoriel de u et v a comme longueur p et il est égal au produit vectoriel de u+mv et v et est aussi égal au produit vectoriel de v+mu et u).
  On choisit m∈ ℤ pour que la projection de w=u+m*v sur v soit dans ]−v/2,v/2] (i.e.−(v*v)/2<w*v=(u+m*v)*v≤ (v*v)/2 où * est le produit scalaire ou encore m=floor(1/2−u*v/v*v)=.
  On a alors w*w≤ u*u.
  En effet :
  v*v≤ u*u et
  |w*v|=(u+mv)*v≤ (v*v)/2 (d’après le choix de m
  Puisque u*v n’est pas dans le segment ]]−v*v/2;v*v/2 c’est que :
  soit u*v>v*v/2 et alors m<0
  soit u*v≤ −v*v/2 et alors m>0
  On a :
  w*w=(u+mv)*w=u*w++m*(v*w)==u*u+m(u*v+w*v)
  si m>0 alors u*v+w*v< −v*v/2+(v*v)/2≤ 0 et
  si m<0 alors u*v+w*v>v*v/2−(v*v)/2≥ 0 donc
  dans les 2 cas m(u*v+w*v)≤ 0 i.e. w*w≤ u*u
  On recommence l’opération jusqu’à ce que u soit dans la bande (m=0).
  On montre alors que la distance minimale entre 2 points du réseau est ègale à la norme du dernier v.
  En effet lorsque m=0 c’est que l’on est dans la situation suivante :
  v*v<=u*u et |u*v|≤ v*v/2 donc l’aire (égale à p/2) du triangle engendré par u et v est supérieure à l’aire du triangle équilatéral T de côté v. T a comme aire A=(v*v)*√3/4.
  
  Donc on a (v*v)*√3/2≤ p puisque :
  pour tous les nombres w du réseau, on a w*w est divisible par p donc si v=(a,b) on a v*v=a²+b²<2p et v*v est un entier divisible par p donc v*v=a²+b²=p.
  Remarque Lorsque l’algorithme s’arrête les vecteur u et v ont même norme et sont perpendiculaires.
  En effet lorsque l’algorithme s’arrête on a :
  1. v*v=p,
  2. |u*v|≤ v*v/2 donc si α est l’angle formé par u et v on a : cos(α)²≤ 1/4 ou sin(α)²≥ 3/4,
  3. u*u est divisible par p (u*u=kp avec k∈ℕ^*) et u*u≥ v*v,
  4. l’aire A du parallélogramme engendré par u et v vaut p
  5. v*v=p
  Or A²=sin(α)²(u*u)(v*v)=p²=sin(α)²(u*u)p
  Donc : sin(α)²(u*u)=p=sin(α)²kp
  Donc : k sin(α)²=1≥ 3k/4 avec k∈ℕ^*
  Ou encore k∈ℕ et k≤ 4/3 donc k=1 ce qui signifie que :
  u*u=p et sin(α)²=1 donc u*v=0
  

L’algorithme sur un exemple
On choisit p=13, et prenons rac =5 (puisque 5²=25=−1 mod13).
Dessinons quelques points du reseau en tapant :

reseau(p,rac):={
local L,j,k;
L:=NULL;
pour (j:=-2;j<=2;j++) {
  pour (k:=-3;k<=3;k++) {
    L:=L,point(k+i*(rac+k*p)+13*j);
  }
}
return affichage(L,epaisseur_point_2+1);
}:;

On commence avec u=1,rac et v=0,p. on réduit u,v ce qui veut dire que l’on échange u et v (car u*u<v*v), puis on remplace v par w=v−2*u,u afin que w soit dans la bande bleue.
On réduit w,u ce qui veut dire que l’on remplace w,u par u,w (car u*u>w*w) puis on remplace u par t=u−w afin que t soit dans la bande verte. On s’arrête et t et w sont de norme minimale (t*t=w*w=2²+3²=13).
L’algorithme

1. On écrit la fonction puissance rapide puiss(a,k,p) qui renvoie a^k modp (ou on utilise la fonction powmod de Xcas).
2. On écrit la fonction sqrtmod(p) qui renvoie une racine carrée de -1 modulo p lorsque p est congru à 1 modulo 4.
   Pour p=13, sqrtmod(13) qui renvoie 8.
3. On écrit la fonction reduire(u,v) qui prend en entrée deux vecteurs u et v de ℤ², qui échange u et v si v*v>u*u et renvoie m,u1,v1 tels que −(v*v)/2<u+m*v≤ (v*v)/2 (le produit étant le produit scalaire).
   Pour p=13, reduire([1,8],[0,13]) renvoie -2,[-2,-3],[1,8], (car [0,13]−2*[1,8]=[−2,−3])
   reduire([-2,-3],[1,8]) renvoie 2,[-3,2],[-2,-3] et
   reduire([-3,2],[-2,-3]) renvoie 0,[-3,2],[-2,-3]
   ou si on a pris rac=5
   reduire([1,5],[0,13]) renvoie -2,[-2,-3],[1,5] et
   reduire([-2,-3],[1,5]) renvoie -1,[-3,2],[-2,-3] et
   reduire([-3,2],[-2,-3]) renvoie 0,[-3,2],[-2,-3]
4. On écrit la fonction solpa2b2(p) qui renvoie deux entiers a et b tels que p=a²+b² lorsque p est premier et congru à 1 modulo 4.
   On itère pour cela la fonction reduire avec comme arguments initiaux u=[1,sqrtmod(p)] et v=[0,p] et on s’arrête quand m=0. On renvoie alors les coordonnées en valeurs absolues du dernier v. Pour p=13, solpa2b2(13) renvoie [3,2].

Traduction de l’algorithme en langage Xcas

puiss(a,k,p):={
local pui;
pui:=1;
while(k>0) {
if (irem(k,2)!=0){
pui:=irem(a*pui,p);
k:=k-1;}
a:=irem(a*a,p);
k:=k/2;
}
return pui;
}:;
sqrtmod(p):={
local j,k,a,r;
if (!isprime(p)) {return p+"n'est pas premier"};
k:=iquo(p-1,4);
r:=irem(p-1,4);
if (r!=0) {return "erreur"};
a:=2;
j:=puiss(a,k,p);
while (j == 1 or j==p-1){
a:=a+1;
j:=puiss(a,k,p);
}
return j;
}:;
reduire(u,v):={
local w,uv,m,v2;
if (u*u<v*v){
w:=u;
u:=v;
v:=w;
}
uv:=u*v;
v2:=v*v;
m:=floor(1/2-uv/v2);
return m,u+m*v,v;
}:;
solpa2b2(p):={
local u,v,m,rac;
rac:=sqrtmod(p);
u:=[1,rac];
v:=[0,p];
m,u,v:=reduire(u,v);
while (m!=0) {
m,u,v:=reduire(u,v);
}
return abs(v);
}:;

On tape :
solpa2b2(1009)
On obtient :
[15,28]
On tape :
pa2b2(1009)
On obtient :
[28,15]
On tape :
solpa2b2(1000033)
On obtient :
[408,913]
On tape :
pa2b2(1000033)
On obtient :
[913,408]
On tape :
solpa2b2(1000000009)
On obtient :
[3747,31400]
On tape :
pa2b2(1000000009)
On obtient :
[31400,3747]
On tape :
solpa2b2(1000000000061)
On obtient :
[848494,529205]
On tape :
pa2b2(1000000000061)
On obtient :
[529205,848494]

5.2  Les nombres irréductibles de ℤ[i]

5.2.1  Définitions et Théorème

Définition
On dit que a ∈ ℤ[i] est inversible si il existe b ∈ ℤ[i] tel que ab=1.
On dit que b ∈ ℤ[i] est associé à a ∈ ℤ[i] si il existe c ∈ ℤ[i] inversible tel que a=bc.
Exercice
Déterminer les éléments inversibles de ℤ[i].
Déterminer les associé de x+iy ∈ ℤ[i].
Solution
Si a=a₁+ia₂ ∈ ℤ[i] est inversible si il existe b=b₁+ib₂ ∈ ℤ[i] tel que ab=1.
Donc en égalant les modules :
1=(a₁²+a₂²)(b₁²+b₂²) comme a₁²+a₂² ∈ ℕ et b₁²+b₂² ∈ ℕ cela entraine que a₁²+a₂²=1 c’est à dire a∈ {1,i,−1,−i} Les associés de x+iy sont donc {x+iy,−x−iy,y+ix,y−ix}.
Définition
On dit que a ∈ ℤ[i] est irréductible si a est non inversible ou si a n’est le produit de 2 nombres appartenant à ℤ[i] que lorsque l’un de ces nombres est inversible.
Par exemple :
Les éléments inversibles de ℤ[i], {1,−1,i,−i}, ne sont pas irréductibles dans ℤ[i].
2 n’est pas irréductible dans ℤ[i] car 2=(1+i)*(1−i).
1+2i est irréductible car si 1+2i=(a₁+ia₂)(b₁+ib₂) alors en égalant le carré des modules on a :
5=(a₁²+a₂²)(b₁²+b₂²). Comme 5 est premier cela entraine que a₁²+a₂²=1 (ou b₁²+₂²=1) c’est à dire a∈ {1,i,−1,−i} (ou b∈ {1,i,−1,−i})
(1+i) est irreductible car si 1+i=(a₁+ia₂)(b₁+ib₂) en égalant le carré des modules on obtient :
2=(a₁²+a₂²)(b₁²+b₂²) donc (a₁²+a₂²)=1 et (b₁²+b₂²)=2 (ou (b₁²+b₂²)=1 et (a₁²+a₂²)=2 ) ce qui veut dire que (a₁+ia₂) est inversible et (b₁+ib₂) est l’associé de 1+i (ou (b₁+ib₂) est inversible et (a₁+ia₂) est l’associé de 1+i).
Théorème
Si dans ℤ[i] a irréductible divise bc alors a divise b ou a divise c.
Théorème
Si un entier de Gauss est irréductible alors l’un de ses associé est :

1. le nombre 1+i
2. x+iy où x²+y² est un nombre premier de ℤ congru à 1 modulo 4
3. un nombre premier de ℤ congru à 3 modulo 4

Ainsi un entier de Gauss z est irréductible de type 1 (z=1+i), de type 2 (z=x+iy où x²+y² est un nombre premier de ℤ congru à 1 modulo 4) ou de type 3 (z∈ℤ avec z congru à 3 modulo 4).
Démonstration
Soit a+ib un entier de Gauss est irréductible

1. Supposons que b=0 alors a+ib=p∈ ℤ
   Si p est irréductible, alors p est un nombre premier et p peut être :
   • congru à 3 modulo 4.
     Montrons qu’un nombre premier p∈ ℤ congru à 3 modulo 4 est irréductible dans ℤ[i].
     Raisonnons par l’absurde et supposons que p=(a₁+ia₂)(b₁+ib₂).
     En égalant le carré des modules on obtient :
     p²=(a₁²+a₂²)(b₁²+b₂²) Comme p est premier cela entraine que :
     a₁²+a₂²=p et que (b₁²+b₂²)=p puisque (a₁+ia₂) et (b₁+ib₂) ne sont pas inversibles, on sait que a₁²+a₂²≠ 1 et (b₁²+b₂²)=¬ 1.
     On a donc obtenu une contradiction puisque la somme de 2 carrés n’est jamais congru à 3 modulo 4.
     Donc un nombre premier p∈ ℤ congru à 3 modulo 4 est irréductible dans ℤ[i].
     
   • congru à 2 modulo 4.
     Montrons qu’un nombre premier p∈ ℤ congru à 2 modulo 4 n’est pas irréductible dans ℤ[i].
     Comme p est premier cela entraine que p=2.
     Puisque p=2=(1+i)*(1−i), p n’est pas irréductible dans ℤ[i]
   • congru à 1 modulo 4.
     Montrons qu’un nombre premier p∈ ℤ congru à 1 modulo 4 n’est pas irréductible dans ℤ[i].
     On sait que si p est un nombre premier congru à 1 modulo 4, il existe a et b dans ℕ tels qie p=a²+b² donc p=(a+ib)*(a−i*b) donc p n’est pas irréductible.
   
   Donc si p ∈ ℤ est irréductible dans ℤ[i] c’est que p est premier et congru à 3 modulo 4.
2. Soit un nombre a+ib irréductible dans ℤ[i] avec b≠ 0 ou a≠ 0. On en déduit que g=gcd(a,b)=1 car sinon a+i*b ne serait pas irréductible car on aurait (a+ib)=g*(a/g+ib/g). Montrons tout d’abord que p=a²+b² est un nombre premier de ℤ .
   On a p=a²+b²=(a+ib)(a−ib) avec a+ib irréductible dans ℤ[i] donc (a+ib) divise p₀ un diviseur premier de p dans ℤ . Il existe donc il existe c et d dand ℕ tels que :
   p₀=(a+ib)*(c+id) avec c²+d²≠ 1.
   En égalant le carré des modules on obtient :
   p₀²=(a²+b²)(c²+d²) où p₀ est un nombre premier de ℤ comme c²+d²≠ 1 et (a²+b²)≠ 1 (puisque b≠ 0 ou a≠ 0), on a p₀=a²+b²=c²+d². Donc si a+ib est irréductible dans ℤ[i] avec b≠ 0 ou a≠ 0 alors (a²+b²) est premier.
   Donc a²+b² est congru à 1 ou 2 modulo 4.
   Si a²+b² est congru à 2 modulo 4 c’est que a²+b²=2 (car (a²+b²) est premier) et alors a=1 et b=1 sinon a²+b² est congru à 1 modulo 4.

Exercice
Écrire un programme estirreductible, qui prend en entrée un entier de Gauss z et retourne son type (1, 2 ou 3) si z est irréductble, et 0 sinon.

estirreductible(z):={
local p,m,n;
m:=abs(re(z));
n:=abs(im(z));
//if(type(m)!=2 or type(n)!=2){return faux; }:
if (z*conj(z)==1){return 0};
if (m==0) {m:=n;n:=0;}
if (n==0) {if (m>2 and irem(m-3,4)==0){return 3; }};
if (m==1 and n==1) {return 1; };
p:=m^2+n^2;
if (est_premier(p) and irem(p-1,4)==0){return 2; } else {return 0;} 
}
:;

Exercice
Écrire un programme qui décompose un entier de Gauss en un produit de facteurs irréductbles.

decompose(z):={
local p,L1,L2,L3,s2,s0,s1,s3,k,c,lc,fc,j,z1,d;
L1:=NULL;
L3:=NULL;
//if (im(z)==0) {p:=abs(z);} else {p:=z*conj(z);}
p:=z*conj(z);
L2:=ifactors(p);
s2:=size(L2);
c:=L2[0];
s0:=0;
if (c==2) {L1:=L1,1+i,,L2[1];s0:=2;z:=z/(1+i);}
for (k:=s0;k<s2;k:=k+2) {
c:=L2[k];d:=L2[k+1];
if (irem(c-1,4)==0) {
   lc:=pa2b2(c);
   fc:=lc[1]+i*lc[0];
   j:=0;z1:=z;
   while(irem(z1,fc)==0) 
     {j:=j+1;
       z1:=z1/fc;
      }
     if (j!=0 and j!=d) {
     L1:=L1,fc,j,conj(fc),d-j;
     z:=z/fc^j;z:=z/conj(fc)^(d-j);}
else {
    if (j==0) {L1:=L1,conj(fc),d;z:=z/conj(fc)^(d-j)}
else {L1:=L1,fc,j;z:=z/fc^j;}}
}
if (irem(c-3,4)==0) {L3:=L3,c,d/2;z:=z/c^(d/2);}
}
if (z==1){
 return [L1,L3];}
 else
{return [z,1,L1,L3];}
}
:;

Ou bien, on utilise la commande ifactors ou la commande ifactor.

5.3  Les nombres décomposables

Définition
On dit que n ∈ ℤ − {−1,0,1} est décomposable, si pour tout diviseur premier p de 1+n² il existe d∈ ℕ vérifiant d<abs(n) et tel que 1+d² soit un multiple de p.
Par exemple
8 est décomposable car 1+8²=65=5*13 et on a 5 divise 1+2²=5 (d=2) et 13 divise 1+5²=26 (d=5).
17 est décomposable car 1+17²=290=2*5*29 et on a 2 divise 1+1²=2 (d=1) et 5 divise 1+2²=5 (d=2) et 29 divise 1+12²=145=29*5 (d=12).
6 est non décomposable car 1+6²=37=1*37 et on a 1 divise 1+2²=5 (d=2) mais 37 ne divise pas 1+d² quelque soit 0≤ d≤ 5 (car 37> (1+d²) lorsque 0≤ d≤ 5).
19 est non décomposable car 1+19²=362=2*181 et on a 2 divise 1+3²=10 (d=2) mais 181 ne divise pas 1+d² quelque soit 0≤ d≤ 18 (car 180 n’est pas un carré).
Exercice
Écrire une fonction Xcas estdecomposable, qui prend en entrée un entier n, et retourne le booléen vrai si n est d’ecomposable, faux sinon.
Et vérifier que les premiers entiers décomposables sont :
3,7,8,12,13,17,18,21,23,27,30

Les différentes solutions avec des algorithmes de plus en plus performents.

• Algorithme 0
  L’Algorithme 0 est un algorithme naif qui pour tout diviseur premier de 1+n² cherche l’existence de d par balayage (la variable t sert de test ). Avec cet algorithme, si n est décomposable on trouve le plus petit entier d :

  estdeconposable0(n):={
  local p,Lf,k,p1,d,t,s;
  n:=abs(n);
  p:=1+n^2;
  if (isprime(p)) {return faux};
  Lf:=ifactors(p);
  s:=size(Lf);
  for (k:=0;k<s;k:=k+2){
  p1:=Lf[k];
  d:=1;
  t:=0;
  while(t!=1 and d<n) {
  if (irem(1+d^2,p1)==0) {t:=1;afficher(d,p1);};
  d:=d+1;
  }
  if (t==0){return faux;}
  }
  return vrai;
  }:;
  

• Algorithme 1
  L’Algorithme 1 va faire appel aux nombres complexes.
  N=1+n² est la norme au carrée de z=1+i*n et soit p un diviseur premier de N.
  Donc p divise (1+in)(1−in).
  
  • p n’est pas congru à 3 modulo 4.
    En effet si p est congru à 3 modulo 4, p est irréductible dans ℤ[i] donc p divise 1+in ou 1−in. Cela veut dire qu’il existe x ∈ ℤ et y ∈ ℤ tel que p(x+iy)=1+in (ou p(x+iy)=1−in) ce qui est impossible car p diviserait 1 puisqu’en égalant les parties réelles on a p*x=1
  • p n’est pas congru à 0 modulo 4 car p est premier
  • p=2 ou p est congru à 1 modulo 4 En effet si p est congru à 2 modulo 4 c’est que p=2 car p est premier
  On sait que tout nombre premier p congru à 1 modulo 4 est la somme des carrés de 2 entiers donc il existe a∈ ℕ et b∈ N:
  p=a²+b².
  On cherche les entiers d qui sont tels que :
  p=a²+b²=(a+i*b)(a−i*b) divise 1+d²=(1+i*d)(1−i*d) donc
  on cherche les entiers d ∈ Z qui sont tels que :
  a+i*b divise 1+i*d c’est à dire tel qu’il existe u et v vérifiant :
  (a+ib)(u+iv)=1+i*d
  donc au−bv=1 et av+bu=d
  Tous les d sont congrus modulo p=a²+b² (car si au0−bv0=1 et au−bv=1 alors u=u0+k*b et v=v0+k*a)
  

  estdecomposable1(n):={
  local p,N,Lf,k,d,d1,a,b,L,a1,b1,s;
  n:=abs(n);
  N:=1+n^2;
  if (isprime(N)) {return faux};
  Lf:=ifactors(N);
  s:=size(Lf);
  for (k:=0;k<s;k:=k+2){
  p:=Lf[k];
  if (p!=2){
  //on irem(p,4)==1 et p premier
  a,b:=pa2b2(p);
  if (a!=1 and b!=1) {
  L:=iegcd(a,b);
  a1:=L[0];
  b1:=-L[1];
  d:=irem(b*a1+a*b1,p);
  d1:=irem(-b*a1-a*b1,p);
  //afficher(d,d1,p);
  };
  if (d>=n et d1>=n) {return faux;}
  }
  }
  return vrai;
  }:;
  

• Algorithme 2
  l’Algorithme 2 simplifie l’algorithme1 puisque n et −n se trouve être un d particuler, donc le plus petit d est égal à n modp ou à −n modp.

  estdecomposable2(n):={
  local p,N,Lf,k,d,a,b,d1,s;
  n:=abs(n);
  N:=1+n^2;
  if (isprime(N)) {return faux};
  Lf:=ifactors(N);
  s:=size(Lf);
  for (k:=0;k<s;k:=k+2){
  p:=Lf[k];
  if (p!=2){
  d:=irem(n,p);
  d1:=irem(-n,p);
  afficher(d,d1,p);}
  if (d1>=n et d >=n){return faux;}
  }
  }
  return vrai;
  }:;
  

• Algorithme
  L’Algorithme (le bon !!!!) utilise le théorme suivant :
  Théorème 1:
  Si p est premier et est congru à 1 modulo 4 alors il existe a et b tel que p=a²+b² et il existe u+iv unique tel que :
  (a+ib)(u+iv)=1+im avec m∈ ℤ, abs(m)<p/2 et u²+v²≤ 0.29p
  Cela entraine que si p est premier et congru à 1 modulo 4 alors il existe m ∈ ℤ tel que p divise 1+m² et m est unique dans ]−p/2;p/2[.
  Démonstration
  Soit p∈ ℕ un nombre premier congru à 1 modulo 4 il existe a et b tel que p=a²+b².
  On cherche u, v,m ∈ ℤ³ de valeur absolue la plus petite possible tels que :
  (a+ib)(u+iv)=1+im
  on a donc :
  au−bv=1 et av+bu=m. Puisque p=a²+b² est premier a et b sont premier entre eux donc il existe u et v (identité de Bézout) tels que :
  au−bv=1 et les solutions sont de la forme :
  u=u₀+kb v=v₀+ka k∈ ℤ où u₀,v₀ est une solution particulière de au−bv=1.
  On a donc :
  (a+ib)(u0+iv0+k(b+ia))=1+im
  (a+ib)(u0+iv0)+ik(a²+b²)=1+im
  Donc : m=av₀+bu₀+k(a²+b²) k∈ ℤ c’est à dire les m solutions sont ègaux modulo p.
  Comme a²+b²=p est impair on en déduit qu’il existe un m₀ et un seul tel que |m₀|<p/2 (m ∈ {(1−p)/2,..−1,0,1... (p−1)/2 }).
  Comme (a+ib)(u+iv)=1+im₀, on a (a²+b²)(u²+v²)=1+m₀²=p(u²+v²) Puisque p est un nombre premier congru à 1 modulo 4, on a p≥ 5 donc p²≥ 25 ou encore 1/p≤ p/25 donc :
  p(u²+v²)=1+m₀²<1+p²/4 donc
  (u²+v²)≤ 1/p+p/4<p/25+p/4=0.29p
  On tape :

  estdecomposable(n):={
  local p,N,Lf,k,d,d1,s,s1;
  n:=abs(n);
  N:=1+n^2;
  if (isprime(N)) {return faux};
  Lf:=ifactors(N);
  s:=size(Lf);
  p:=Lf[0];
  if (p==2){s1:=2} else {s1:=0};
  for (k:=s1;k<s;k:=k+2){
  p:=Lf[k];
  //on a irem(p,4)==1 et p premier
  if (abs(n)<p/2) {return faux;}
  }
  return vrai;
  }:;
  

On tape pour avoir la liste des nombres décomposables plus petit que n :

Lestdecomposable(n):={
local L,k;
L:=NULL;
for (k:=1;k<=n;k++){
if (estdecomposable(k)) {
L:=L,k;
}
}
return L;
}:;

Lestdecomposable(35)
On obtient :
3,7,8,13,17,18,21,30,31,32

5.4  Les nombres complétables

Definition :
On dit que le nombre z=a+ib est complétable si il existe u+iv ∈ ℤ[i] et m∈ ℤ tel que : (a+ib)(u+iv)=1+im .
Théorème2 :
Si a et b sont premiers entre eux alors z=a+ib est complétable. De plus, si a≠ 1 et b≠ 1, il existe u,v,m ∈ ℤ³ uniques tel que (a+ib)(u+iv)=1+im et |m|<(a²+b²)/2 et u²+v²<0.29(a²+b²).
De plus u et v sont premiers entre eux et donc u+iv et u−iv sont complétables.
Démonstration
C’est le théorème1 sans l’hypothèse p=a²+b² premier.
Tout d’abord 1+in et n+i sont complétables car (1+in)*1=1+in et (n+i)*(−i)=1−in et on a n<(1+n²)/2 si et seulement si n≠ 1.
Soient a≠ 1 et b≠ 1 premiers entre eux et z=a+ib.
On suppose donc que a²+b²≥ 5.
On a vu (cf th 1) que les m vérifiant (a+ib)(u+iv)=1+im sont congru modulo a²+b².
On va considérer 2 cas :

• a²+b² est impair i.e. a²+b²=2q+1
  il existe donc un m unique dans {−q,−q+1...−1,0,1,..q} donc
  m≤ q<q+1/2=(a²+b²)/2
• a²+b² est pair i.e. a²+b²=2q et q>2
  il existe donc un m unique dans {−q+1...−1,0,1,..q}.
  Mais on ne peut pas avoir m=q car alors on aurait :
  (a²+b²)(u²+v²)=2q(u²+v²)=1+q² donc q diviserait 1.
  Donc il existe un m unique dans {−q+1...−1,0,1,..q−1} donc :
  m≤ q−1<q=(a²+b²)/2.

Puisque a²+b²≥ 5 on a (a²+b²)²≥ 25 ou encore :
1/(a²+b²)≤ (a²+b²)/25 donc :
(a²+b²)(u²+v²)=1+m²<1+(a²+b²)²/4 donc
(u²+v²)< 1/(a²+b²)+(a²+b²)/4≤ (1/25+1/4)(a²+b²)=0.29(a²+b²).
Le programme complete ci-dessous a comme argument z=a+in et renvoie u+iv,1+im avec (a+ib)(u+iv)=1+im et −(a²+b²)/2<m<(a²+b²)/2

complete(z):={
local p,m,a,b,u,v,L;
a:=re(z);
b:=im(z);
p:=a^2+b^2;
if (gcd(a,b)!=1){ return faux;}
if (a==1) {return 1,1+i*b};
if (b==1) {return -i,1-i*a};
L:=iegcd(a,b);
u:=L[0];
v:=-L[1];
m:=irem(b*u+a*v,p);
if (m>p/2){m:=m-p;}
return u+i*v,1+i*m;
}:;

Si on veut une liste des nombres qui complétent le nombre complétable a+ib, on tape :

Lcomplete(z):={
local L,z1,a1,b1,d1,k,b,a ;
L:=complete(z);
z1:=L[0];
a1:=re(z1);
b1:=im(z1);
a:=re(z);
b:=im(z);
d1:=L[1];
return ([a1+k*b+i*b1+i*k*a,d1+i*k*abs(z)^2])$(k=-5..5);
}:;

5.5  L’algorithme de Todd

5.5.1  Le Théorème3

Soit n≥ 2 un entier décomposable (i.e. pour tout diviseur premier p de 1+n² et il existe d, 0<d<n, tel que p soit aussi un diviseur premier de 1+d²).
Il existe un entier M>1 et des entiers w_j (|w_j|<n) tels que :
M(1+in)=є(1+iw₁)^a₁(1+iw₂)^a₂...(1+iw_k)^a_k (є ∈ {1,−1,i,−i}).
Cette formule donne en égalant les arguments :
atan(n)=arg(є)+∑_j=1^ka_jatan(w_j)+mπ.
et puisque pour x>0 on a :
atan(x)+atan(1/x)=π/2
on a aussi :
atan(1/n)=−arg(є)+∑_j=1^katan(1/w_j)+q*π.
Soit n≥ 2 un entier décomposable. L’algorithme de Todd factorise 1+in et compléte par u+iv chaque facteur irréductible a+ib si a≠ 1 ou b≠ 1 pour avoir (a+ib)(u+iv)=1+im
Par exemple si (1+in)=(a+ib)*z1, on obtient :
(1+in)(u+iv)(u−iv)=(a+ib)(u+iv)(u−iv)z1 donc
(1+in)(u²+v²)=(1+im)(u−iv)z1
Si u==1 ou v==1 on s’occupe d’un autre facteur irréductible, sinon on compléte (u+iv)....
Comme (u²+v²)<0.29(a²+b²) u²+v² diminue à chaque complétion, donc l’algorithme s’arrête.

5.5.2  Un Exemple

On va montrer sur un exemple comment fonctionne l’algorithme de Todd.
Soit n=342 n est décomposable.
On tape :
ifactors(1+i*342)
On obtient :
[-1,1,2-i,1,10-7*i,1,11-6*i,1]
On a : −(2−i)=−2+i=i(1+2i)
Donc 1+342i=i(1+2i)(10−7i)(11−6i)
On tape :
complete(10-7*i)
On obtient :
-2+3*i,1+44*i
donc (10−7i)*(−2+3i)=1+44i
On tape :
complete(-2-3*i)
On obtient :
1+i,1-5*i
donc
(10−7i)(−2+3i)(−2−3i)(1+i)(1−i)=26(10−7i)=(1+44i)(1−5i)(1−i)
On tape :
complete(11-6*i)
On obtient :
-1+2*i,1+28*i
donc (11−6*i)(−1+2i)=1+28i
donc (11−6*i)(−1+2i)(−1−2i)=5(11−6*i)=(1+28i)(−1−2i)
Donc puisque −(2−i)=i(1+2i) on a :
5*26(1+342i)=i(1+2i)(1+44i)(1−5i)(1−i)(1+28i)(−1−2i)
130(1+342i)=−i(1−i)(1+2i)²(1−5i)(1+28i)(1+44i)

5.5.3  Exercice

1. Soit f(x)=atan(x)+atan(1/x).
   Déterminer le domaine de définition de f.
   Calculer f′(x) puis montrer que :

   atan(x)+atan(

   1 x

   )=

   π 2

   si x>0

   atan(x)+atan(

   1 x

   )=−

   π 2

   si xx0

2. Soit g(x)=atan(x+a/1−ax)−atan(x) pour a∈ ℝ Déterminer le domaine de définition de g.
   Calculer g′(x) puis montrer que :
   si ab<1 alors atan(a)+atan(b)=atan((a+b)/(1−ab)) et
   si ab=1 et a>0 alors atan(a)+atan(b)=π/2 et
   si ab=1 et a<0 alors atan(a)+atan(b)=−π/2.
   si ab>1 et a>0 alors atan(a)+atan(b)=π+atan((a+b)/(1−ab)) et
   si ab>1 et a<0 alors atan(a)+atan(b)=−π+atan((a+b)/(1−ab)).
3. En déduire que :
   atan(28)+atan(44)=π+atan(−72/1231)
   2atan(2)+atan(−5)=π+atan(−4/3)+atan(−5)=atan(19/17)
   π+atan(−72/1231)+atan(19/17)=π+atan(341/343) donc
   atan(−1)+2atan(2)−atan(5)+atan(28)+atan(44)=π+atan(−1)+atan(341/343)=
   π−atan(1/342)=π/2+atan(342)
   Donc puisque atan(−1)=−π/4 et puisque pour x>0 on a :
   atan(x)+atan(1/x)=π/2 on obtient :
   atan(342)=−3π/4+2atan(2)−atan(5)+atan(28)+atan(44)
   Donc puisque pour x>0 on a atan(x)+atan(1/x)=π/2
   atan(1/342)=−π/4+2atan(1/2)−atan(1/5)+atan(1/28)+atan(1/44)

5.5.4  Un programme qui simplie les formules précédentes

On peut écrire un petit programme ajuste pour simplifier : ∑_j=1^ka_jatan(w_j).
ajuste a comme argument la liste formée par les arguments w_j des arcs tangentes en répétant a_j fois w_j et renvoie C,a tel que :
∑_j=1^ka_jatan(1/w_j)=C+atan(a).
Par exemple pour la formule :
atan(−1)+2atan(2)−atan(5)+atan(28)+atan(44). on met comme argument la liste L:=[-1,2,2,-5,28,44] et ajuste(L) renvoie pi,-1/342.
On définit f la fonction f par :
f(a,b):=(a+b)/(1-a*b);
Pour simplifier atan(a)+atan(b), on écrit tout d’abord la fonction simpl(a,b) qui renvoie C,c tel que :
atan(a)+atan(b)=C+atan(c)
Puis, on écrit ajuste(L) qui renvoie C,c tel que :
∑_jatan(L[j])=C+atan(c)

f(a,b):=(a+b)/(1-a*b);
simpl(a,b):={
local s;
if (a==0) {return 0,b;}
if (b==0) {return 0,a;}
s:=sign(a);
if (a*b==1) {return s*pi/2,0;}
if  (a*b<1) {return 0,f(a,b);}
if  (a*b>1) {return s*pi,f(a,b);}
}:;
ajuste(L):={
local s,a,b,C,c,ajou,k;
ajou:=0;
s:=size(L);
a:=L[0];
k:=1;
while (k<s){
b:=L[k];
C,c:=simpl(a,b);
ajou:=ajou+C;
a:=c;
k:=k+1;
}
return normal(ajou),a;
}:;

On tape : ajuste([-1,2,2,-5,28,44])
On obtient : pi,-1/342
Donc :
atan(342)+π/2=atan(−1/342)+π=atan(−1)+2*atan(1/2)−atan(1/5)+atan(1/28)+atan(1/44)
Donc :
atan(342)=−π/2+atan(−1)+2*atan(2)−atan(5)+atan(28)+atan(44)
On tape : ajuste([-1,1/2,1/2,-1/5,1/28,1/44])
On obtient : 0,1/342
Donc :
atan(1/342)=atan(−1)+2*atan(1/2)−atan(1/5)+atan(1/28)+atan(1/44)
Remarque
En utilisant Lcomplete(11-6*i) on voit que:
(11−6i)(5−9i)=1−129i
On peut aussi utiliser cette complétion car 123<342/2 et 5²+9²=106<342/3.
On tape :
complete(5+9i)
On obtient :
2+i,1+23*i
Donc (5+9i)(2+i)=1+23i
Donc on a :
(11−6i)(5−9i)(5+9i)(2+i)(2−i)=5*106(11−6i)=(1−129i)(1+23i)(2−i)
On obtient alors :
1+342i=i(1+2i)(10−7i)(11−6i)
5*106*26(1+342i)=i(1+2i)(1+44i)(1−5i)(1−i)(1−129i)(1+23i)(2−i)
13780(1+342i)=(1−i)(1+2i)²(1−5i)(1+23i)(1+44i)(1−129i)
Donc :
atan(342)=−π/4+2atan(2)−atan(5)+atan(23)+atan(44)−atan(129)
Donc puisque pour x>0 on a atan(x)+atan(1/x)=π/2 on a :
atan(1/342)=−π/4+2atan(1/2)−atan(1/5)+atan(1/23)+atan(1/44)−atan(1/129)
On tape : ajust([-1,2,2,-5,23,44,-129])
On obtient : 0,1/342
On tape : ajust([-1,1/2,1/2,-1/5,1/23,1/44,-1/129])
On obtient : 0,-342
Traduction de l’algorithme de Todd en langage Xcas

 
todd(n):={
 local L,k,s,s1,z,R,Z,Zc,zc,p;
 //if (estcompletable(n)==faux) {return faux;};
 L:=ifactors(1+i*n);
 s:=size(L);
 R:=NULL;
 p:=1;
 for (k:=2;k<s;k:=k+2){
  z:=L[k];
  if (im(z)^2==1 or re(z)^2==1) {
    R:=R,z,L[k+1];}
  else {
    Z:=complete(z);
    R:=R,Z[1],L[k+1];
    zc:=conj(Z[0]);
    p:=p*abs(zc)^(2*L[k+1]);
    while (re(zc)^2!=1 and im(zc)^2!=1){
      Zc:=complete(zc);
      R:=R,Zc[1],L[k+1];
      zc:=conj(Zc[0]);
      p:=p*abs(zc)^(2*L[k+1]);
    }
    R:=R,zc,L[k+1];
  }
 }
 return normal(p),[L[0],1,R];
}:;

On tape :
todd(342)
On obtient :
130,[-1,12-i,1,1+44*i,1,1-5*i,1,1-i,1,1+28*i,1,-1-2*i,1]
On tape :
todd(266)
On obtient :
1850,[i,1,1-80*i,1,1+6*i,1,1-143*i,1,-1+7*i,1]

5.6  Pour obtenir une formule de type Machin

Une formule de type Machin est une formule qui ressemble à :

avec 0<wj<n Si le but est d’obtenir une formule avec des arcs tangentes, on modifie l’algorithme précédent pour avoir seulement comme résultat la liste des w_j compté avec leur multiplicité.
On tape :

 
todd2(n):={
local L,k,s,s1,z,R,Z,Zc,zc,p,RR;
//if (estcompletable(n)==faux) {return faux;};
L:=ifactors(1+i*n);
s:=size(L);
R:=NULL;
p:=1;
for (k:=2;k<s;k:=k+2){
z:=L[k];
if (im(z)^2==1 or re(z)^2==1) {R:=R,z,L[k+1];}
else {Z:=complete(z);
R:=R,Z[1],L[k+1];
zc:=conj(Z[0]);
p:=p*abs(zc)^(2*L[k+1]);
while (re(zc)^2!=1 and im(zc)^2!=1){
Zc:=complete(zc);
R:=R,Zc[1],L[k+1];
zc:=conj(Zc[0]);
p:=p*abs(zc)^(2*L[k+1]);
}
R:=R,zc,L[k+1];
}
}
RR:=NULL;
s:=size(R);
for (k:=0;k<s;k:=k+2){
if (re(R[k])^2!=1){R[k]:=i*R[k];}
RR:=RR,(re(R[k])*im(R[k]))$(R[k+1]);
}
return sort(RR);
}
:;

On tape :
todd2(342)
On obtient :
-5,-1,2,2,28,44
On tape :
ajust(todd2(342))
On obtient :
0,1/266
Donc :
atan(1/342)=atan(−1/5)+atan(−1)+2atan(1/28)+atan(1/44)
On tape :
todd2(266)
On obtient :
-143,-80,-7,6
On tape :
ajust(todd2(266))
On obtient :
0,1/266
Donc :
atan(1/266)=atan(−1/143)+atan(−1/80)+atan(−1/7)+atan(1/6)