Séance de cours

Algorithme euclidien

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre l'algorithme euclidien des polynômes sur un champ K. Elle explique comment calculer le plus grand diviseur commun (GCD) de deux polynômes en utilisant la division avec la méthode restante. L'algorithme implique la recherche itérative des restes jusqu'à atteindre un solde zéro, en déterminant le GCD. Des exemples sont fournis pour illustrer l'application de l'algorithme, y compris l'utilisation de l'identité de Bézout et du lemma de Gauss.

Source officielle

Proximité ontologique

Mathématiques

Algèbre: Algèbre générale

Concepts associés (32)

Polynomial greatest common divisor

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers. In the important case of univariate polynomials over a field the polynomial GCD may be computed, like for the integer GCD, by the Euclidean algorithm using long division. The polynomial GCD is defined only up to the multiplication by an invertible constant.

Théorème de Bachet-Bézout

En mathématiques, et plus précisément en arithmétique élémentaire, le théorème de Bachet-Bézout ou identité de Bézout est un résultat d'arithmétique élémentaire, qui prouve l'existence de solutions à l'équation diophantienne linéaire : ax + by = pgcd(a, b) d'inconnues x et y entiers relatifs, où a et b sont des coefficients entiers relatifs et où pgcd(a, b) est le plus grand commun diviseur de a et b. Le théorème de Bézout affirme que les entiers a et b sont premiers entre eux si et seulement si l'équation ax + by = 1 admet des solutions.

Anneau euclidien

vignette|Statue d'Euclide à Oxford. En mathématiques et plus précisément en algèbre, dans le cadre de la théorie des anneaux, un anneau euclidien est un type particulier d'anneau commutatif intègre (voir aussi l'article anneau euclidien non commutatif). Un anneau est dit euclidien s'il est possible d'y définir une division euclidienne. Un anneau euclidien est toujours principal. Cette propriété est riche de conséquences : tout anneau principal vérifie l'identité de Bézout, le lemme d'Euclide, il est factoriel et satisfait les conditions du théorème fondamental de l'arithmétique.

Plus grand commun diviseur

En arithmétique élémentaire, le plus grand commun diviseur ou PGCD de deux nombres entiers non nuls est le plus grand entier qui les divise simultanément. Par exemple, le PGCD de 20 et de 30 est 10, puisque leurs diviseurs communs sont 1, 2, 5 et 10. Cette notion s'étend aux entiers relatifs grâce aux propriétés de la division euclidienne. Elle se généralise aussi aux anneaux euclidiens comme l'anneau des polynômes sur un corps commutatif. La notion de PGCD peut être définie dans tout anneau commutatif.

Algorithme d'Euclide étendu

En mathématiques, l'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide. À partir de deux entiers a et b, il calcule non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout, c'est-à-dire deux entiers u et v tels que au + bv = PGCD(a, b). Quand a et b sont premiers entre eux, u est alors l'inverse pour la multiplication de a modulo b (et v est de la même façon l'inverse modulaire de b, modulo a), ce qui est un cas particulièrement utile.

Afficher plus

Séances de cours associées (50)

Méthodes polynomiales: Résumé du calcul GCD

Couvre le calcul du plus grand commun diviseur en utilisant des méthodes polynomiales et l'algorithme euclidien.

Factorisation polynomiale sur les champs Finite

Introduit la factorisation polynôme sur les champs finis et le calcul efficace des plus grands diviseurs communs des polynômes.

Idéal : Polynômes et définitions

Explore les idéaux en K[X], y compris le PGCD, l'unicité, la coprimalité, et les théorèmes de Bézout et Gauss.

Théorie des nombres: Division, Reste, Congruence

Couvre la théorie des nombres, la division, le reste, la congruence, les nombres premiers, la représentation entière et l'algorithme euclidien.

Polynômes : Racines et factorisation

Explore en profondeur les racines polynômes, la factorisation et l'algorithme euclidien.

Afficher plus

Concepts associés (32)

Polynomial greatest common divisor

Théorème de Bachet-Bézout

Anneau euclidien

Plus grand commun diviseur

Algorithme d'Euclide étendu

Afficher plus