Division euclidienne

surprise ` C´dric (par exemple, le a a e 10), message qui ne doit pas ˆtre intercept´ par ledit C´dric, bien sˆr. e e e u 7 = 187 × 53475 + 175, et envoyer le r´sultat 175 Bernard va donc calculer 10 e a ` Alice. Alice va calculer le reste de la division euclidienne de 17523 par 187 : – Elle calcule d’abord 1752 = 30625 = 163×187+144, donc 1752 ≡ 144[187]. – Ensuite, 1442 = 20736 = 110 × 187 + 166, donc 1754 ≡ 166[187]. – Puis, 1662 = 27556 = 147 × 187 + 67 donc 1758 ≡ 67[187]. – Et 672 = 4489 = 24 × 187

(P1 , P2 , P3 ) est une base de K2 [X]. Exercice 22 [ 02146 ] Exercice 15 Soit A, B, C ∈ K [X] tels que A et B soient premiers entre eux. Montrer : pgcd(A, BC) = pgcd(A, C). [ 02139 ] Exercice 23 Division euclidienne Exercice 16 En réalisant une division euclidienne, former une condition nécessaire et susante sur (λ, µ) ∈ K 2 pour que X 2 + 2 divise X 4 + X 3 + λX 2 + µX + 2. [ 02140 ] Pour k ∈ {0, . . . , n}, on pose Pk = (X + 1)k+1 − X k+1 . Montrer que la famille (P0

par une représentation en perspective centrale du quadrillage des faces ABFE et BCGF. E XERCICE 3 1. a. Déterminer le reste de la division euclidienne de 23 par 7. b. 23 et 26 sont-ils congrus modulo 7 ? Justifier la réponse. 6 points c. Démontrer que, pour tout entier naturel n, 23n ≡ 1 (modulo 7). Que peuton en déduire pour le reste de la division euclidienne de 22 007 par 7 ? 2. On considère l’algorithme suivant : Entrée : n est un entier naturel. Initialisation : Donner à u la valeur initiale

nulles. Exercice II (5 points). Candidats ayant suivi l’enseignement de spécialité Les trois questions peuvent être traitées de façon indépendante. 1. a. Quel est le reste de la division euclidienne de 610 par 11 ? Justifier. b. Quel est le reste de la division euclidienne de 64 par 5 ? Justifier. c. En déduire que 640 ≡ 1[11] et que 640 ≡ 1[5]. d. Démontrer que 640 −1 est divisible par 55. 2. Dans cette question x et y désignent des entiers relatifs.

récurrence 4) Equations, inéquations, systèmes d’équations linéaires 5) Etude de fonctions 6) Intégration 7) Applications et bijections. Bijection réciproque 8) Logarithme et exponentielle 9) Suites numériques 10) Notions de combinatoire 11) Division euclidienne, pgcd et algorithme d’Euclide Mathématiques et informatique La caractéristique de ce cours est de lier l’informatique et les mathématiques. Dans chaque chapitre, des programmes informatiques sont donnés, qu’il conviendra de tester

[correction] Résoudre dans Z2 les équations suivantes : 1 1 a) xy = 3x + 2y b) x + y = 1 c) x2 − y 2 − 4x − 2y = 5. 5 Exercice 3 [ 01189 ] [correction] Soient a ∈ Z et b ∈ N , on note q le quotient de la division euclidienne de a − 1 par b. Déterminer pour tout n ∈ N, le quotient de la division euclidienne de (abn − 1) par bn+1 . PGCD et PPCM Exercice 9 [ 01195 ] [correction] Déterminer le pgcd et les coefficients de l’égalité de Bézout (1730-1783) des entiers a et b suivants : a) a = 33 et b = 24 b)

ouvrage de l’histoire des mathématiques, les Éléments. Euclide se distingue également en théorie des nombres, démontrant notamment que l’ensemble des nombres premiers est infini. Il est aussi le premier à pratiquer la division avec le reste, appelée aujourd’hui division euclidienne.

= (X + 1)(X 3 + X + 1)(X 3 + X 2 + 1) = 1 + X + X 2 + X 3 + X 4 + X 5 + X 6 , qui donne un code de param`tres (1, 7). On reconnaˆ le code de r´p´tition pure. e ıt e e Et c’est tout ! Exercice 2 Posons g(X) = X 3 + X + 1, on effectue les divisions euclidiennes : 1 + X + X 5 + X 6 = (X + X 2 + X 3 )g(X) + 1. Le reste est non nul, ce mot contient des erreurs. X + X 3 + X 4 + X 5 = (X + X 2 )g(X). Le reste est nul, ce mot ne contient pas d’erreur. 1 + X + X 2 + X 5 = (1 + X 2 )g(X). Le reste est nul

par 0 est égale à 0. VLa division ALa division euclidienne Dans la division de a par b, le nombre a est le dividende , le nombre b est le diviseur. Le résultat est le quotient, et peut être accompagné d'un reste : dividende=diviseur×quotient+resteOn écrit aussi : a=b×q+rEt on pose : dividende diviseur reste quotient Le reste doit toujours être inférieur au diviseur. La division par 0 est impossible. 46=3×15+132=4×8+0 BLes multiples et les diviseurs Si le reste de la division de a par b est nul

Algèbre des polynômes . . . . . . . . . . . . . . . . 1.1.1 Définition . . . . . . . . . . . . . . . . . . . 1.1.2 Opérations sur K[X] . . . . . . . . . . . . . 1.2 Division des polynômes . . . . . . . . . . . . . . . . 1.2.1 Divisions suivant les puissances décroissantes 1.2.2 Algorithme d’Euclide, PGCD . . . . . . . . 1.2.3 Divisions suivant les puissances croissantes . 1.3 Racines d’un polynôme . . . . . . . . . . . . . . . . 1.4 Factorisation . . . . . . . . . . . . . . . . . . . . . 1.4.1