Une suite modulo N

Re: Une suite modulo N

Messagepar Thomas B » Jeu 7 Jan 2010 19:08

Ah ouais pas mal... Nous on s'était modestement contentés des entiers de Gauss...
Thomas B
 
Message(s) : 183
Inscrit le : Mer 6 Mai 2009 15:16

Re: Une suite modulo N

Messagepar Noé » Jeu 7 Jan 2010 21:18

Il faut bien un petit peu de restes chinois dans la première partie, non ? (A moins que tu ais une solution sans Thomas).
Sinon Antony, si le théorème de Dirichlet, tu l'utilises modulo 4, en théorie y en a pas besoin (on peut démontrer facilement sans l'utiliser l'infinité des nombres premier congrus à 1 modulo 4).
"Invoquons les mânes des illustres ancêtres qui ont fait des bons théorèmes pour nous !" (S. Dupont)
Noé
 
Message(s) : 88
Inscrit le : Mer 27 Août 2008 20:39
Localisation : Ulm

Re: Une suite modulo N

Messagepar Thomas B » Jeu 7 Jan 2010 21:53

Oui d'accord, mais je ne classe pas ce théorème dans l'artillerie lourde de toute façon
Thomas B
 
Message(s) : 183
Inscrit le : Mer 6 Mai 2009 15:16

Re: Une suite modulo N

Messagepar antony » Ven 8 Jan 2010 15:14

J'utilise réciprocité quadratique + restes chinois + Dirichlet pour montrer que pour tout x il existe une infinité, et même une fraction positive, des nombres premiers tels que x est un résidu quadratique mod p (i.e. lim_n #{p dans E|p<n}/#{p dans P|p<n}>0, où E est l'ensemble des tels nombres premiers).
antony
 
Message(s) : 13
Inscrit le : Mar 8 Juil 2008 18:26

Re: Une suite modulo N

Messagepar Noé » Ven 8 Jan 2010 19:06

Ah et ça aide en quoi ? Tu peux montrer ou résumer vite fait ta solution pour voir ?
"Invoquons les mânes des illustres ancêtres qui ont fait des bons théorèmes pour nous !" (S. Dupont)
Noé
 
Message(s) : 88
Inscrit le : Mer 27 Août 2008 20:39
Localisation : Ulm

Re: Une suite modulo N

Messagepar antony » Ven 8 Jan 2010 23:09

Alors, euh.

[tex]u_{n+1}=Au_n+Bu_{n-1}[/tex]. Soit [tex]C=A^2+4B^2[/tex]

Soit [tex]g(N)=|{u_n\text{ mod }N, n\in\mathbf N}|[/tex]. D'après le théorème des restes chinois, [tex]g[/tex] est multiplicative, donc [tex]f[/tex] aussi.
Soit [tex]p\in\mathbf P, p>C[/tex]. L'équation caractéristique de la récurrence, [tex]X^2-AX-B=0[/tex], a deux solutions distinctes dans [tex]\mathbf Z/p\mathbf Z[/tex] si et seulement si [tex]C[/tex] est un résidu quadratique [tex]\text{mod }p[/tex].

Lemme :
Il existe [tex]N\in\mathbf N[/tex] et [tex]t\in\mathbf Z/n\mathbf Z[/tex] premier avec [tex]n[/tex] tel que [tex]p=t\text{ mod }N\Rightarrow C\text{ residu quadratique mod }p[/tex].

Preuve :
Il suffit de montrer le même résultat où on a remplacé [tex]C[/tex] par chacun de ses facteurs premiers. En effet, si chacun des facteurs premiers de [tex]C[/tex] est un résidu quadratique mod [tex]p[/tex], alors il en est de même de tout nombre construit en les multipliant.
Soit [tex]q_i[/tex] un facteur premier de [tex]C[/tex]. D'après le théorème de réciprocité quadratique, il existe [tex]c_i[/tex] tel que [tex]q_i[/tex] est un résidu quadratique [tex]\text{mod }p[/tex] si et seulement si [tex]p=c\text{ mod }q_i[/tex] (plus précisément, si et seulement si [tex]p[/tex] est, ou n'est pas, selon les restes de [tex]p[/tex] et de [tex]q_i\text{ mod }4[/tex], un résidu quadratique [tex]\text{mod }q_i[/tex]).
D'après le théorème des restes chinois, le système [tex]\{p=c_i\text{ mod }q_i\}[/tex] est équivalent à [tex]p=t\text{ mod }q_\cdots q_n[/tex] pour un certain [tex]t[/tex] premier avec [tex]N=q_1\cdots q_n[/tex].

Soit un tel [tex]p[/tex]. Soient [tex]a, b\in\mathbf Z/p\mathbf Z[/tex] les racines de l'équation caractéristique. On a [tex]u_n=Ca^n+Db^n[/tex] pour un certain couple [tex]C, D\in\mathbf Z/p\mathbf Z[/tex]. D'après le petit théorème de Fermat, [tex]a[/tex] et [tex]b[/tex] ont des ordres divisant [tex]p-1[/tex], donc le ppcm de leurs ordres le divise aussi, et donc [tex](u_n)[/tex] est de période [tex]\leq p-1[/tex]. Et donc, [tex]g(p)\leq p-1[/tex], soit [tex]f(p)\leq1-1/p[/tex].

Soient [tex](p_n)[/tex] la suite des nombres premiers congrus à [tex]t\text{ mod }N[/tex], et [tex]r_n=p_1\cdots p_n[/tex]. D'après tout ce qui précède, [tex]f(r_n)\leq(1-1/p_1)\cdots(1-1/p_n)[/tex]. Or le produit des [tex]1-1/p_i[/tex] est nul si et seulement si la somme des [tex]1/p_i[/tex], ce qu'affirme la forme forte du théorème de Dirichlet. Ouf !
antony
 
Message(s) : 13
Inscrit le : Mar 8 Juil 2008 18:26

Re: Une suite modulo N

Messagepar Thomas B » Sam 9 Jan 2010 18:33

Ah oui, tu as fait le cas général.
Sinon ça dit quoi exactement la "forme forte du théorème de Dirichlet"? ça peut pse montrer facilement à partir de la forme habituelle ?
Thomas B
 
Message(s) : 183
Inscrit le : Mer 6 Mai 2009 15:16

Re: Une suite modulo N

Messagepar Noé » Sam 9 Jan 2010 20:27

La version forte de Dirichlet Thomas, je pense que c'est celle de la première ligne de la page dont tu m'avais parlé par MP. Le théorème de Chebotarev, ça a l'air juste d'une généralisation bizarre de cette version forte.
Sinon je me disais bien, quand j'avais posé le problème, qu'il y avait moyen de montrer le cas général avec un théorème bourrin qui trivialise tout, mais j'avais mis ce cas particulier justement parce qu'il en existe une preuve qui n'utilise que des connaissances plus ou moins élémentaires : dans ce cas, le polynôme a des solutions dans [tex]\mathbb{Z}/p\mathbb{Z}[/tex] pour [tex]p[/tex] premier congru a 1 modulo 4, et donc il faut montrer que le produit des [tex]1-\frac{1}{p}[/tex] converge vers 0 pour ces nombres premiers. Et ça, on peut le faire sans analyse complexe ;) .
"Invoquons les mânes des illustres ancêtres qui ont fait des bons théorèmes pour nous !" (S. Dupont)
Noé
 
Message(s) : 88
Inscrit le : Mer 27 Août 2008 20:39
Localisation : Ulm

Re: Une suite modulo N

Messagepar antony » Jeu 14 Jan 2010 10:35

Pour la preuve de cette forme de Dirichlet, j'en sais rien (enfin pas plus que le Dirichlet standard quoi :-)) (bon en fait si j'ai du voir ça une fois mais j'ai vite tout oublié...)
Par contre je veux bien un rappel sur la preuve "élémentaire" que la somme des inverses des nombres premiers =1[4] diverge...
antony
 
Message(s) : 13
Inscrit le : Mar 8 Juil 2008 18:26

Re: Une suite modulo N

Messagepar Noé » Jeu 14 Jan 2010 20:32

Euh non, je sais pas montrer que la somme des inverses diverge, je sais juste montrer que [tex]\prod_{p\in \mathbb{P}, p\equiv 1 [4]\frac{1}{1-\frac{1}{p}}[/tex] diverge (mais c'est suffisant pour résoudre le problème).

J'ai pas le temps de détailler mais en gros, le principe c'est d'utiliser le fait que [tex]\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}\frac{1}{a^2+b^2}=+\infty[/tex].
Comme la série des inverses des carrés converge, tu peux montrer que la même somme avec en plus la condition [tex]a[/tex] et [tex]b[/tex] premiers entre eux diverge aussi. Or un produit de [tex]n[/tex] nombres premiers congrus à 1 modulo 4 (éventuellement égaux) peut s'écrire au plus de [tex]4^n[/tex] façons différentes comme une somme de deux carrés (ça se démontre en utilisant la décomposition en facteurs premiers en entiers de Gauss), et donc la dernière somme est majorée par [tex]\prod_{p\in \mathbb{P}, p\equiv 1 [4]}(1+\frac{4}{p}+\frac{4^2}{p^2}+...)[/tex], qui diverge donc aussi. En simplifiant les sommes géométriques et en bidouillant un peu, on montre que le gros produit dont on voulait montrer qu'il diverge, diverge bien ;) .
"Invoquons les mânes des illustres ancêtres qui ont fait des bons théorèmes pour nous !" (S. Dupont)
Noé
 
Message(s) : 88
Inscrit le : Mer 27 Août 2008 20:39
Localisation : Ulm

Précédent

Retour vers Problèmes mathématiques

Qui est en ligne ?

Utilisateur(s) parcourant ce forum : Aucun utilisateur inscrit et 1 invité

cron