Racines primitives

OShine

Bonsoir
Je bloque sur la question $7$. J'ai trouvé une indication mais je ne l'ai pas trop comprise : considérer une partition des racines n-ièmes de l'unité donnée par le théorème de Lagrange sur l'ordre d'un élément dans un groupe. 

raoul.S

Oshine, as-tu remarqué que les racines n-ième de l'unité forment un groupe pour la multiplication ? Lequel ?

OShine

Bonjour,
$U_n = \{ e^{ 2i k \pi /n} \ | \ k \in [|0,n-1|] \}$ est un sous-groupe de $\C^{*}$, c'est donc un groupe.
Pour tout $z \in U_n$, on a $z^n=1$.

raoul.S

OK.
Pour $d\in [\![1,n]\!]$ diviseur de $n$ on note $O_d$ le sous-ensemble de $U_n$ formé des éléments d'ordre $d$.
Essaie de montrer que $U_n=\coprod_{d\mid n} O_d$.
Puis conclure en sachant que $X^n-1=\prod_{z\in U_n} (X-z)$.

OShine

D'accord merci. J'ai avancé un peu mais je n'ai pas réussi à terminer. 
Montrons que $U_n = \displaystyle\bigcup _{d \mid n} O_d$.
Il est évident que $ \displaystyle\bigcup _{d \mid n} O_d$ car $O_d$ est un sous-ensemble de $U_n$.
Réciproquement, si $z \in  \displaystyle\bigcup _{d \mid n} O_d$ alors $z$ est un élément de $U_n$ d'ordre $d$. Comme $z \in U_n$ alors $z^n=1$. Et comme $z$ est d'ordre $d$ alors $z^d=1$ et $d \mid n$ car $d$ est minimal. 
Ainsi, on a montré $\boxed{U_n = \displaystyle\bigcup _{d \mid n} O_d}$. 
Or $X^n-1= \displaystyle\prod_{ z \in U_n} (X-z)$ donc $X^n-1= \displaystyle\prod_{ z \in  \cup _{d \mid n} O_d} (X-z)$ 
Je bloque ici.

noobey

Je n'ai ABSOLUMENT rien compris à ta réciproque

OShine

Ma réciproque est fausse je vais corriger ça dans la soirée. 

Amédé

Tu t'attaques à l’agrégation?

Amédé

Il faut voir que les $O_{d}$ forment une partition de $U_{n}$. Car si $d|n$ alors $O_{d}\subset U_{d}\subset U_{n}$. Chaque racine de l'unité à un unique ordre qui divise $n$ par le théorème de Lagrange. Donc chaque élément de $U_{n}$ appartient à un unique $O_{d}$ et est un générateur de $U_{d}$. Les racines de $X^{n}-1$ sont exactement les éléments de $U_{n}$. Donc en réorganisant le produit par rapport à la partition $X^{n}-1=\prod\limits_{\omega\in U_{n}}{(X-\omega)}=\prod\limits_{d|n}{\prod\limits_{\omega\in U_{d}^{*}}{(X-\omega)}}=\prod\limits_{d|n}{\Phi_{d}(X)}$

OShine

C'est niveau MP. 

OShine

Peux-tu enlever ta solution Amédé ? Je ne souhaite pas de corrigé pour ces questions, et j'essaie de suivre la piste de RaoulS.
Quel intérêt de donner la solution alors que je cherchais et que j'avais une piste ? 

OShine

Montrons que $U_n = \displaystyle\bigcup_{d \mid n} O_d$.
On a clairement, $\displaystyle\bigcup_{d \mid n} O_d \subset U_n$ car $O_d$ est une partie de $U_n$.
Réciproquement, si $z \in  \displaystyle\bigcup_{d \mid n} O_d$ alors il existe un diviseur $d$ de $n$ pour lequel $z$ est d'ordre $d$.
Mais $O_d \subset U_n$ donc l'ordre de $z$ qu'on note $o(z) \mid card (U_n)=n$ d'après le théorème de Lagrange. (L'ordre de tout élément d'un groupe fini divise le cardinal ce groupe)
Ainsi, il existe $k \in \N \ n = k \times o(z)$ donc $z^n= z^{  k \times o(z) }=(z^{ o(z)})^k=1^k=1$
Finalement, $z \in U_n$
On a montré par double inclusion : $\boxed{U_n = \displaystyle\bigcup_{d \mid n} O_d}$
Or $X^n- 1 = \displaystyle\prod_{z \in U_n} (X-z)$
Or $\phi_d =  \displaystyle\prod_{z \in P_d} (X-z)$ donc $ \displaystyle\prod_{d \mid n} \phi_d = \displaystyle\prod_{d \mid n}  \displaystyle\prod_{z \in P_d} (X-z)  $.

Je bloque ici, je ne vois pas comment utiliser le résultat intermédiaire donné par RaoulS avec l'union dans le produit. 
J'ai l'impression que $P_n = O_n$ mais idem je ne vois pas où l'utiliser.

noobey

Mais....

Tu montres 2 fois de suite que $A \subset B$ ....

OShine

Oui décidemment j'ai du mal. 

Soit $z \in U_n$. Alors il existe $k \in [|0,n-1|]$ tel que $z=e^{2 i k \pi /n}$

Montrons qu'il existe $d \mid n$ tel que $o(z)=d$.

Comme $U_n$ est un groupe fini de cardinal $n$, l'ordre de tout élément de $U_n$ divise $n$. Ainsi, $o(z) \mid n$

Si on note $d= o(z)$, on a $d \mid n$ et $z$ est bien un élément d'ordre $d$ qui divise $n$.

Donc $U_n \subset \displaystyle\bigcup_{d \mid n} O_d$

Après je n'ai pas compris comment utiliser cette union dans le produit.

OShine

Ensuite $\displaystyle\prod_{ d \mid n} \phi_d = \prod_{ d \mid n}  \prod_{z \in P_d} (X-z)$
Et ici je bloque, je ne vois pas comment introduire le $O_d$.

noobey

Soit z = exp(2ik.pi/n) d'ordre d. C'est une racine primitive m-ème pour quel m?

OShine

Pour $m=d$

lourrran

Soit z = exp(2ik.pi/n) d'ordre d
Je ne sais pas ce que veut dire d'ordre d ... donc je lis seulement :  Soit z = exp(2ik.pi/n). De toutes façons, z = exp(2ik.pi/n) est parfaitement défini, j'ai tout ce qu'il me faut pour savoir si c'est une racine primitive de 1 d'ordre 100 ou 10 ou 5...

d est un leurre, pour attraper les moineaux.

La réponse attendue dépend de k et de n, pas de d.

raoul.S

Peut-être regarder s'il y a un lien entre $O_d$ et $P_d$...

OShine

Lourrran tu ne connais pas l'ordre d'un élément dans un groupe ? C'est le plus petit entier p tel que z^p=1

lourrran

J'ai effacé tout ça de ma mémoire, il y a plus de 30 ans. Donc je suis cette discussion de très loin.

Par contre, je peux te dire que si $z =  \exp(2ik\pi/n) $, et si on note $u =n/ \mathrm{pgcd}(k,n)$
alors $z \in P_u$ : $z$ est une racine primitive $u$-ième de l'unité.

De là à conclure que le $d$ dont tu parles, ce serait peut-être bien $n/ \mathrm{pgcd}(k,n)$, il n'y a qu'un pas ... mais comme je ne comprends pas la moitié des notations, je vais te laisser franchir ce pas toi-même.

OShine

Après réflexion, je pense avoir résolu la question. Merci Raoul.S. 
Pas facile cette question, apparemment c'est une question classique. 
$O_d$ est l'ensemble des éléments d'ordre $d$ avec $d$ diviseur de $n$.
Un élément d'ordre $d$ est un élément $z$ qui vérifie $\forall n \in \N \ \ z^n=1 \implies d \mid n$ ce qui signifie que $d$ est minimal pour la relation de divisibilité.
Un élément de $P_d$ est une racine d-ième primitive de l'unité. Donc $\forall 1 \leq k <d$ on a $z^k \ne 1$ et $z^d =1$
Finalement, on a $\boxed{P_d = O_d}$
Donc  $\displaystyle\prod_{ d \mid n} \phi_d = \prod_{ d \mid n}  \prod_{z \in P_d} (X-z) =\displaystyle\prod_{ d \mid n}  \prod_{z \in O_d} (X-z) $
Pour y voir plus clair. 
Notons $\{d_1, \cdots, d_r \}$ les diviseurs de $n$.
Or $\displaystyle\prod_{ z \in \displaystyle\cup_{d \mid n} O_d} (X-z) =\displaystyle\prod_{ z \in O_{d_1} } (X-z)  \times \cdots \times \displaystyle\prod_{ z \in O_{d_r} } (X-z)$
Ce qui montre clairement que $\boxed{\displaystyle\prod_{ d \mid n}  \prod_{z \in O_d} (X-z)= \displaystyle\prod_{ z \in \displaystyle\cup_{d \mid n} O_d} (X-z) }$
Mais $ \displaystyle\bigcup_{d \mid n} O_d = U_n$
Ainsi, $\displaystyle\prod_{ d \mid n}  \prod_{z \in O_d} (X-z)=\displaystyle\prod_{ z \in U_n} (X-z)$
On sait que $\displaystyle\prod_{ z \in U_n} (X-z) =X^n-1$
Finalement $\boxed{\displaystyle\prod_{ d \mid n} \phi_d = X^n -1}$

OShine

Je teste la question 8.a. Le rapport ne donne pas d'indication mais dit juste qu'une récurrence n'est pas nécessaire.
Soit $p$ un nombre premier et $k \geq $ un entier.
Remarquons d'abord que $Y^m -1 =(Y-1)(Y^{m-1} + \cdots +1)$

J'avais comme idée de prendre $n=p$ et les diviseurs de $p$ sont $1$ et $p$.

Ainsi, $X^p-1= \displaystyle\prod_{d \mid p} \phi_d= \phi_p \phi_1$ mais je ne connais pas $\phi_1$

Je ne trouve pas la 8.a.

gai requin

$\Phi_{p^k}(X)=\dfrac{X^{p^k}-1}{X^{p^{k-1}}-1}$.

OShine

Je ne comprends pas comment on fait pour calculer $\phi_{p^k}$. 

J'ai une indication qui dit : caractériser les racines primitives n-ièmes de la forme $e^{2 i k \pi /n}$ et se rappeler que pour tout polynôme $Y$ on a $Y^m-1=(Y-1)(Y^{m-1} + \cdots +Y+1)$

Je ne comprends pas l'indication. 

gai requin

Lis mon message précédent puis choisis bien $Y$ et $m$.

OShine

Je ne comprends pas d'où sort ta formule.
Comme j'ai dit je ne comprends pas comment calculer $\phi_{p^k}$.
Car si j'applique la formule, $X^{p^k}-1= \displaystyle\prod_{d \mid p^k} \phi_{d}$ et je ne vois pas comment avancer car on ne connait pas $\phi_d$.
Les diviseurs de $p^k$ sont $1,p, \ldots, p^{k-1},p^k $.

Amédé

Tu ne veux pas qu'on te donne la réponse mais tu ne sais pas trouver $\phi_{1}$? Quelles sont les racines primitive unièmes de 1?

Tu peux décomposer: $X^{q}-1=\phi_{q}\prod\limits_{d|q\text{ et } d<q}{\phi_{d}}=$...

OShine

Ok merci je pense avoir trouvé l'idée grâce à ta décomposition. 

Par contre vous comprenez l'indication avec la caractérisation des racines primitives ?

OShine

Amédé ta décomposition m'a mis sur la piste. Merci. J'ai mis une journée pour comprendre l'idée de la preuve.
On a $X^{q}-1=\phi_{q} \displaystyle\prod_{d \mid q\text{ et } d<q} \phi_{d}$
Or $ \displaystyle\prod_{d \mid q\text{ et } d<q} \phi_{d} = X^{q-1}-1$
Ainsi, en prenant $q=p^k$, on trouve $\boxed{X^{p^k}-1 = \phi_q (X^{p^k -1} -1)}$
Ainsi, $\phi_q = \dfrac{X^{p^k}-1}{X^{p^k -1} -1}$ Je retrouve la formule de Gai Requin 
En posant $Y=X^{p^k -1} $ et $m=p$ et sachant que $\dfrac{Y^m-1}{Y-1} = 1+ Y + \cdots + Y^{m-1}$
On obtient $\boxed{\phi_q = 1+ X^{p^k -1} + \cdots + X^{(p-1)(p^k -1)}}$

raoul.S

Pas correcte cette formule $\displaystyle\prod_{d \mid q\text{ et } d<q} \phi_{d} = X^{q-1}-1$ 

OShine

Si $d<q$ alors $d \leq q-1$ ... C'est la définition de $\phi_n$ je ne comprends pas pourquoi la formule n'est pas correcte, surtout que je tombe sur la bonne réponse à la fin.

Elle est valable pour $q \geq 2$ mais ici $q=p^k$ donc $q \geq 2$. 

JLapin

OShine a dit :

Amédé ta décomposition m'a mis sur la piste. Merci. J'ai mis une journée pour comprendre l'idée de la preuve.
On a $X^{q}-1=\phi_{q} \displaystyle\prod_{d \mid q\text{ et } d<q} \phi_{d}$
Or $ \displaystyle\prod_{d \mid q\text{ et } d<q} \phi_{d} = X^{q-1}-1$
Ainsi, en prenant $q=p^k$, on trouve $\boxed{X^{p^k}-1 = \phi_q (X^{p^k -1} -1)}$
Ainsi, $\phi_q = \dfrac{X^{p^k}-1}{X^{p^k -1} -1}$ Je retrouve la formule de Gai Requin 

Non, pas vraiment. Tu as plutôt réussi à démontrer une formule fausse à l'aide d'une autre formule fausse.

OShine

La question 8.b est moins dure que les précédentes, un simple calcul fournit

$\phi_1= \displaystyle\prod_{z \in \{1 \} } (X-z)=\boxed{X-1}$

Pour $\phi_2$ il suffit de remarquer que $2=2^1$ avec $2$ premier ce qui donne $\boxed{\phi_2= 1+X}$

Pour $\phi_3$ il suffit de remarquer que $3=3^1$ avec $3$ premier ce qui donne $\boxed{\phi_3= X^2+X+1}$

Pour $\phi_4$ il suffit de remarquer que $4=2^2$ avec $2$ premier ce qui donne $\boxed{\phi_4= X^2+1}$

Pour $\phi_5$ il suffit de remarquer que $5=5^1$ avec $5$ premier ce qui donne $\boxed{\phi_5= X^4+X^3+X^2+X+1}$

Je ne trouve pas $\phi_6$...

raoul.S

OShine a dit :

je ne comprends pas pourquoi la formule n'est pas correcte...

Tiens on va la vérifier sur un calcul :

je prends $q=4$, je devrais obtenir $X^3-1=\phi_1\phi_2$. Or $\phi_1=X-1$ et $\phi_2=X+1$...

OShine

Raoul.S ok merci du coup je ne comprends pas l'idée pour résoudre la question 8.a.

Amédé

$\displaystyle\prod_{d \mid q\text{ et } d<q}{ \phi_{d}(X)} =\prod\limits_{i=0}^{k-1}{\phi_{p^{i}}(X)}=\prod\limits_{d|p^{k-1}}{\phi_{d}(X)}\underset{7}{=}???$ 

OShine

Je n'ai pas compris. 

Amédé

Les diviseurs de $q$ strictement plus petits que $q$ sont les $p^{i}$ pour $0\leq i<k$. Sur le dernier membre de l'égalité la question 7 te dit quoi?

OShine

Amédé je ne comprends pas pourquoi les diviseurs de $q$ seraient forcément de la forme $p^i$ avec $0 \leq i <k$.
À vrai dire, je ne comprends rien à ta méthode.
Quelqu'un comprend l'indication présente ici ? 

JLapin

De quel sujet s’agit-il ?

OShine

J'ai finalement compris l'idée ! Ce n'était pas compliqué en fait.
On applique la question $7$ pour $n=p^k $ et $n=p^{k-1}$.
On obtient $\displaystyle X^{p^k}-1= \prod_{d \mid p^k} \phi_d$ et  $\displaystyle X^{p^k -1}-1= \prod_{d \mid p^k -1} \phi_d$
Ainsi, $\dfrac{X^{p^k}-1}{X^{p^k -1}-1} = \dfrac{\displaystyle \prod\nolimits_{d \mid p^k} \phi_d}{\displaystyle\prod\nolimits_{d \mid p^k -1} \phi_d}$.
Le quotient va se simplifier il va rester qu'un terme.
Les diviseurs de $p^k$ étant les $p^i$ avec $0 \leq i \leq q$ on obtient immédiatement : $\boxed{\dfrac{X^{p^k}-1}{X^{p^k -1}-1} = \phi_{p^k} }$.
Par contre je bloque pour trouver $\phi_6$ ...

gai requin

Tu m'as mal lu ici !

OShine

J'ai mal lu quoi ? Je trouve la même chose ...

gai requin

L'exposant de $X$ au dénominateur est $p^{k-1}$ et pas $p^k-1$ !

OShine

D'accord merci. 

gai requin

Pour $\Phi_6$, il n'y a pas beaucoup de racines $6$-ièmes primitives de l'unité...

OShine

Oui c'est vrai. Il n'y a pas plus rapide ? 

Je voulais utiliser $X^6-1= \phi_1 \phi_2 \phi_3 \phi_6$ ce qui donne $(X^3+2X^2+2X+1) \phi_6 = X^6-1$ et après je n'ai pas réussi à poursuivre.

Résolvons $X^6=1$. Les solutions sont les $X_k = e^{  2i k \pi / 6}=e^{  i k \pi / 3}$ avec $k \in [|0,5|]$

$X_0=1$ n'est pas une racine primitive.
$X_1= e^{  i  \pi / 3}$ est une racine primitive.
$X_2= e^{  2i  \pi / 3}$ n'est pas une racine primitive.
$X_3= e^{  3i  \pi / 3}$ n'est pas une racine primitive.
$X_4= e^{  4i  \pi / 3}$ n'est pas une racine primitive.
$X_5= e^{  i 5 \pi / 3}$ est une racine primitive.

Donc $P_6 = \{  e^{  i  \pi / 3} ,  e^{ - i  \pi / 3} \}$

Ainsi $\phi_6 = \displaystyle\prod_{z \in P_6} (X-z)=(X- e^{  i  \pi / 3} )(X- e^{ - i  \pi / 3})=X^2-2Re( e^{  i  \pi / 3} ) X+1$

Finalement $\boxed{\phi_6 = X^2- X+1}$

OShine

Voici la suite, je pense m'arrêter à la question $10$. Je coince un peu sur la question 9.a. La suite parle de série entière et je n'ai pas les connaissances suffisantes.

Je conjecture que $\phi_n(0)=1$. J'ai tenté une récurrence mais je ne vois pas comment faire le lien entre $P_n$ et $P_{n+1}$.

OShine

Finalement j'ai trouvé la question 9a, la 9b m'a l'air bien plus difficile. 

Question 9a : 
Montrons par récurrence forte sur $n$ la propriété $P_n$ : $\forall n \geq 2, \ \phi_n(0)=1$
$P_2$ est vraie car $\phi_2(0)=1$
Supposons $P_k$ vraie pour tout $k \in [|0,n-1|]$ et montrons $P_{n}$
On a $0^n-1=\displaystyle\prod_{d \mid n} \phi_d (0)=\phi_1(0) \phi_{n} (0) \displaystyle\prod_{d \mid n \ \ \text{et} \ d \ne 1 \ \text{et} \ d \ne n} \phi_d (0)$
D'après l'hypothèse de récurrence, on a $ \displaystyle\prod_{d \mid n \ \ \text{et} \ d \ne 1 \ \text{et} \ d \ne n} \phi_d (0)=1$
Or $\phi_1(0)=-1$. 
Donc $0^n-1= -1 = - \phi_n(0)$. Enfin, $\phi_n(0)=1$
On a montré par récurrence forte sur $n$ que $\boxed{\forall n \geq 2 \ \ \phi_n(0)=1}$
Je tenterai la question 9b demain, car elle va me prendre du temps je le sens.

gai requin

Oui pour 9)a), preuve par récurrence.
9)b) Si $n$ a un seul facteur premier $p$, $\Phi_n(1)=p$ et sinon, $\Phi_n(1)=1$.
10) Par récurrence, on peut effectuer une division euclidienne dans $\Z[X]$...