%+----------------------------------------------------------------------------+
%|                     Exercices division Euclidienne                         |
%+----------------------------------------------------------------------------+

\input exos
\fiche{Division euclidienne}

%------------------------------------------------------------------
\ex Décomposition en puissances croissantes
Soit $A ∈ 𝕂[X]$ de degré $>0$.
Montrer que pour tout polynôme $P ∈ 𝕂_n[X]$, il existe des polynômes
$P₀,P₁,…,P_n$ uniques vérifiant :
$$\cases{\deg P_i < \deg A\cr
P = P₀ + P₁A + … + P_nAⁿ.}$$

%------------------------------------------------------------------
\ex Linéarité du reste et du quotient
Soit $B ∈ 𝕂[X]$ de degré $n > 0$. On considère les applications :
$$\application Φ {𝕂[X]} {𝕂_{n-1}[X]} P R
  \quad\text{et}\quad
  \application Ψ {𝕂[X]} {𝕂[X]} P Q\quad
  \text{ avec }P = QB + R.$$

\qq Montrer que $Φ$ et $Ψ$ sont linéaires.
    Chercher leurs noyaux et leurs images.
\qq Montrer que $Φ(P₁P₂) = Φ(Φ(P₁)Φ(P₂))$.

%------------------------------------------------------------------
\ex Endomorphisme $P ↦ AP \bmod B$
Soit $E = 𝕂₃[X]$, $A = X⁴-1$, $B = X⁴-X$
et $\application φ E E P
    {\text{reste de la div. euclid. de } AP \text{ par } B.}$

Chercher $\Kerφ$, $\Imφ$.

\reponse{$\Imφ = ⦃P ∈ E$ tel que $X-1 │ P⦄$,
         $\Kerφ = \vect(X³+X²+X)$.}

%------------------------------------------------------------------
\ex Congruences
Soient $P ∈ 𝕂[X]$, $a,b∈𝕂$ distincts, et $α = P(a)$, $β = P(b)$.

\qq Quel est le reste de la division euclidienne de $P$ par $(X-a)(X-b)$ ?
    \reponse{$\dfrac {α(b-X) + β(X-a)}{b-a}$.}
\qq Trouver le reste de la division euclidienne de
    $(\cosθ + X\sinθ)ⁿ$ par $X²+1$.
    \reponse{$\cos nθ + X\sin nθ$.}

%------------------------------------------------------------------
\ex Congruences
Déterminer les polynômes $P ∈ ℚ₃[X]$ divisibles par $X+1$ et
dont les restes des divisions euclidiennes par $X+2,X+3,X+4$ sont égaux.
\reponse{$P = λ((X+2)(X+3)(X+4)-6)$.}

%------------------------------------------------------------------
\ex Calcul de pgcd
Calculer le pgcd de $P$ et $Q$ pour :

\qq $P=X⁴+X³-3X²-4X-1$,    $Q=X³+ X²-X-1$.       \reponse{$X+1$}
\qq $P=X⁴-10X²+1$,         $Q=X⁴-4X³+6X²-4X+1$.  \reponse{$1$}
\qq $P=X⁵-iX⁴+X³-X²+iX-1$, $Q=X⁴-iX³+3X²-2iX+2$. \reponse{$X²-iX+1$}

%------------------------------------------------------------------
\ex Coefficients de Bézout
Montrer que les polynômes $P$ et $Q$ suivants sont premiers entre eux.
Trouver $U,V ∈ 𝕂[X]$ tels que $UP + VQ = 1$.

\qq $P=X⁴+X³-2X+1$, $Q=X²+X+1$. \reponse{$7U=X+3$, $7V=-X³-3X²+X+4$.}
\qq $P=X³+X²+1$,    $Q=X³+X+1$. \reponse{$3U=2X²-X+1$, $3V=-2X²-X+2$.}

%------------------------------------------------------------------
\ex Division de $(X+1)ⁿ - Xⁿ - 1$ par $X² + X + 1$
Chercher le reste de la division euclidienne de
$(X+1)ⁿ - Xⁿ - 1$ par $X² + X + 1$.

\reponse{Substituer $j$ à $X$ $⇒$
         $R = \cases{(-1)ⁿ - 2           &si $n ≡ 0 \pmod 3$ \hfill\cr
                     ((-1)^{n+1}-1)(X+1)  &si $n ≡ 1 \pmod 3$ \hfill\cr
                     ((-1)ⁿ+1)X          &si $n ≡ 2 \pmod 3$.}$}

%------------------------------------------------------------------
\ex Ensi P 90
Pour quels $n∈ ℕ$ le polynôme $(1+X⁴)ⁿ - Xⁿ$ est-il divisible par
$1+X+X²$ dans $ℝ[X]$ ?
\reponse{$n≡ 0\pmod 6$.}

%------------------------------------------------------------------
\ex Division de $(X-2)^{2n} + (X-1)ⁿ - 1$ par $(X-1)(X-2)$
Soit $P_n = (X-2)^{2n} + (X-1)ⁿ - 1$.

\qq Montrer que $P_n$ est divisible par $X-1$ et par $X-2$.
    On note $Q₁$ et $Q₂$ les quotients correspondant.
\qq Montrer que $P_n$ est divisible par $(X-1)(X-2)$ et que le quotient est
    $Q₂-Q₁$.
\qq Montrer que ce quotient est égal à :
    $$((X-2)^{2n-2} - (X-2)^{2n-3} + … - (X-2) + 1)
    + ((X-1)^{n-2} + (X-1)^{n-3} + … + (X-1) + 1).$$
    \reponse{Développer le produit.}

%------------------------------------------------------------------
\ex Calcul de restes
Trouver les restes des divisions euclidiennes :

\qq de $X^{50}$ par $X²-3X+2$.          \reponse{$(2^{50}-1)X + 2-2^{50}$.}
\qq de $(X+√3)^{17}$ par $X²+1$.        \reponse{$2^{16}(X-√3)$.}
\qq de $X^8 - 32X² + 48$ par $(X-√2)³$.\reponse{$192(X-√2)²$.}

%------------------------------------------------------------------
\ex Divisibilité
Trouver $λ, µ ∈ ℂ$ tels que $X²+X+1$ divise $X⁵ + λ X³ + µ X² + 1$.
\reponse{$λ = µ = -1$.}

%------------------------------------------------------------------
\ex Congruences
Soit $P ∈ 𝕂[X]$ tel que les restes des divisions de $P$ par $X²+1$
et $X²-1$ valent respectivement $2X-2$ et $-4X$.
Quel est le reste de la division de $P$ par $X⁴-1$ ?
\reponse{$-3X³ + X² - X - 1$.}

%------------------------------------------------------------------
\ex $\pgcd(Xⁿ-1,X^m-1)$
Soient $m,n ∈ ℕ^*$. Chercher $\pgcd( Xⁿ-1,X^m-1)$.
\reponse{$n = qm+r ⇒ Xⁿ-1 ≡ X^r-1 \pmod{X^m-1}$.
         On applique la méthode des divisions euclidiennes entre $n$ et $m$
         $⇒$ pgcd $= X^{n ∧ m} - 1$.}

%------------------------------------------------------------------
\ex Degré minimal dans la formule de Bézout
Soient $P,Q ∈ 𝕂[X]$ non nuls et $D = \pgcd(P,Q)$.

\qq   Démontrer qu'il existe $U,V ∈ 𝕂[X]$ uniques tels que :
      $\cases{ UP + VQ = D \cr
               \deg  U < \deg  Q - \deg  D \hfill\cr
               \deg  V < \deg  P - \deg  D .}$

\qq   Montrer que la méthode des divisions euclidiennes fournit $U$ et $V$.
      \reponse{Récurrence.}

%------------------------------------------------------------------
\ex Application $(U,V) ↦ UA + VB$
Soient $A,B ∈ 𝕂[X]$, $p = \deg A$, $q = \deg B$.
On considère l'application :
    $$\application Φ {𝕂_{q-1}[X] × 𝕂_{p-1}[X]}
                     {𝕂_{p+q-1}[X]} {(U,V)} {UA + VB.}$$

Démontrer que : $A ∧ B = 1 ⇔ Φ$ est bijective.

%------------------------------------------------------------------
\ex $\pgcd(P(X),P(-X))$ et $\ppcm(P(X),P(-X))$
Soit $𝕂$ un corps de caractéristique diffrénete de~$2$ et $P ∈ 𝕂[X]$.
Démontrer que $\pgcd(P(X),P(-X))$ et $\ppcm(P(X),P(-X))$
sont pairs ou impairs.

%------------------------------------------------------------------
\ex $A∘P │ B∘P ⇒ A │ B$
Soient $A,B,P ∈ 𝕂[X]$ avec $P$ non constant.
Montrer que si $A∘P$ divise $B∘P$, alors $A$ divise $B$.

\bye
