Une suite modulo N

par **Thomas B** » Jeu 7 Jan 2010 19:08

Ah ouais pas mal... Nous on s'était modestement contentés des entiers de Gauss...

par **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).

par **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

par **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).

par **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 ?

par **antony** » Ven 8 Jan 2010 23:09

Alors, euh.

$u_{n+1}=Au_n+Bu_{n-1}$ . Soit C=A^2+4B^2

Soit $g(N)=|{u_n\text{ mod }N, n\in\mathbf N}|$ . D'après le théorème des restes chinois,

est multiplicative, donc

aussi.
Soit $p\in\mathbf P, p>C$ . L'équation caractéristique de la récurrence, X^2-AX-B=0

, a deux solutions distinctes dans $\mathbf Z/p\mathbf Z$ si et seulement si

est un résidu quadratique $\text{mod }p$ .

Lemme :
Il existe $N\in\mathbf N$ et $t\in\mathbf Z/n\mathbf Z$ premier avec

tel que $p=t\text{ mod }N\Rightarrow C\text{ residu quadratique mod }p$ .

Preuve :
Il suffit de montrer le même résultat où on a remplacé

par chacun de ses facteurs premiers. En effet, si chacun des facteurs premiers de

est un résidu quadratique mod

, alors il en est de même de tout nombre construit en les multipliant.
Soit q_i

un facteur premier de

. D'après le théorème de réciprocité quadratique, il existe c_i

tel que

est un résidu quadratique $\text{mod }p$ si et seulement si $p=c\text{ mod }q_i$ (plus précisément, si et seulement si

est, ou n'est pas, selon les restes de

et de $q_i\text{ mod }4$ , un résidu quadratique $\text{mod }q_i$ ).
D'après le théorème des restes chinois, le système $\{p=c_i\text{ mod }q_i\}$ est équivalent à $p=t\text{ mod }q_\cdots q_n$ pour un certain

premier avec $N=q_1\cdots q_n$ .

Soit un tel

. Soient $a, b\in\mathbf Z/p\mathbf Z$ les racines de l'équation caractéristique. On a u_n=Ca^n+Db^n

pour un certain couple $C, D\in\mathbf Z/p\mathbf Z$ . D'après le petit théorème de Fermat,

et

ont des ordres divisant p-1

, donc le ppcm de leurs ordres le divise aussi, et donc (u_n)

est de période $\leq p-1$ . Et donc, $g(p)\leq p-1$ , soit $f(p)\leq1-1/p$ .

Soient (p_n)

la suite des nombres premiers congrus à $t\text{ mod }N$ , et $r_n=p_1\cdots p_n$ . D'après tout ce qui précède, $f(r_n)\leq(1-1/p_1)\cdots(1-1/p_n)$ . Or le produit des 1-1/p_i

est nul si et seulement si la somme des 1/p_i

, ce qu'affirme la forme forte du théorème de Dirichlet. Ouf !

par **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 ?

par **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 $\mathbb{Z}/p\mathbb{Z}$ pour

premier congru a 1 modulo 4, et donc il faut montrer que le produit des $1-\frac{1}{p}$ converge vers 0 pour ces nombres premiers. Et ça, on peut le faire sans analyse complexe

.

par **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...

par **Noé** » Jeu 14 Jan 2010 20:32

Euh non, je sais pas montrer que la somme des inverses diverge, je sais juste montrer que $\prod_{p\in \mathbb{P}, p\equiv 1 [4]\frac{1}{1-\frac{1}{p}}$ 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 $\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}\frac{1}{a^2+b^2}=+\infty$ .
Comme la série des inverses des carrés converge, tu peux montrer que la même somme avec en plus la condition

et

premiers entre eux diverge aussi. Or un produit de

nombres premiers congrus à 1 modulo 4 (éventuellement égaux) peut s'écrire au plus de 4^n

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 $\prod_{p\in \mathbb{P}, p\equiv 1 [4]}(1+\frac{4}{p}+\frac{4^2}{p^2}+...)$ , 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

.

Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Re: Une suite modulo N

Qui est en ligne ?