Polynômes et congruences dans Z/nZ

[Floria]

Bonjour,
J'ai un DM à faire mais ce ne sont que des démonstrations et, étant en reprise d'étude, j'ai un peu de mal à retrouver les techniques (sans compter toutes les propriétés et définitions que je n'arrête pas de réviser...) et j'aurais besoin de petits coup de pouces (indice, méthode, idée, n'importe quoi) pour m'aider.

Le DM compte 4 exercices, mais je n'ai pour l'instant réfléchi qu'aux deux premiers donc je ne met que ceux-là:

Exercice 1: Démontrer ou réfuter les affirmations suivantes:
1) Soient K un corps et P(X) K[X] un polynôme de degré n. Alors P(x) admet au plus n racines dans K.
2) Soit m>1 un entier. Alors il existe un entier n tel que le polynôme admet plus que m racines dans

Pour la question 1, j'ai fait par récurrence, je pense que c'est bon:
Soit K un corps et un polynôme. On considère la propriété pn:"Si deg(P)=n, alors P admet au plus n racines dans K", que l'on se propose de démontrer par récurrence:
Pour n=1: , où . Alors P a une unique racine (car K est un corps)
Supposons la propriété pk vraie (i.e. vraie au rang k, k entier supérieur à 1) et considérons un polynôme P de degré k+1.
Notons une racine de P (Si P n'a pas de racine, la propriété est immédiatement vraie au rang k+1). On peut alors écrire: où Q(X) est un polynôme de degré k.
Comme pk est vraie, Q(X) admet au plus k racines; donc P(X) admet au plus k+1 racines.
La propriété est donc vraie pour tout n supérieur ou égal à 1.


Pour la question 2, en revanche, je n'avance pas. Alors, pour commencer, j'ai cherché les racines de dans pour différents n. Voici ce que j'ai trouvé:
Pour n=2: une racine, X=1 (le prof ne met pas la barre, je suppose qu'il trouve évident qu'on parle de classe d'équivalence...)
Pour n=3: deux racines: X=1 et X=2=-1
Pour n=4: deux racines: X=1 et X=3=-1
Pour n=5: deux racines: X=1 et X=4=-1
Pour n=6: deux racines: X=1 et X=5=-1
ect jusqu'à n=12, avec deux cas particuliers:
Pour n=8: 4 racines: X=1, X=3, X=5 et X=7: j'ai remarqué que 7=-1 et 5=-3
Pour n=12: 4 racines: X=1, X=5, X=7 et X=11. là encore, 11=-1 et 7=-5.
Donc, à priori, je dirais que l'assertion est fausse. Mais pour y démontrer....
Je sais qu'avec le théorème des restes chinois, si on note la décomposition en facteurs premiers de n, on a qui est isomorphe à , et comme les sont des nombres premiers, le polynôme admet au plus 2 racines dans chacun de ces corps de fraction . Si j'ai bien compris mon cours, je peux aussi dire qu'il admet exactement deux racines si n est impair (parce que dans ce cas, tous les sont différents de 2, donc 2 divise pour tout i, et on a une propriété qui dit que si alors le polynôme admet exactement d racines dans (avec p premier) )

Après, je ne sais pas comment faire. Après plus d'une demie-heure à me retourner la tête, j'ai décidé de passer à l'exo 2:

Exercice 2:
1) Soient m, n entiers strictement positifs. Montrer que s'il existe une infinité de nombres premiers congrus à m modulo n, alors pgcd(m,n)=1.
2) Montrer qu'il existe une infinité de nombres premiers congrus à 1 modulo 4:
a) Soit {p1, ..., pk} un ensemble de nombres premiers congrus à 1 module 4 et considérons . Que peut-on dire des facteurs premiers de N?
b) Soit p un nombre premier tel que contient un élément d'ordre 4. Que peut-on dire de p?
c) Conclure.

Là, c'était encore pire. En gros, j'ai repris mes définitions de cours et cherché des propriétés, dans mon cours ou dans mes livres et cours des années passées, qui pourraient m'aider; sans grand résultat. Ce qui donne un afflu de données dont je ne vois pas comment me servir.

1) il existe u et v entiers tels que mu+nv=1
il existe k, k' entiers tq p=kn+r et m=k'n+r il existe q entier tq p-m=qn
J'ai essayé d'appliquer ces définitions en remplaçant p par un produit infini d'entiers, ou en remplaçant n par sa décomposition en facteurs premiers, mais ça ne m'a pas aidé.

2) a) On note la décomposition en facteurs premiers de N. On a alors:
soit encore:
On en déduit que 4 divise donc
De même, donc pour tout
De plus, on sait que pour tout
Et voilà. j'ai l'impression de pas être loin, mais ce n'est sans doute qu'une impression puisque je n'arrive pas à conclure.

b) (les éléments inversibles) contient un élément d'ordre 4 ssi il existe x dans tel que ce qui équivaut à dire que .
Or les diviseurs de sont : (j'en oublie peut-être, je n'avais pas beaucoup étudié les polynômes en licence par rapport à ce que je fais maintenant....)
Comme p est premier, p est différent de 1; ce qui me laisse les 3 autres et ne m'avance pas beaucoup.


Voilà; merci d'avance pour toute idée pouvant me faire avancer. En une semaine je doute fort d'avoir le temps de m'intéresser au deux derniers, d'autant que l'exo 2 compte encore une longue question, sachant qu'il m'a déjà fallu 3H pour faire tout ça et qu'au final, je n'ai répondu qu'à une question...(ce qui est, il faut bien l'avouer, un peu déprimant)
-----

[Resartus]

Bonjour,
Exercice 1 partie 2 :
X2-1=(X+1)(X-1). Donc tout diviseur de zero X0 dans l'anneau Z/nZ va donner (au moins) la racine X0+1 ( il se peut que X0-1 ait déjà été compté)

Si vous navez pas déjà vu comment calculer le nombre de diviseurs de zero dans le cas le plus général, vous pouvez vous contenter de choisir n de la forme 2^k où le calcul est très simple.Et manifestement on peut trouver un k assez grand pour que ce nombre dépasse n'importe quel m

Exercice 2 1
bête comme chou : un nombre congru à n modulo m est forcément multiple ou égal à leur pgcd...

Exercice 2 2 a : vous souvenez-vous comment on démontre qu'il existe une infinité de nombres premiers? On prend le produit de tous les nombres premiers déjà connus plus 1 et on démontre qu'il doit être multiple d'un nombre premier non déjà connu
Il faut faire de même mais avec N=(2*P1*P2*...)².+1 (qui est de la forme voulue)
2 2 b : maintenant, il faut montrer que ce nouveau nombre premier p découvert et qui divise N est bien de la forme 4k+1 (et pas 4k+3). Pour cela, il faut reexaminer le nombre N : N-1 est un carré, et est congru à -1.module p On a donc trouvé un nombre d'ordre 4 dans le corps. ce qui avec quelques manipulations conduira à la conclusion sur p cherchée....

[Floria]

Ok, merci beaucoup.

Du coup pour la 1.2 J'ai mis:
Soit m un entier (supérieur à 1). On considère un entier n de la forme 2^k, où k>m
Soit x0 un diviseur de 0 dans Z/nZ; Alors x0+1 est une racine de X²-1
Comme n=2^k, les diviseurs de 0 sont les x0=2^i, avec i=1..k
IL y a k diviseurs de 0, donc au moins k racines de X²-1 dans Z/nZ; or k>m.
Donc pour tout m>1 entier il existe un entier n tq X²-1 admet plus que m racines dans Z/nZ.

Et pour la 2.1, j'ai encore un doute:
tq ou (car p premier)
Si je suis ce raisonnement, il suffit que j'ai deux nombres premiers congrus à m mod n pour que pgcd(m,n)=1; il n'y a donc pas besoin de l'infinité déclarée...

Pour la 2.2, je regarderais demain ou mercredi. Il me semble que l'on a déjà fait un exercice en TD basé sur l'absurde pour démontrer qu'il y avait une infinité de nombre premiers congrus à -1 mod 4, mais la méthode employé me semblait totalement différente de ce qui est demandé ici. Je relirais ça à tête reposée.

Encore merci

[Floria]

Bon, ça ne marche pas :/

Q°2.2.a: J'ai pris N=q1...qr la décomposition en facteurs premiers de N. J'étudie ensuite la congruence des qi mod 4:
Si qi=0[4] alors 4 divise qi donc qi n'est pas premier : Absurde.
Si qi=1[4] alors qi est l'un des pj cité précédemment (j=1..k). Or N=(2p1..pk)²+1 donc N=1[pj] et pj ne divise pas N. Si qi est un des pj, alors qi ne divise pas N, ce qui est absurde.
Si qi=2[4] alors qi=4x+2=2(2x+1) donc qi est un multiple de 2; Or qi est premier donc qi=2. Cependant, N est impair (car N=(2p1..pk)²+1=2(2p1²..pk²)+1) donc N n'est pas divisible par 2, donc qi ne divise pas N: Absurde.

On en déduit que qi=3[4]
Tous les facteurs premiers de N sont congrus à 3 modulo 4.


Q°2.2.b: L'ordre d'un élément d'un corps divise l'ordre du corps; L'ensemble des inversibles de Z/pZ est un corps car p premier. De plus, l'ordre de ce corps est p-1 (propriété du cours). S'il contient un élément d'ordre 4, alors 4 divise p-1, et donc p est congru à 1 modulo 4.

Jusque là, ça me semble bon, et pourtant ça ne concorde pas avec ce que vous avez dit: Les diviseurs de N sont de la forme 4k+3 et pas 4k+1; N est congru à 1 mod pj donc N-1 est congru à 0 mod pj, pas à -1...
Du coup, ça ne marche pas.

[A voir en vidéo sur Futura]

[Floria]

Autant pour moi, N est congru à -1 modulo qi
donc N est d'ordre 4 dans Z/qiZ et donc qi congru à 1 modulo 4
Or on a montré à la question a que qi est congru à 3 modulo 4

On obtient donc une contradiction et on en déduit qu'il y a une infinité de nombres premiers congrus à 1 modulo 4.

C'est bon?

[Floria]

Et donc, avec tout ça, on en arrive à la question 3: Montrer que, si pour toue paire d'entier m,n supérieurs ou égaux à 1 tq pgcd(m,n)=1, il existe p premier congru à m mod n, Alors il existe une infinité de nombres premiers congrus à m mod n.

A priori, ça me semble être juste une généralisation de la question précédente. Sauf que pour faire ça, on nous pose deux questions intermédiaires:
a) Expliquer pourquoi on peut supposer n>1 et 0<m<n:
J'ai mis que le cas n=1 était trivial (il y a une infinité de nombres premiers congrus à m mod 1, parce que p=m[n] équivaut à dire qu'il existe un entier k tel que p=k+m; ce qui est vrai pour tout nombre premier) et que dans les cas m<0 et m>n on pouvait toujours se rapporter au cas 0<m<n en ajoutant (ou retirant) n un certain nombre de fois.

b) Supposons que p1...pr soient congrus à m modulo n. soit k tel que . Montrer qu'il existe p tel que
(p n'est pas précisé premier dans le texte de l'énoncé, mais je pense que ce n'est qu'un oubli)
Et là, je ne vois pas du tout le lien avec la question précédente (2.2)....

[libellilas]

Bonjour,

J'espère que ce n'est pas trop tard,

Pour la question 2 de l'exercice k, attention i va 1 à k-1 car 2^k = 0 dans Z/nZ et (dans la definition que j'ai d'un diviseur de 0), il doit être non nul. Après on peut en effet quand même compter le nombre de racines que tu dis puisque 1 est racine (et correspond à un x0=0, mais ce n'est pas un diviseur de 0).

Pour l'exercice 2, question 1 :
Tu arrives à pgcd(m,n)=1 ou p, or l'hypothèse est qu'une infinité de nombre premier vérifie ça, mais une infinité de nombre premier n'est pas égale à pgcd(m,n) qui est un entier fixé indépendant de p, par conséquent pgcd(m,n)=1.

Pour la question 2.a), ton raisonnement et ton résultat sont corrects, mais tu aurais pu juste prendre un facteur premier p quelconque de N, plutôt que de te balader avec des indices...

Pour la question 2.b) le résultat est bon mais attention, c'est Z/pZ qui est un corps car p est premier, pas l'ensemble des inversibles. Lorsque tu utilises que 4 divise l'ordre de l'ensemble des inversibles, donc p-1, tu utilises en fait le théorème de Lagrange qui est un théorème sur les groupes, pas sur les corps : l'ensemble des inversibles de Z/pZ est un groupe, ça suffit pour appliquer le théorème de Lagrange.

Pour la question 2.c) pourquoi conclus tu que N est d'ordre 4 dans Z/qiZ ? Il suffit en effet trouver un élément d'ordre 4 dans Z/qiZ pour conclure, mais je pense qu'il faut montrer que 2p1...pk est d'ordre 4 (c'est à dire que 4 est le plus petit entier n tel que (2p1...pk)^n est congrus à 1 modulo qi...)

Pour la question 3.b) je ne vois pas non plus...

[Floria]

Ce n'est pas trop tard, je suis encore en train de recopier au propre et mes (nombreux) doutes me retardent.

En particulier pour la question 1.2: J'avais remarqué qu'il n'y a, en effet, que k-1 diviseurs de 0; mais finalement, je n'arrive pas à montrer qu'il y a du coup k-1 solutions de P(X)=X²-1=0

En effet, si x0 est diviseur de 0 et que l'on regarde P(x0+1) ça donne
Mais le fait que x0 soit un diviseur de 0 ne signifie pas que ce truc-là fasse 0...
même si j'utilise la factorisation: alors
J'étais allée trop vite en disant que si x0 est diviseur de 0 dans Z/nZ alors il est congru à 0 mod n, ce qui est tout à fait faux.
En plus, j'ai fait un test avec n=2^4=16. Ici, 2 est un diviseur de 0 mais 2+1=3 n'est pas solution de X²-1: 3²=9 n'est pas congru à 1 modulo 16
D'autre part, je suis tombée sur un site qui dit que x² congru à 1 mod 2^n admet seulement 4 solutions, ce qui va en contradiction avec ce que je cherche...

J'en déduis que ce que j'avais fait est faux. Oups. Retour à la case départ....
Une autre idée?

[libellilas]

Oups, en effet ça ne marche pas.

Ce que l'on pourrait faire sinon :

Soit k un entier tel que 2^k>m. Soit n=p_1*...*p_k un produit de k nombres premiers impairs (possible de faire ça comme il y en a une infinité).

Par le théorème des restes chinois on peut montrer que x est solution dans Z/nZ ssi x est solution dans Z/p_iZ pour tout i=1,...k.

(En effet, l'implication directe est évidente, l'autre peut se montrer en disant que : 1 est solution particulière de système de congruence "a congrus à 1 modulo p_i pour tout i" donc les solutions générales du système sont les a congrus à 1 modulo n.)

On a donc que {solutions dans Z/nZ}=intersection des {solutions dans Z/p_iZ} pour i=1,... k
Donc le cardinal du premier ensemble est égal au produit des cardinaux des ensembles {solutions dans Z/p_iZ}. Or les p_i sont impairs donc p_i-1 est divisible par 2 donc l'équation a exactement 2 solutions dans chaque Z/p_iZ, donc l'équation à exactement 2^k solutions dans Z/nZ, et 2k>m, d'où le résultat.
Cette preuve me semble correcte

[Floria]

J'avais effectivement commencé avec cette décomposition en facteurs premiers, mais je n'avais pas pensé à me limiter au cas n impair ce qui m'ajoute des solutions...

Cependant, il y a encore un souci: Si on prend l'intersection des solutions dans les Z/piZ, ça veut dire que l'on limite le nombre de solutions, vu que c'est l'intersection pas la réunion. On ne se retrouve donc pas avec 2^k solutions; d'abord, il y a toujours 1 et -1, et ensuite on ajoute toutes celles qui sont dans tous les Z/piZ en même temps.....à mon humble avis, il n'y en a pas d'autre que 1 et -1 dans l'intersection.
Donc non.

Personnellement, j'étais plutôt partie sur l'idée de démontrer qu'il ne peut pas y avoir plus de 4 solutions....sauf que j'ai trouvé un contre exemple.
J'envisage l'abandon de cette question

[libellilas]

effectivement...