Division euclidienne polynôme

Rien ne t'interdit de regarder sur un exemple et d'essayer d'en tirer des généralités. Par exemple, effectue "complètement" (en la posant comme division c'est mieux) la division euclidienne de $X^{11} - 1$ par $X^3 - 1$ et regarde ce que tu trouves (et les quotients et restes intermédiaires, i.e. tant que la division n'est pas terminée).

$20=3\times 2+14$ le reste de la division euclidienne de $20$ par $3$ est aussi le reste de la division euclidienne de $14$ par $3$.
Un reste par division euclidienne par $3$ consiste à soustraire autant de fois que possible le nombre $3$ (c'est à dire que la soustraction donne un résultat positif ou nul). Le nombre obtenu à la fin du processus est le reste (s'il ne reste rien cela signifie que le nombre est divisible par $3$).

Par ailleurs,
Si $n-p\geq p$ qu'est-ce qui t'empêche de diviser $x^{n-p}-1$ par $x^p-1$?

PS:
L'action répétée de la formule $X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$ te garantit que tu vas obtenir à la fin un polynôme qui est soit $0$ soit un polynôme de degré plus petit que $p$.
Car à chaque fois que tu utilises cette formule cela te renvoie un polynôme de degré auquel on a soustrait $p$ par rapport à celui qu'on avait en entrée.

PS2:
Il est aisé d'anticiper avec la formule $X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$ ce que sera le reste de la division euclidienne de $x^m-1$ par $x^p-1$. A chaque fois qu'on applique cette formule on soustrait $p$ au polynôme en entrée.

Si on sait que $X^{pk}-1$ est divisible par $X^p-1$ on peut aller plus vite.

Si $n=pk+r$ avec $0\leq r<p$

On a aussi, sauf erreur, l'égalité: $X^n-1=(X^{kp}-1)X^{n-kp}+X^{n-kp}-1=(X^{kp}-1)X^{r}+X^{r}-1$

Gai Requin: je ne dis pas le contraire. Mais autant exploiter au mieux ce que OS met sur la table (et qu'il n'exploite pas bien). C'est lui qui pose la question, pas moi. B-)-

Oshine, tu ne nous facilites pas la tâche !!
Beaucoup de monde a répondu à côté de la plaque car la question de départ n'était pas claire... parce que tu as eu peur d'avouer que tu lisais encore un corrigé sans le comprendre.

Comment voulais-tu que l'on comprenne avant que tu ne nous dises que pour CHAQUE valeur $n$, on définit les quotient et reste $Q_n$ et $R_n$ de $X^n-1$ par $X^p-1$ ?

Je suppose que le corrigé essaie d'établir une relation de récurrence entre $Q_n$ et $Q_{n-p}$ et entre $R_n$ et $R_{n-p}$.
Cette relation est TRIVIALE en utilisant la définition de la division euclidienne.

Il n'y a plus qu'à travailler.
Si tu ne vois toujours pas, écris la TOTALITÉ de ce que tu as essayé d'écrire et explique pourquoi TU n'arrives pas à avancer. Il ne sert à rien de comprendre comment le corrigé s'en est sorti.

On y retourne?

Si $n=mp+m'$ alors le reste dans la division euclidienne de $n$ par $p$ est le même que le reste de la division de $m'$ par $p$.

OS:

Le calcul modulo $X^p-1$ est beaucoup plus simple que ce que tu écris.
Pour reprendre tes notations $n=pq+r$

$X^n-1=X^{pq+r}-1=\left(X^{p}\right)^qX^r-1\equiv X^r-1\mod{X^p-1}$

Car $X^p-1\equiv 0\mod{X^p-1}$ est équivalent à $X^p\equiv 1\mod{X^p-1}$

(c'était déjà expliqué par Gai Requin plus haut)

OS:

Tout est dit dans ce fil.

Encore un essai: si $m$ et $n$ sont tels que $m-n$ est divisible par $p$ alors $m$ et $n$ ont le même reste dans la division euclidienne par $p$

($m,n,p$ appartiennent à un anneau euclidien comme $\mathbb{Z}$,$K[X]$ avec $K$ un corps)

Pour chaque polynôme $X^n-1$ est associé son reste et son quotient dans la division par le polynôme $X^p-1$ qui sont deux polynômes uniques. (quelqu'un d'autre l'a déjà expliqué plus haut).
Et sans surprise le quotient est nommé $Q_n(X)$ et le reste $R_n(X)$.

Par ailleurs, ce n'est pas parce qu'on a une relation du type $n=pq+r$ que dans la division euclidienne de $n$ par $p$ le quotient est $q$ et le reste $r$.
Cependant il y a bien une relation (déjà indiquée plus haut) entre le reste dans la division euclidienne de $n$ par $p$ et le reste de la division de $r$ par $p$.

OS:
Ce que je t'ai dit permet de montrer la deuxième relation que tu as mise en rouge dans ton premier message.

Il faut prendre en compte la relation que tu donnes:

$\displaystyle X^n-1=\underbrace{(X^p-1)X^{n-p}}_{\text{multiple de }X^p-1} +X^{n-p}-1$

PS:
En réalité, il y a seulement à traduire formellement les définitions données pour $Q_m(X)$ et $R_m(X)$

(c'est à dessein que j'introduis $m$ un entier strictement positif quelconque).

Ces deux quantités sont uniques.

PS2:
$22=5\times 3+7=5\times 3+\left(2\times 3+1\right)=(5+2)\times 3+1=7\times 3+1$

OS:

On te dit que $X^n-1=Q_n(X)\left(X^p-1\right)+R_n(X)$ et $X^{n-p}-1=Q_{n-p}(X)\left(X^p-1\right)+R_{n-p}(X)$

On dit un peu plus que cela mais voyons voir ce que tu fais de ces informations.

Sinon, en conjecturant le résultat (ce que je ne trouve pas forcément fou puisque "humainement" on a envie que ce soit ça), et en exploitant quelque chose du type $a^{k} - b^{k}$, on peut être direct. Je ne sais pas si c'est un bon exercice mais je pense que c'est intéressant de faire cette petite preuve en une ligne.

OS:

Je ne veux pas être grossier mais si on te dit $A=5+B$
et $B=7$.
Tu ne sais pas calculer $A$?
Pour moi ce qu'on te demande est une question qui très proche de ça.

Tu sais que:

$X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$ (c'est toi qui l'a mis sur la table)

et l'énoncé introduit des notations, on te dit que $X^{n-p}-1=Q_{n-p}(X)\times (X^p-1)+R_{n-p}(X)$ (*)

Tu ne vois toujours pas le rapport?

*: l'énoncé dit plus mais pour le moment voyons ce que tu vas faire de tout ceci.

OS a écrit:

et on conclut par unicité de la division euclidienne.

Cela demanderait à être précisé selon moi.

OS a écrit:

Par unicité du reste et du quotient dans une division euclidienne

Pardon mais cela peut être pris pour de l'esbroufe ici.

C'est tout de même le même algorithme !!
Il est même plus compliqué pour les entiers que pour les polynômes puisque pour les entiers, on ne sait pas à l'avance si on va devoir considérer un paquet de 1, 2, 3, n chiffres au départ, alors que pour les polynômes, il suffit de regarder le monôme non nul de plus haut degré.

Tu viens également d'avouer que tu n'avais pas parfaitement compris l'algorithme jusque là... D'ailleurs, tu l'as mal exprimé puisque tu as dit que l'on redivisait le "premier reste", alors que ce terme n'est pas adéquat puisque ce n'est PAS encore LE reste.