nombre premier somme de 2 carrés

donnet

Bonjour

Quelqu'un connaît-il une méthode éprouvée et simple pour décomposer un nombre premier de la forme 4N+1 en une somme de deux carrés a²+b²=c ?

Ce que j'ai trouvé ou retrouvé :
cela sera toujours la somme d'un carré pair et d'un carré impair.

Je considère deux cas
1er cas 2*K pair (*K<2*K+1)
je fais varier les nombres a de 1 à 2*K et les nombres b et 2*K+1 à 4*K
de façon qu'à chaque nombre a =2*K-n corresponde un nombre b=2*K+1+n
(a+b est toujours égal à 4*K+1).

J'obtiens l'égalité suivante
(2*K-n)²+ (2*K+1+n)² =4*K²+(2K+1)² +(4*(n*(n+1))/2

4*K²+(2K+1)² est la plus petite somme de deux carrés a²+b² pour la famille des nombres correspondant au cas considéré.

Les résultats sont semblables dans le cas impair 2*K'-1 et 2*K'
(2*K'-1-n)²+(2*K'+n)²=(2*K'-1⁾²+(2*K')²+(4*(n*(n+1))/2
cela permet de déterminer a et b on retranche à (c-1)/4 la somme des n premiers nombres et on compare au minimum
4*K²+(2K+1)² si on trouve cette valeur Alors a=2*K-n b=2*k +1+n.
sinon on passe K pair ou K' impair suivant.

les limites sont fixées par (c-1)/4>K*(2*K+1)(pour les cas pairs) ou (2K-1)*K pour les cas impair
et (c-1)/4<4*K²( pour les cas pairs) et (2*K-1) pour les cas impairs
Bien sur le nombre de possibilités augmente avec K/
Mais un tout petit programme simple vient à bout de l'affaire.

Merci de vos commentaires ou autres solutions.
Courtoisement
Serge Donnet

GaBuZoMeu

Il y a la méthode suivante :
Soit $p$ premier congru à $1$ modulo $4$. On trouve $x$ racine carrée de $-1$ modulo $p$. On calcule, dans les entiers de Gauss, le pgcd de $p$ et de $x+i$.

flipflop

Pour le pgcd on dispose d'un algorithme car l'anneau des entiers de Gauss est Euclidien.

Exemple : $p=677$.

il faut trouver une racine de $-1$ dans $\Z / p\Z$ ... on trouve $26$.

Ensuite il faut trouver le plus grand commun diviseur entre $677$ et $26+i$ dans $\Z[ i]$. Là on a de la chance car la norme de $26+i$ est $677$ de sorte que $26+i$ divise $677$ et le pgcd est $26+I$. Donc $677 = 26^2+1^2$.

Par contre, $p = 409$. On trouve $143$ racine de $-1$ donc il faut trouver le pgcd de $409$ et de $143+i$ ...

donnet

bonjour

merci flipflop et GaBuZoMeu de votre solutionpour la décomposition d'un premier en somme de 2 carrés

une derniére question si on prend le produit de trois nombres premiers ( ou plus) par exemple 1105=5*13*17
on trouve que 1105 est la somme de deux carres de 4 façons différentes.
9²+32²
12²+31²
24²+23²
4²+33²
On peut opérer pour les trois nombres premiers de base comme vous indiquez
et faire toutes les combinaisons avec
l'identité classique (a²+b²)*(c²+d²)=(ab+cd)²+(ad-bc)²
ou=(ab-cd)²+(ad+bc)²

Mais je ne perçois pas comment faire autrement pour obtenir de façon exhaustive toues les solutions

Avez vous une proposition

courtoisement

Sd

GaBuZoMeu

L'identité classique que tu cites permet d'obtenir les quatre façons que tu explicites. Alors, quel est ton problème ?

donnet

Cher GaBuZoMeu

je me demandais seulement s'il n'y avait pas une autre façon "plus directe "d'y arriver.


courtoisement

sd

flipflop

Salut,

Tu veux compter le nombre de solution ou bien les construire ? Dans tous les cas, l'arithmétique de l'anneau des entiers de Gauss permet de faire des choses ! Tu connais $\Z[ i]$ l'ensemble des nombres complexes $z=a+ib$ avec $a$ et $b$ des ENTIERS ?

Par exemple, ton identité classique $(a^2+b^2)\times(c^2+d^2)=(ab+cd)^2+(ad-bc)^2$ est simplement l'identité de multiplicativité de la norme :
$$
z := a+ib \quad z' := c+id \quad \text{Alors} \quad N(z)N(z') = N(zz') \qquad \text{Avec} \quad N(x+iy) = x^2+y^2
$$
Du coup, je trouve une petite erreur dans ta formule ! Perso, j'ai
$$
(a^2+b^2)\times(c^2+d^2)=(ac-bd)^2+(ad+bc)^2
$$

Tu peux regarder un peu s'il n'y a pas une coquille dans ton identité classique ?

noix de totos

Petite ingérence de ma part dans ce fil...

Si l'on ne souhaite que compter les solution, alors l'identité suivante est bien connue : $r_2 = 4 \left( \chi_4 \star \mathbf{1} \right)$, où $\chi_4$ est le caractère primitif réel de Dirichlet modulo $4$ (voir par exemple l'ouvrage d'Hardy \& Wright).

GaBuZoMeu

Ce qui veut dire, pour qui n'a pas Hardy & Wright sous la main ?

PS. Je vois comment compter en utilisant la décomposition en facteurs premiers dans l'anneau des entiers de Gauss, mais je doute qu'un non-arithméticien comprenne ce que tu écris.

donnet

bonsoir

flipflop, mes excuses pour la faute dans l'identité de Diophante qui s'écrit comme tu l'indiques:

(a²+b²)*(c²+d²)=(ac+bd)²+(ad-bc)²
ou=(ac-bd)²+(ad+bc)²

Ah!que ne ferai-je sans vos lumières .Cela me donne une furieuse envie de me remettre à l'arithmétique modulaire à 72 ans.

Mille mercis et courtoisement
Serge Donnet

noix de totos

OK. $\chi_4(n) = (-1)^{(n-1)/2}$ pour tout $n$ impair (et $0$ si $n$ est pair) et $(\chi_4 \star \mathbf{1})(n) = \displaystyle \sum_{d \mid n} \chi_4(d)$.

(J'avais déjà indiqué cette identité il y a quelques mois, il me semble, non ?)

Plus généralement, si $K$ est un corps quadratique de caractère de Dirichlet associé $\chi$, et si $r_K(n)$ désigne le nombre d'idéaux entiers non nuls de norme $n$, alors $r_K = \chi \star \mathbf{1}$, où le produit de convolution de Dirichlet est donné par $(f \star g)(n) = \displaystyle \sum_{d \mid n} f(d) g(n/d)$.

flipflop

Salut,

J'ai lu ton message, no soucis 72 ans c'est cool de refaire un peu de calcul !

Par contre, tu n'as pas répondu aux petites questions. Tu veux compter ou les trouver les solutions ? Et également, est-ce que tu connais $Z[ i]$ ?

Un petit lien : [url=http://math.univ-lyon1.fr/~caldero/Z[ i].pdf ]ici[/url]

donnet

Bonsoir cher Flipflop

Ce que je recherche est une méthode donnant toutes les décompositions possibles.
Par conséquent il faut en connaître le nombre.
Jje sais maintenant depuis deux jours compter les solutions avec R₂(n) (grâce aux indications de Poirot).

J'ai une connaissance scolaire un peu vieille sur les nombres complexes, je suis en train de lire le Pdf de Caldero sur l'anneau des entiers de Gauss que tu m'as indiqué,
et aussi un cours d'arithmétique de Alberto Mingez.
www.math.jussieu.fr/~minguez/Enseignement/.../LM220_trois_derniers cours .pdf.
Et ensuite je réessayerai de gamberger à partir de mes trinômes diviseurs en particulier ceux à coefficients de Fibonacci
Courtoisement.
sd.

flipflop

Bonjour Donnet,

Ok. Pour $R_2(n)$ il faut quand même comprendre ce que signifie $R_2(n)$.

Par exemple, si je prends $n=5$.

$R_2(5) = ?$, et combien il y a de "décomposition" de $5$ en somme de deux carrés ?

Est-ce que ça correspond bien ?

claude quitté

@Donnet, flip-flop
Désolé, mais quand j'ai vu les objets :
$$
x^2 + y^2, \qquad r_2(n), \qquad \theta_{1,0,1}(q) = \sum_{x,y \in \Z} q^{x^2 + y^2} = \Bigl(\sum_{n \in \Z} q^{n^2}\Bigr)^2 = \sum_{n \ge 0} r_2(n)q^n ,
\qquad \hbox {...etc...}
$$
j'ai pas pu m'en empêcher. Je vais quand même donner $r_2(5)$ pour dire que je reste dans le sujet.

> Qminus4 := BinaryQuadraticForms(-4) ;                                                                       
> Qminus4 ;
Binary quadratic forms of discriminant -4
> q101 := Qminus4 ! 1 ;
> q101 ;
<1,0,1>
> Lattice(q101) ;
Standard Lattice of rank 2 and degree 2
> GramMatrix(Lattice(q101)) ;
[1 0]
[0 1]
> QuadraticForm(GramMatrix(Lattice(q101))) ;
x1^2 + x2^2
> T101<q> := ThetaSeries(q101, 50) ; 
> T101 ;
1 + 4*q + 4*q^2 + 4*q^4 + 8*q^5 + 4*q^8 + 4*q^9 + 8*q^10 + 8*q^13 + 4*q^16 + 8*q^17 + 4*q^18 + 8*q^20 + 12*q^25 + 8*q^26 + 8*q^29 + 4*q^32 + 
    8*q^34 + 4*q^36 + 8*q^37 + 8*q^40 + 8*q^41 + 8*q^45 + 4*q^49 + 12*q^50 + O(q^51)
> 
> &+[q^(n^2) : n in [-5..5]] ;                                                                                
1 + 2*q + 2*q^4 + 2*q^9 + 2*q^16 + 2*q^25
> (&+[q^(n^2) : n in [-5..5]])^2 ;
1 + 4*q + 4*q^2 + 4*q^4 + 8*q^5 + 4*q^8 + 4*q^9 + 8*q^10 + 8*q^13 + 4*q^16 + 8*q^17 + 4*q^18 + 8*q^20 + 12*q^25 + 8*q^26 + 8*q^29 + 4*q^32 + 
    8*q^34 + 8*q^41 + 4*q^50

Et voici $r_2(n)$ relié au caractère quadratique donné par noix de totos, caractère que j'écris plutôt $\chi_{-4}$ (indexation par le discriminant $-4$) :
$$
r_2(n) = 4\ \sum_{d \mid n} \chi_{-4}(d)
$$
Ce qui équivaut à :
$$
r_2(n) = 4(\delta_{4,1}(n) - \delta_{4,3}(n)) \qquad
\hbox {$\delta_{4,i} = $ nombre de diviseurs $d$ de $n$ vérifiant $d \equiv i \bmod 4$}
$$

> r_2 := func < n | 4*(#[d : d in D | d mod 4 eq 1] - #[d : d in D | d mod 4 eq 3]) where D is Divisors(n) > ;
> r_2(5) ;
8
> S := 1 + &+[r_2(n)*q^n : n in [1..50]] ;                                                                    
> S - T101 ;
O(q^51)

J'ai fourni $r_2(5) = 8$, histoire de rester dans le fil. Et puis, pour paraphraser Godement, un petit tour dans le jardin des délices modulaires (opium des mathématiciens) avec l'espace $M_1(\Gamma_1(4), \chi_{-4})$, qui restera pour moi un éternel mystère. Je commence quand même par vérifier que :
$$
\chi_{-4}(n) = (-1)^{n-1 \over 4} \quad \hbox {si $n$ est impair}
$$

> G<chi4> := DirichletGroup(4) ;
> G ;
Group of Dirichlet characters of modulus 4 over Rational Field
> [chi4(n) eq (IsEven(n) select 0 else (-1)^ExactQuotient(n-1,2)) : n in [0..15]] ;
[ true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true ]
> 
> M := ModularForms(chi4,1) ;
> M ;
Space of modular forms on Gamma_1(4) with character chi4, weight 1, over Integer Ring.
> Dimension(M) ;
1
> M ;
Space of modular forms on Gamma_1(4) with character chi4, weight 1, and dimension 1 over Integer Ring.
> 
> f := Basis(M)[1] ;
> f ;
1 + 4*q + 4*q^2 + 4*q^4 + 8*q^5 + 4*q^8 + 4*q^9 + 8*q^10 + O(q^12)
> qExpansion(f, 50) ;
1 + 4*q + 4*q^2 + 4*q^4 + 8*q^5 + 4*q^8 + 4*q^9 + 8*q^10 + 8*q^13 + 4*q^16 + 8*q^17 + 4*q^18 + 8*q^20 + 12*q^25 + 8*q^26 + 8*q^29 + 4*q^32 + 
    8*q^34 + 4*q^36 + 8*q^37 + 8*q^40 + 8*q^41 + 8*q^45 + 4*q^49 + O(q^50)
> T101 - qExpansion(f, 50) ;
O(q^50)

Désolé.

flipflop

@Claude : Tu n'as pas résisté :-D J'avais écrit la première ligne et ensuite je me suis perdu ! Faut que je reprenne le truc ! D'ailleurs, avec la somme de $4$ carrés il me semble que c'était plus simple ! ici il n'y a pas de $\chi_{-4}$.

@Donnet : Ce que je voulais te dire c'est que $r_2(n)$ il faut bien comprendre ce qu'il calcule (avec la formule de Noix de toto), parce que selon ce que tu appelles "décomposition", on va devoir diviser ou multiplier par un truc !

Du coup, la question c'est pour : $n = 5$, tu comptes combien de décompositions ?

claude quitté

@Donnet
Histoire de rester dans le fil. Je me suis souvenu de ``The Euclidean Algorithm Strikes Again'' mais je n'ai pas réussi à trouver le pdf sur le web. J'attache cependant une épreuve (corrigée) écrite pour des petit(e)s de L3 (ne pas se fier à la date de recompilation). Il est question, d'une part, pour un entier $n \ge 2$ de démontrer l'équivalence :
$$
\hbox {$n$ est une somme primitive de deux carrés} \iff \hbox {$-1$ est un carré modulo $n$}
$$
L'assertion de gauche signifie que $n$ est de la forme $a^2 + b^2$ avec $a \wedge b = 1$.

Et d'autre part, de donner un algorithme qui réalise l'assertion de gauche à partir de celle de droite. On ne passe pas par $\Z[i\rbrack$ mais on reste dans $\N$ avec le ``brave algorithme d'Euclide''. Je vois qu'il est question des polynômes (continuants) d'Euler. Peut-être de quoi t'amuser ? Et dans le corrigé, je vais jusqu'à donner une implémentation en maple (contraint, forcé par le cadre de l'enseignement).

Quant à $r_2(5)$, une piste. Avec comme mots-clés : entiers positifs ou négatifs et égalités :
$$
5 = 1^2 + 2^2 = 2^2 + 1^2
$$
@flip flop
Je t'assure que j'ai résisté : par exemple, je n'ai pas parlé du caractère de Kronecker $\chi_D$ associé à un discriminant quadratique fondamental $D$ et du comptage des idéaux de l'anneau des entiers de $\Q(\sqrt D)$ de norme donnée. Quant à $r_4(n)$, là tu me cherches ...

Et figure toi que je viens de comprendre que j'utilise mon logiciel comme un pied.

> L2 := StandardLattice(2) ;
> L2 ;
Standard Lattice of rank 2 and degree 2
> theta<q> := ThetaSeries(L2,30) ;
> theta ;
1 + 4*q + 4*q^2 + 4*q^4 + 8*q^5 + 4*q^8 + 4*q^9 + 8*q^10 + 8*q^13 + 4*q^16 + 8*q^17 + 4*q^18 + 8*q^20 + 12*q^25
    + 8*q^26 + 8*q^29 + O(q^31)
> Parent(theta) ;
Power series ring in q over Integer Ring

Bon, jusque là rien de nouveau. Mais je vais demander d'enquêter sur $\theta_{1,0,1} = \sum_{x,y \in \Z} q^{x^2 + y^2}$, côté jardin de la fumette :

> f := ThetaSeriesModularForm(L2) ;
> f ;
1 + 4*q + 4*q^2 + 4*q^4 + 8*q^5 + 4*q^8 + 4*q^9 + 8*q^10 + O(q^12)
> M := Parent(f) ;
> M ;
Space of modular forms on Gamma_1(4) with character $.1, weight 1, and dimension 1 over Integer Ring.

Dammed, il a retrouvé l'espace $M_1(\Gamma_1(4), \chi)$ pour un certain caractère $\chi$. Note que malgré l'inclusion stricte $\Gamma_1(4) \subsetneq \Gamma_0(4)$ ($-I_2$ est dans le gros mais pas dans le petit), on a l'égalité $P\Gamma_0(4) = P\Gamma_1(4)$.
On va aller jusqu'à récupérer le caractère $\chi_{-4}$.

> G<chi> := Universe(DirichletCharacters(M)) ;
> G ;
Group of Dirichlet characters of modulus 4 over Rational Field
> chi eq KroneckerCharacter(-4) ;
true

Il faut parfois se méfier de l'égalité :

> Gamma0(4) ;
Gamma_0(4)
> Gamma1(4) ;
Gamma_1(4)
> Gamma0(4) eq Gamma1(4) ; 
false
> Generators(Gamma0(4)) ;
[
    [1 1]
    [0 1],

    [ 1 -1]
    [ 4 -3]
]
> Generators(Gamma1(4)) ;
[
    [1 1]
    [0 1],

    [ 1 -1]
    [ 4 -3]
]

noix de totos

Ce que dit Claude dans son avant-dernier message répète ce que j'ai dit plus haut concernant $r_2$, et plus généralement $r_K$.

Serais-je devenu transparent ?

flipflop

Bonjour Noix de totos,

Je pense que Claude voulait également insister (enfin faire mumuse :-D) avec l'aspect modulaire de la chose ! C'est plus un clin oeil pour moi qui veut faire joujou avec les courbes modulaires

claude quitté

@noix de totos

Mais non, tu n'es pas devenu transparent ; j'ai d'ailleurs écrit `` Et voici $r_2(n)$ relié au caractère quadratique donné par noix de totos, caractère que j'écris plutôt $\chi_{-4}$ (indexation par le discriminant $-4$)''. J'avais même, à l'instant, l'intention de donner d'autres références concernant $r_2(n)$ et $r_4(n)$.

noix de totos

OK. Merci à Claude Q et à Flipflop pour leurs réponses.