Racine commune à deux trinômes

Je suis plutôt d'accord avec la formule de GaBuZoMeu qu'on peut retrouver en écrivant $x^2 = -bx/a -c/a = -b'x/a' -c'/a'$

Il faut vraiment avoir envie de se couper les cheveux en quatre (ce que je peux comprendre, j'en suis adepte à l'occasion) pour trouver la solution commune (si elle existe) de deux équations du second degré. B-)-

GBZM.
On parle de polynômes du second degré dans ce fil si j'ai bien lu.
Sauf erreur, du système d'équations suivant : $$

\begin{array}{rcl}
ax^2+bx+c&=0 \\
a'x^2+b'x+c'&=0
\end{array}

$$ on déduit que : $$
(ab'-a'b)x+(ac'-a'c)=0

$$ La dernière équation étant obtenue en multipliant les deux membres de la première équation du système d'équations par $-a'$ et en multipliant les deux membres de la seconde équation du système par $a$, et finalement en ajoutant membre à membre ces deux égalités.

PS. Si on aime les déterminants on peut réécrire la dernière équation sous la forme : $$
\begin{vmatrix} a & a' \\ b & b' \end{vmatrix}x+\begin{vmatrix} a & a' \\ c & c' \end{vmatrix}=0.

$$ PS2. On trouve cette équation avec des déterminants dans le texte mentionné plus haut (mais pas obtenue de la même façon si je lis bien).

Piteux_gore:
Quand on veut enc... des mouches, on peut se permettre ça. X:-(

Salut,
J'avoue que je rejoins un peu Fin de partie. Je ne sais pas ce que sont les polynômes sous-résultants, c'est probablement utile dans un autre cadre, mais ici, si j'ai bien pigé, on cherche le PGCD de deux polynômes avant d'en extraire des racines. On sait que l'anneau $K[X]$ ($K$ un corps commutatif), n'est pas seulement principal, il est euclidien. De là, on n'a pas de mal à trouver une méthode algorithmique pour trouver le PGCD de quelques polynômes sans s'embêter à écrire des déterminants (zut! Pourquoi rajouter une couche?).

$\def\F{\mathbb F}\def\Res{\text{Res}}$@TitiLeCurieux
Je prends 5 minutes pour te répondre. L'algorithme d'Euclide dans $K[X]$ ($K$ corps) et le pgcd, c'est certes utile mais cela ne permet absolument pas de répondre à certaines questions, cf la tentative d'exemples ci-dessous.

Je vais parler du résultant. Tout ceci date des anciens, en particulier de Sylvester. Mais la lecture du fil donne l'impression que certains ignorent ce qu'est le résultant et ce à quoi il sert. Un des points importants est l'aspect polynomial du résultant : le résultant de deux polynômes à une indéterminée est un polynôme en les coefficients des deux polynômes de départ et permet la spécialisation (sous certaines hypothèses, je ne rentre pas dans les détails). Rien de tel avec le pgcd.

$\bullet$ 1. A quelles conditions portant sur $a,p,q$ les polynômes $T^2 + aT + 1$ et $T^3 + pT + q$ ont-ils une racine commune ? Je ne précise pas pour l'instant où vivent $a,p,q$. Et quand je dis racine commune, cela signifie dans une certaine extension du corps des coefficients. Si on prend pour $a,p,q$ des indéterminées, le pgcd de ces deux polynômes est 1. Difficile d'en tirer quelque chose. Par contre, le résultant apporte la solution.

[color=#000000]> Z := IntegerRing() ;
> Z3<a,p,q> := PolynomialRing(Z,3) ;
> Z3T<T> := PolynomialRing(Z3) ;
> F := T^2 + a*T + 1 ;
> G := T^3 + p*T + q ;
> S := SylvesterMatrix(F,G) ;
> S ;
[1 a 1 0 0]
[0 1 a 1 0]
[0 0 1 a 1]
[1 0 p q 0]
[0 1 0 p q]
> Determinant(S) ;
-a^3*q + a^2*p - a*p*q + 3*a*q + p^2 - 2*p + q^2 + 1
> Resultant(F,G) ;
-a^3*q + a^2*p - a*p*q + 3*a*q + p^2 - 2*p + q^2 + 1
> Gcd(F,G) ;
1
[/color]

La théorie élémentaire du résultant dit que les deux polynômes ont une racine commune (dans une extension ....etc..) si et seulement $-a^3q + a^2p - apq + 3aq + p^2 - 2p + q^2 + 1 = 0$.

$\bullet$ 2. Je considère les deux polynômes $X^n + b$ et $(X+1)^n + b$ avec $b \in \Z$. Sauf cas exceptionnels, ils sont premiers entre eux dans $\Z[X]$ donc dans $\Q[X]$ et donc à vie sur toute extension de $\Q$. Le pgcd (l'algorithme d'Euclide si on travaille au dessus d'un corps) permet de le vérifier.

Mais si on se pose la question : quels sont les premiers $p$ tels que $X^n + b$ et $(X+1)^n + b$ sont premiers modulo $p$, le pgcd n'apporte aucune réponse. Mais le résultant, si. Les premiers $p$ pour lesquels ils ne restent pas premiers entre eux sont les diviseurs du résultant.

[color=#000000]> ZX<X> := PolynomialRing(Z) ;
> n := 5 ; b := 3 ;
> P := X^n + b ;
> Q := (X+1)^n + b ;
> Gcd(P,Q) ;
1
> 
> r := Resultant(P,Q) ;
> r ;
258751
> Factorization(r) ;
[ <41, 1>, <6311, 1> ]
> Pmod41<T> := ChangeRing(P, GF(41)) ;
> Qmod41<T> := ChangeRing(Q, GF(41)) ;
> Gcd(Pmod41, Qmod41) ;
T + 12
[/color]

Exercice : pour $b = -1$ et $n \equiv 0 \bmod 6$, les polynômes $X^n - 1$ et $(X+1)^n - 1$ ne sont pas premiers entre eux car divisibles par $X^2 + X + 1$ (ou encore $j$, de $j^3 = 1$, est une racine commune).
Est ce le seul cas pour lesquels ils ne sont pas premiers entre eux (rappels : $n$ est entier et $b \in \Z$).

$\bullet$ 3. Là je fais joujou en prenant $n = 17$ et $b = 9$. Même topo, les deux polynômes $X^{17} + 9$ et $(X+1)^{17} + 9$ sont premiers entre eux dans $\Z[X]$. Mais que donne le résultant ?

[color=#000000]> n := 17 ; b := 9 ;
> P := X^n + b ;
> Q := (X+1)^n + b ;
> Gcd(P,Q) ;
1
> 
> p, U, V := Res(P,Q) ;
> p ;
8936582237915716659950962253358945635793453256935559
> p eq U*P + V*Q ;
true
> IsPrime(p) ;
true
[/color]

La théorie élémentaire du résultant dit que le résultant de $P,Q$ s'écrit de manière explicite sous la forme $\Res(P,Q) = UP + VQ$ avec $U,V$ dans l'anneau des coefficients de $P,Q$. Et d'ailleurs, $U,V$ sont extraits de la matrice de Sylvester de $P,Q$. C'est le B.A.BA.

Il se trouve qu'ici le résultant est un nombre premier et c'est pour cela que je l'ai noté $p$.

Que va-on faire avec cela ? On va évaluer $p = UP + VQ$ en n'importe quel entier $m$ : $p = U(m)P(m) + V(m)Q(m)$. Ceci prouve que le pgcd des deux entiers $P(m)$ et $Q(m)$ est un diviseur de $p$ donc, à $\pm 1$ près, que c'est $1$ ou $p$.

Allons un peu plus loin.

[color=#000000]> Pmodp<T> := ChangeRing(P, GF(p)) ;
> Qmodp<T> := ChangeRing(Q, GF(p)) ;
> D := Gcd(Pmodp, Qmodp) ;
> D ;
T + 512149312322827330662764931050044963334032796143126
> N := Z! -Coefficient(D,0) ;
> N ;
8424432925592889329288197322308900672459420460792433
> 
> Gcd(Evaluate(P,N), Evaluate(Q,N)) ;
8936582237915716659950962253358945635793453256935559
> 
> m := Random(1,10^10) ;
> Gcd(Evaluate(P,m), Evaluate(Q,m)) ;
1
[/color]

Bilan avec $p, N$ ci-dessus
$$
\gcd\big( m^{17} + 9, (m+1)^{17} + 9\big) = \cases {
p & si $m \equiv p \bmod N$ i.e. pas souvent \cr
1 & sinon \cr
}
$$En particulier, le pgcd est 1 pour $0 \le m < N$ mais vaut $p$ pour $m = N$.

Claude a parlé du résultant et l'a comparé au PGCD. On peut poursuivre l'analogie avec d'un côté les polynômes sous-résultants (dont le résultant) et de l'autre côté les restes successifs dans l'algorithme d'Euclide qui calcule le pgcd.

Reprenons l'exemple du texte de Dostor avec le polynôme de degré 3 $ax^3+bx^2+cx+d$ et le polynôme de degré 2 $a'x^2+b'x+c'$. Le résultant de ces deux polynômes est le déterminant de la matrice de Sylvester
$$\begin{pmatrix} a&b&c&d&0\\ 0&a&b&c&d\\ 0&0&a'&b'&c'\\ 0&a'&b'&c'&0\\ a'&b'&c'&0&0 \end{pmatrix}\;.$$
Le sous-résultant de degré 1 s'obtient en prenant le déterminant de la matrice obtenue en effaçant la ligne du haut, la ligne du bas, la colonne de gauche et en écrasant les deux dernières colonnes en une. C'est :
$$\begin{vmatrix} a&b&cx+d\\ 0&a'&b'x+c'\\ a'&b'&c'x \end{vmatrix}\;.$$
Ça ressemble à ce que fait Dostor, mais ce que fait Dostor souffre toujours du même défaut : ça coince visiblement quand 0 est la racine commune des deux polynômes.
Si les deux polynômes sont $(x-\alpha)(x-\beta)(x-\gamma)$ et $(x-\alpha)(x-\delta)$, vous pouvez vérifier que le polynôme sous-résultant de degré 1 est
$$ (\delta-\beta)(\delta-\gamma)(\alpha-x)\;.$$

$\def\Res{\text{Res}}$@Titi le curieux
Peux tu me détailler i.e. le faire VRAIMENT ton ``on peut faire un algorithme assez simple qui résoudra le problème du pgcd "avec coefficients inconnus" très systématiquement'' ?Juste dans le cas de $F = T^2 + aT + 1$ et $G = T^3 + pT + q$.

Cela a comme implication la chose suivante. Si la quantité $r = \Res(F,G)$ ci-dessous est non nulle, alors le pgcd est 1. Si $r = 0$, en supposant DE PLUS $q^2 + p-1 \ne 0$, le pgcd est $h$, de degré 1 en $T$, que j'ai fait figurer également

[color=#000000]> r ;
-a^3*q + a^2*p - a*p*q + 3*a*q + p^2 - 2*p + q^2 + 1
> 
> h ;
T - q/(q^2 + p - 1)*a^2 + (q^2 + p)/(q^2 + p - 1)*a + (-p*q + 2*q)/(q^2 + p - 1)
[/color]

Précision (déjà dit mais ...) : dans la branche $r = 0$, je me suis limité à $q^2 + p-1 \ne 0$.

Bonjour,

Il me semble que la plupart des exposés sur le résultant signalent que celui-ci est le produit des évaluations d'un des polynômes aux racines de l'autre, multiplié par une constante adéquate. Voir par exemple le théorème 5 dans ce document. Après, savoir si ça donne une méthode commode de calcul du résultant, c'est une autre paire de manches ...

Il est bien évident que ça fournit une condition nécessaire et suffisante pour que les deux polynômes aient une racine commune. mais si tu avais lu avec attention, tu aurais vu que le problème n'est pas là : la discussion porte sur une méthode de calcul du résultant.

Par ailleurs, que veux-tu dire par "On peut même faire plus efficace en 'déterminant' la (ou les) racine(s) en question. " ?