Division euclidienne

restitution organisée de connaissances. Dans le premier paragraphe de ce chapitre, on introduit la notion de diviseur et de multiple ainsi que les propriétés liées à ces notions. Dans le deuxième paragraphe, on définit la division euclidienne dans ‫ ,ގ‬puis la division euclidienne dans ‫ ,ޚ‬en se limitant, conformément au programme, au cas d’un diviseur positif. Dans le troisième paragraphe, on aborde les congruences en développant les démonstrations. Corrigés des activités préparatoires ACTIVITÉ

  12  –  12  =  0   Nicolas  Rayez   1   Méthode  3  :  L’algorithme  d’Euclide     1. On  effectue  la  division  euclidienne  du  plus  grand  nombre  par  le  plus  petit   2. Puis  on  refait  une  division  euclidienne  avec  le  diviseur  et  le  reste  jusqu’à  obtenir   un  reste  nul   3. Le  PGCD  est  le  dernier  reste  non

PGDC est toujours supérieur ou égal à 1. Pour calculer le PGDC ont peut utiliser la division euclidienne : On effectue la division euclidienne de a par b et on note r le reste. Ensuite, b devient a et r devient b comme sur le tableau ci-dessous et on recommence. On continue ainsi de suite jusqu'à ce qu'une division donne un reste égal à 0. Dans cette méthode le PGCD est le dernier entier b quand la division obtient un reste nul. Ex :

n−1 de P(X − a nn−1 ) est nul. 4 2. Arithmétique des polynômes Il existe de grandes similarités entre l’arithmétique dans Z et l’arithmétique dans K[X ]. Cela nous permet d’aller assez vite et d’omettre certaines preuves. 2.1. Division euclidienne Définition 3 Soient A, B ∈ K[X ], on dit que B divise A s’il existe Q ∈ K[X ] tel que A = BQ. On note alors B| A. On dit aussi que A est multiple de B ou que A est divisible par B. Outre les propriétés évidentes comme A | A, 1| A et A

programmation : Python Ecrire un programme permettant de vérifier si un nombre donné est divisible par 13 en effectuant un test dans une instruction conditionnelle sur le reste de la division de ce nombre par 13. Voici la syntaxe permettant d'afficher le reste d'une division euclidienne : Langage naturel Reste de la division euclidienne de A par B Python Scilab TI CASIO A%B reste(A,B) A–B*ent(A/B) A–BxInt (A÷B) Commentaires : "==" est le symbole d'égalité ; "=" celui d'affectation. Yvan  Monka

Caractères de divisibilité ? Diviseur, multiple : Définition : Si le reste de la division euclidienne d’ entier a par un entier b est nul, on dit que : un ? a est divisible par b ou : ? a est un multiple de b ou : ? b est un diviseur de a Exemple : 65 13 0 5 Le reste de la division euclidienne de 65 par 13 est zéro, donc : ? 65 est un multiple de 13 ? 65 est un divisible par 13 ? 13 est un diviseur de 65 ? Caractères de divisibilité usuels : 1) Un nombre entier est divisible par

variante du petit théorème de Fermat. 1. Division euclidienne et pgcd 1.1. Divisibilité et division euclidienne Définition 1 Soient a, b ∈ Z. On dit que b divise a et on note b|a s’il existe q ∈ Z tel que a = bq . Exemple 1 – – – – – – 7|21 ; 6|48 ; a est pair si et seulement si 2|a. Pour tout a ∈ Z on a a|0 et aussi 1|a. Si a|1 alors a = +1 ou a = −1. (a| b et b|a) =⇒ b = ±a. (a| b et b| c) =⇒ a| c. (a| b et a| c) =⇒ a| b + c. 1 2 Théorème 1. Division euclidienne Soit a ∈ Z et b ∈ N \ {0}. Il existe

entiers naturels non nuls (a>b) Un diviseur commun à a et b est un diviseur : -de leur somme, -de leur différence -du reste de la division euclidienne de a par b. Exemple : 5 est un diviseur de 40 et de 15 donc 5 est un diviseur de 55 (la somme de 40 et 15) donc 5 est un diviseur de 25 (la différence de 40 et 15) donc 5 est un diviseur de 10 (reste de la division euclidienne de 40 par 15) 2.3 Algorithme d’euclide Enoncé1 : On veut connaitre le plus grand diviseur commun à 3162 et 1884 en utilisant l’algorithme

.....................................................54 A. A propos de la parité de deux entiers consécutifs. ........................... 54 B. D’autres exercices à propos de la parité .......................................... 56 4. Division euclidienne ...................................................................................... 57 5. Divisibilité - Approche du théorème de Gauss.............................................. 58 6. Apprendre à reconnaître une situation arithmétique

devoirs professionnels du médecin - Les mathématiques avec Euclide, on lui doit -"postulat d'Euclide : par un point pris hors d'une droite il passe une et une seule parallèle à cette droite selon la géométrie euclidienne. On lui doit également la division que l'on appelle division euclidienne, un algorithme pour calculer le plus grand commun diviseur de deux nombres. - La physique avec Archimède à qui l'on doit -l'étude du cercle où il détermine une méthode d'approximation de π, l'étude des aires