Racines primitives

OShine

D'accord merci.

Question $9b$.

Montrons par récurrence sur $n \geq 2$ la propriété $Q_n$ : "Si $n$ a un seul facteur premier $p$ alors $\phi_n(1)=p$ sinon $\phi_n(1)=1$"
$Q_2$ est vraie car $\phi_2(1)=1+1=2$
Supposons $Q_k$ vraie pour tout $k \in [|2,n-1|]$ et montrons $Q_n$.
Si $n$ a un seul facteur premier alors $n=p^k$ et d'après la question $8a$ on a $\phi_n(1)=1+1+ \cdots +1 =p$ donc $Q_n$ est vraie. 
Sinon $n$ s'écrit sous la forme $n=p_1 ^{\alpha_1} p_2 ^{\alpha_2} \cdots p_r ^{\alpha_r}$ avec les $p_1, \cdots, p_r$ distincts et $r \geq 2$
Je bloque ici.

bisam

Ta propriété $Q_n$ est mal formulée.

Tu connais beaucoup de nombres entiers qui n'ont pas de facteur premier ?

lourrran

Je n'avais pas voulu relever.
Il a mal recopié le message de gai requin. Il y a seul et p qui ont disparu dans la copie.
Ca ne peut vraiment pas être une faute de frappe, et donc, il n'aurait pas vu à quel point ces mots 'seul'  et 'p' étaient importants ?

Je mets ça sur le compte de la négligence.

OShine

Merci j'ai corrigé.

Les diviseurs de $p_1 ^{\alpha_1} \cdots p_r ^{\alpha_r}$ sont de la forme $p_1 ^{\beta_1} \cdots p_r ^{\beta_r}$, où $\forall i \in [|1,r|], \ \beta_i \leq r$.

Or, $X^n-1= \displaystyle\prod_{d \mid n} \phi_d$ et $X^1-1= \displaystyle\prod_{d \mid 1} \phi_d = \phi_1$
Donc $\dfrac{X^n-1}{X-1}=\dfrac{ \prod_{d \mid n} \phi_d}{\phi_1}= \displaystyle\prod_{\substack{d \mid n  \\ d \ne n, \ d \ne 1}} \phi_d$
Mais $X^n-1=(X-1)(X^{n-1} + \cdots + X+1)$ donc $1+X+ \cdots + X^{n-1} = \displaystyle\prod_{\substack{d \mid n  \\ d \ne n, \ d \ne 1}} \phi_d$
En évaluant en $1$, on obtient $\boxed{n=  \displaystyle\prod_{\substack{d \mid n  \\ d \ne n, \ d \ne 1}} \phi_d (1)}$
Je bloque à ce stade.

Zgrb

Pourquoi les beta i seraient plus petit que r ?

OShine

Les beta i sont inférieurs aux alpha i erreur de frappe. 

lourrran

Tu as mal corrigé. La phrase n'a toujours pas de sens.
Si n a un seul facteur premier p alors ... ...

OShine

D'accord.

OShine

Voici la question 9.b rédigée correctement. Vraiment pas facile comme question. 
Montrons pour tout $n \geq 2$, par récurrence forte la propriété : $Q_n$ : "Si $n$ a un seul facteur premier $p$ alors $\phi_n(1)=p$, sinon $\phi_n(1)=1$".
$Q_2$ est vraie car $\phi_2(1)=1+1=2$
Supposons $Q_k$ vraie pour tout $k \in [|2,n-1|]$ et montrons $Q_n$. 
Si $n$ a un seul facteur premier $p$ alors il existe un entier $k$ tel que $n=p^k$ et $\phi_n(1)=1+1 + \cdots + 1 =p$
Sinon, $n$ a au moins deux facteurs premiers. On écrit $n= \displaystyle\prod_{k=1}^r p_i ^{\alpha_i}$ avec $r \geq 2$
On remarque que les diviseurs de $n$ s'écrivent sous la forme $ \displaystyle\prod_{k=1}^r p_i ^{\beta_i}$ avec $1 \leq \beta_i \leq r$
$\dfrac{X^n-1}{X-1} =\phi_n \displaystyle\prod_{d \mid n \ \ d \ne 1,d} \phi_d$
Or $\dfrac{X^n-1}{X-1}= 1+ X+ \cdots + X^{n-1}$
Donc $\boxed{n=\phi_n( 1) \displaystyle\prod_{d \mid n \ \ d \ne 1,d} \phi_d(1)}$
Les seuls termes différents de $1$ sont des $\phi_{p_i ^k} (1)$ donc $\displaystyle\prod_{d \mid n \ \ d \ne 1,d} \phi_d(1)=\displaystyle\prod_{i=1}^r \displaystyle\prod_{k=1}^{\beta_i} \phi_{p_i ^k} (1)= \displaystyle\prod_{i=1}^r p_i ^{\beta_i} = n$
Finalement $\boxed{\phi_n(1)=1}$
On a montré par récurrence forte sur $n$ la propriété $Q_n$.

OShine

Pour la question $10$ je n'ai pas compris la méthode de Gai Requin avec la division euclidienne dans $\Z[X]$. Le rapport parle aussi de cette seconde méthode.
On a $X^n- 1 = \phi_n \displaystyle\prod_{ d \mid n \ \ d <n } \phi_d$. Posons $P =  \displaystyle\prod_{ d \mid n \ \ d <n } \phi_d$
Ce qui donne $\boxed{X^n -1 = \phi_n P}$
$\phi_n$ est le quotient de la division euclidienne de $X^n-1$ par $P$ dans $\Q[X]$. Mais après je ne vois pas.

gai requin

Par hypothèse de récurrence, ton polynôme $P$ est un polynôme unitaire de $\Z[X]$.

Donc il existe $Q,R\in\Z[X]$ tels que $X^n-1=PQ+R$ avec $\deg R<\deg P$.
C'est aussi la division euclidienne de $X^n-1$ par $P$ dans $\C[X]$ donc, par un argument d'unicité, on obtient $R=0$ et $Q=\Phi_n\in\Z[X]$.

OShine

Je n'ai pas compris c'est où qu'on utilise que $P$ est unitaire dans le raisonnement…

gai requin

Peut-on effectuer la division euclidienne de $X$ par $2X$ dans $\Z[X]$ ?

JLapin

Essaye de montrer par récurrence forte sur le degré de A que si A et B sont deux polynômes à coefficients entiers avec B unitaire, alors le quotient et le reste de la division euclidienne de A par B sont à coefficients entiers.

OShine

@JLapin
Ok merci je vais essayer de le démontrer. 
Je n'ai jamais étudié la théorie sur la division euclidienne dans $\Z[X]$. 
On a $X = (2 X) \times \dfrac{1}{2}$ et $1/2$ n'appartient pas à $\Z[X]$. 
Dans le cours de MPSI j'ai pour $K=\R$ ou $K=\C$ : 
Soit $A$ et $B$ des polynômes avec $B \ne 0$. Il existe un unique couple $(Q,R)$ de polynômes de $K[X]$ vérifiant $A=BQ+R$ et $\deg R < \deg B$.

OShine

Je ne trouve pas l'idée de la preuve.
Posons $n= \deg A$ et soient $A$ et $B$ deux polynômes à coefficients dans $\Z$ avec $B$ unitaire. 
Supposons $P_n$ vraie. Soit $A$ de degré $n+1$. On pose $A=a_{n+1} X^{n+1}+ \cdots + a_1 X+a_0$ et $B=X^m + \cdots +b_1 X+b_0$}
Dans $\C[X]$ on peut écrire $A=B Q + R$ avec $\deg R < \deg B$
Après je ne vois pas.

OShine

Le rapport du jury parle de cette idée mais bon c'est hors programme c'est étrange de donner une méthode hors programme sans la démontrer. 

JLapin

J'ai parlé de récurrence forte.

Et d'où vient ce problème d'ailleurs ?

OShine

XENS maths A 2019.
Ton exercice n'est pas facile du tout. J'ai mis une journée à y réfléchir. 

Procédons par récurrence sur le degré de $A$. 
Soit $B \in \Z[X]$ un polynôme unitaire.
Posons $P_n$ : pour tout $A \in \Z[X]$ tel que $\deg A \leq n$, le quotient et le reste de la division euclidienne de $A$ par $B$ effectuée dans $\Q[X]$ sont des polynômes de $\Z[X]$.

Soit $A$ est constant. Si $\deg B \leq 0$ comme $B$ est unitaire alors $B=1$ et $A= A \times B+0$. Ainsi, $(Q,R)=(A,0) \in \Z^2[X]$. Si $\deg B \geq 1$ alors $A=B \times 0+A$. Donc $(Q,R)=(0,A) \in \Z^2[X]$. Donc $P(0)$ est vraie.

Soit $A$ non constant. Supposons $P_n$ vraie. Soit $A \in \Z[X]$ tel que $\deg A \leq n+1$.
Si $\deg A \leq n$ alors $P_n$ s'applique.
Supposons $\deg A =n+1$.
Si $\deg B \geq n+2$ alors la division euclidienne de $A$ par $B$ dans $\Q[X]$ est $A = B \times 0+A$ et donc $(Q,R)=(0,A) \in \Z^2[X]$.
Si $\deg B \leq n+1$ alors posons $A= \displaystyle\sum_{k=0}^{n+1} a_k X^k$ et $B=\displaystyle\sum_{k=0}^{m} b_k X^k$ avec $b_m =1$
Posons $\tilde{A}= A- a_{n+1} X^{n+1- m} B$ de sorte que $\deg \tilde{A} < \deg A$ car le terme en $a_{n+1} X^{n+1}$ se simplifie.
Effectuons la division euclidienne de $\tilde{A}$ par $B$ : 
On a donc dans $\Q[X]$ : $\tilde{A}=B  \tilde{Q} + \tilde{R}$ avec $\deg \tilde{R} < \deg B$
Comme $\deg \tilde{A} < \deg A =n+1$ alors d'après l'hypothèse de récurrence, ce qui est possible car $\tilde{A} \in \Z[X]$, on a $(\tilde{Q},\tilde{R}) \in \Z^2[X]$.
Or $A=\tilde{A} + a_{n+1} X^{n+1- m} B$ donc $\boxed{A=\left( a_{n+1} X^{n+1-m}+\tilde{Q} \right) B + \tilde{R}}$
Où $a_{n+1} X^{n+1-m}+\tilde{Q}  \in \Q[X]$ et $\tilde{R} \in \Q[X]$ avec $\deg \tilde{R} < \deg B$
Par unicité de la division euclidienne dans $\Q[X]$, on a $(Q,R)=(a_{n+1} X^{n+1-m}+\tilde{Q} , \tilde{R} ) \in \Z^2[X]$ car $\Z[X]$ est un anneau. 
Donc $P_{n+1}$ est vraie.

bisam

@Oshine : Si tu as mis une journée à montrer ce résultat, c'est bien la preuve que tu es loin de maîtriser ton cours. C'est exactement la preuve du théorème de division euclidienne que tu viens d'écrire, et celle-ci ne fait qu'utiliser l'algorithme de division euclidienne appris... en CM1 !

OShine

En effet, la preuve est dans le cours de MPSI. Je me suis trouvé une lacune. 

En posant $A=\displaystyle\sum_{k=1}^n a_k X^k$ et $B=\displaystyle\sum_{k=1}^m b_k X^k$

L'idée clé est de preuve est de considérer le polynôme $A_1 = A -\dfrac{a_n}{b_m} X^{n-m} B$ pour baisser le degré. Le reste de la preuve n'est qu'une formalité. 

Si $B$ est unitaire on voit directement que $A_1$ sera à coefficient dans $\Z$ si $A$ et $B$ le sont. 

Je vais essayer de résoudre Q10 avec la seconde méthode proposée par le rapport du jury. 

pldx1

\[ \left(\forall\,question\in\mathrm{Questions}\right)\left(\exists\,poire\in\mathrm{Poires}\right)  \left({\rm repond}(poire,question)\wedge{\rm est\_fier\_de\_lui}(poire)\right) \]

Plus de détails après le retour du LateX

OShine

Bonjour, le rapport du jury dit que pour la question $10$ on peut raisonner par analyse des coefficients. Je tente donc cette méthode.
On a $X^n-1= \phi_n \displaystyle\prod_{d \mid n \ d <n } \phi_d$
Montrons par récurrence forte que $\forall n \geq 2 \ \ \phi_n \in \Z[X]$.
On a $\phi_2 = X+1 \in \Z[X]$ donc la propriété est vraie au rang $n=2$.
Supposons que $\forall k \in [|2,n-1 |]$ on ait $\phi_k \in \Z[X]$. 
Comme $\Z[X]$ est un anneau alors $\displaystyle\prod_{d \mid n \ d <n } \phi_d \in \Z[X]$.
On pose $\displaystyle\prod_{d \mid n \ d <n } \phi_d = \displaystyle\sum_{k=0}^m a_k X^k$ avec $a_m=1$ et $\forall k \in [|0,m|] \ a_k \in \Z$
On pose aussi $\phi_n =  \displaystyle\sum_{k=0}^{m'} b_k X^k$. On veut montrer que  $\forall k \in [|0,m'|] \ b_k \in \Z$
Or $\phi_n \displaystyle\prod_{d \mid n \ d <n } \phi_d = \left(  \displaystyle\sum_{k=0}^{m'} b_k X^k \right) \left( \displaystyle\sum_{k=0}^m a_k X^k  \right)$
Donc $\boxed{X^n -1 = \displaystyle\sum_{k=0}^{m +m'} \left( \displaystyle\sum_{i=0}^k b_k a_{k-i}  \right) X^k}$
Je bloque ici. C'est quoi ces erreurs Latex ? 

pldx1

Bonjour, $\def\RU{\mathfrak{U}} \def\pri{\mathbb{P}} \def\where{\qquad\mathrm{where}\;}$ Comme d'habitude, OShine tient à nous montrer qu'il ne comprend rien à rien... tout en tenant à ne pas nous montrer qu'il a déjà téléchargé tous les corrigés possibles. Un nouvel exemple de la propriété citée ci-dessus. On remarquera, entre autres perles: $\phi_{1}\phi_{2}\phi_{3}=X^{3}+2X^{2}+2X+1$ (sans doute sur le modèle 1+1+2=3) ; $p^{k-1}=p^{k}-1$ ; $\beta_{i}\leq r$ à la place de $\beta_{i}\leq\alpha_{i}$... tout en prétendant avoir corrigé. Les quelques points abordés sont extraits de
ECOLE POLYTECHNIQUE - ECOLES NORMALES SUPERIEURES
CONCOURS D'ADMISSION 2019
JEUDI 18 AVRIL 2019 - 8h00 - 12h00
FILIERE MP - Epreuve n° 1 : MATHEMATIQUES A
Sources:https://www.doc-solus.fr/prepa/sci/adc/pdf/enonces.pdf/2019/MP_MATHS_X_1_2019.enonce.pdf Je reprends du début, en utilisant systématiquement la méthode de descente (à la Fermat), plutôt que la méthode de propagation (récurrence).

1. On considère $\RU$ l'ensemble des racines de l'unité, c'est à dire \[ \left\{ z\in\C\left|\exists m\in\N^{*}:z^{m}=1\right.\right\} \] Pour $z\in\RU$, l'ordre $o\left(z\right)$ de $z$ est défini comme le plus petit $m$ ayant cette propriété. $\RU$ est visiblement un groupe: (a) $1\in\RU$ (b) si $z\in\RU$ alors $z\neq0$ et $\left(1/z\right)\in\RU$ puisque $\left(1/z\right)^{o\left(z\right)}=1/\left(z^{o(z)}\right)=1$ (c) $\RU$ est clos par multiplication: on voit aisément que $\left(x\times y\right)^{o\left(x\right)\times o\left(y\right)}=1$ lorsque $x,y\in\RU$.
2. Le théorème de factorisation dans $\C\left[X\right]$ nous montre que \[ X^{n}-1=\prod_{z}\left\{ X-z\left|z\in\C:z^{n}=1\right.\right\} \] Il y a donc $n$ racines $n$-ièmes de l'unité. Chacune possède un ordre et cet ordre divise $n$: c'est le théorème de Lagrange: $o\left(z\right)$ divise le reste de $n$ dans la division par $o\left(n\right)$. On a donc \[ X^{n}-1=\prod_{d}\left\{ \prod_{z}\left\{ X-z\left|z\in\RU:o\left(z\right)=d\right.\right\} \left|d\in\N:d|n\right.\right\} \] C'est exactement la définition de \[ X^{n}-1=\prod_{d|n}\Phi_{d} \] On remarque, au passage, que cela prouve la relation : \[ \sum_{d|n}\phi\left(d\right)=n \]
3. Pour $p$ premier et $k$entier, $k\geq1$, on a: \[ \Phi\left[p^{k}\right]\left(X\right)=\frac{X^{\left(p^{k}\right)}-1}{X^{\left(p^{k-1}\right)}-1}\times\left(X^{\left(p^{k-1}\right)}-1\right) \] Pour $k=1$, cela donne $\Phi_{p}=\sum_{j=0}^{p-1}X$. Et pour les autres puissances $\Phi\left[p^{k}\right]\left(X\right)=\Phi\left[p\right]\left(X^{\left(p^{k-1}\right)}\right)$. On en déduit $\Phi_{p}\left(0\right)=\Phi\left[p^{k}\right]\left(0\right)=1$ et $\Phi_{p}\left(1\right)=\Phi\left[p^{k}\right]\left(1\right)=p$.
4. Au vu du § précédent, on a $\Phi_{1}=X-1$, $\Phi_{2}=X+1$, $\Phi_{3}=X^{2}+X+1$, $\Phi_{4}=X^{2}+1$, $\Phi_{5}=X^{4}+X^{3}+X^{2}+X+1$. Il reste \[ \Phi_{6}=\frac{X^{6}-1}{\Phi_{1}\Phi_{2}\Phi_{3}}=\frac{X^{3}+1}{X+1}=X^{2}-X+1 \]
5. On a $\Phi_{2}\left(0\right)=1$. Pour tout $n>2$, $\phi\left(n\right)=\mathrm{dg}\left(\Phi_{n}\right)$ est pair et donc $\Phi_{n}\left(0\right)$ est le produit des racines. Comme les racines sont simples et conjuguées deux par deux, ce produit vaut $1$. On peut aussi badigeonner cela à la moutarde forte. Bilan $\Phi_{1}\left(0\right)=-1$ et sinon $\Phi_{n}\left(0\right)=+1.$
6. On partage l'ensemble des diviseurs de $n\ge2$ en trois sous-ensembles: $A=\left\{ 1\right\} $, $B$ formé des diviseurs avec un seul facteur premier, $C$ formé par les autres diviseurs. On a donc \begin{eqnarray*} n=\left(\frac{X^{n}-1}{X-1}\right)_{X=1} & = & \prod\left\{ \Phi_{d}\left(1\right)\left|d|n,d\neq1\right.\right\} \\ & = & \prod\left\{ \Phi_{d}\left(1\right)\left|d\in B\right.\right\} \times\prod\left\{ \Phi_{d}\left(1\right)\left|d\in C\right.\right\} \end{eqnarray*} Le premier groupe de facteurs est exactement la décomposition de $n$ en ses facteurs premiers, de sorte que le deuxième groupe de facteurs vaut $1$. Ce sont des entiers: ils valent tous $\pm1$. Supposons qu'il existe un $n$ tel que $\Phi_{d}\left(1\right)=-1$. Il existerait alors un $n$ minimal ayant cette propriété. Mais alors tous les facteurs impliqués seraient positifs sauf un seul, ce qui est impossible. On peut donc, ici aussi, ranger la moutarde forte.
7. Montrons que pour tout $n$, $\Phi_{n}\left(X\right)\in\Z\left[X\right]$. Supposons qu'il y ait une exception. Il y aurait alors un $n$ minimal pour cette propriété, et l'on aurait \[ X^{n}-1=\Phi_{n}\times B\left(X\right) \where B\left(X\right)= \prod\left\{ \Phi_{d}\left| d\in \N, d|n, d \lt n \right. \right\} \] Identifions: \[ X^{n}-1=\left(\sum_{j=0}^{j=u}a_{j}X^{j}\right)\left(\sum_{k=0}^{k=w}b_{k}X^{k}\right) \] où l'on s'est simplifié les notations en posant $\phi\left(n\right)=u$ et $n-\phi\left(n\right)=w$.
   1. Les $\Phi_{m}$ sont tous unitaires (dans $\C\left[X\right]$). On a donc $a_{u}=b_{w}=1$. L'identification est OK au degré $n$.
   2. Puisque $\Phi_{1}\in\Z\left[X\right]$, on a $n\neq1$. D'après ce qui précède, $a_{0}=1$ et $b_{0}=-1$: l'identification est OK au degré $0$.
   3. Il reste les équations $\sum_{j+k=m}a_{u-j}b_{w-k}=0$ pour $m$ allant de $1$ à $u-1$. Comme $n$ est minimal, tous les $b_{k}$ sont entiers. Comme $b_{w}=1$, nos équations peuvent s'écrire: \[ a_{u-m}=a_{u-m}b_{w}=-\sum_{j=0}^{j=m-1}a_{u-j}b_{w+j-m} \]
   4. S'il existait un $a_{j}$ non-entier, il existerait un $m$ minimal et donc un $j=u-m$ maximal pour cette propriété. Mais alors, pour ce $j$ là, le second membre est entier: contradiction.
   5. On peut aussi remarquer que ce processus ne fait que copier l'algorithme de la division euclidienne par un polynôme unitaire: on peut donc aller droit à la conclusion. 
8. On remarquera que ces quelques propriétés constituent un tout petit morceau d'un sujet de 4 heures: le timing attendu est donc: une heure en tout, pas plus.

Cordialement, Pierre

raoul.S

$\left(\forall\,sujet\in\mathrm{Sujets}\right)\left(\exists\,poire\in\mathrm{Poires}\right)  \left({\rm corrige}(poire,sujet)\wedge{\rm est\_fier\_de\_lui}(poire)\right)$

Cordialement, raoul.S

OShine

pldx1 merci je vais examiner ta preuve dans le détail, ça m'a l'air clair.
Je n'ai pas regardé de corrigé juste les indications du rapport du jury.
D'ailleurs les corrigés des sujets de l'X je ne les comprends pas, donc je ne vois pas l'intérêt de les regarder.
Je comprends mieux en lisant le rapport du jury et en essayant les méthodes proposées. 

pldx1

Bonjour,

En résumé: proposer une "récurrence forte" pour démontrer toutes ces propriétés est assez loin d'être une indication pertinente. il ne s'agit pas d'élargir la zone de validité par un procédé de montée, mais de rétrécir la zone d'exception par un procédé de descente (au point de la réduire au vide). Trouver une preuve, ce n'est pas la même chose que valider/invalider un texte ayant des prétentions prouvatoires.

Et, évidemment, l'objectif d'un corrigé ne doit pas être de décrire ce qu'un candidat aurait dû faire (=contemplation lamentatoire du passé), mais de suggérer ce qu'un candidat raisonnablement préparé pourrait faire dans une situation analogue (=préparation active du futur).

Cordialement, Pierre.

OShine

Pierre je n'ai pas compris ton corrigé tant pis.
Tes solutions sont trop sophistiquées pour moi. Je n'ai pas le niveau pour les comprendre.