Division euclidienne

car- B - Division euclidienne Exercice 1716 1. Déterminer la division euclidienne de 1038 par 17. 2. En étudiant le carré (61×17 + 1)2 , déterminer le reste de la division euclidienne de 10382 par 17. 3. En déduire une conjecture sur, pour tout entier naturel n, la division euclidienne de 1038n par 17. C - Congruence Exercice 27 1. a. Trouver les plus petits entiers naturels a, b, c vérifiant : 100 ≡ a (mod. 4) ; 27 ≡ b (mod. 4) 2. 95 ≡ c (mod. 4) b. En déduire le reste de la division euclidienne

Conclusion : n = 55 ou n = 37 ou n = 73. a) En écrivant la division euclidienne de 45 par le nombre entier naturel y, 45 = y ¥ q + r avec 0 ഛ r Ͻ y. La condition « quotient égal au reste » se traduit par : 45 = y ¥ x + x et 0 ഛ x Ͻ y, donc 45 = ( y + 1) x et 0 ഛ x Ͻ y. b) Les diviseurs positifs de 45 sont 1, 3, 5, 9, 15 et 45. On envisage tous les cas. • Si x = 1, alors y + 1 = 45, soit x = 1 et y = 44. Dans la division euclidienne de 45 par 44, le quotient est égal au reste et vaut 1. •

et de 5. b. La réciproque semble-t-elle vraie ? 5 Liste a. Trouve tous les nombres divisibles par 7 compris entre 220 et 260. b. Parmi ces nombres, quels sont ceux qui sont divisibles par 4 ? Division euclidienne 13 Posée, en ligne a. Donne le quotient et le reste de la division euclidienne de : • 63 par 4 ; • 218 par 12 ; • 3 245 par 135 ; • 32 par 50. 6 Énigme Trouve tous les nombres de trois chiffres divisibles à la fois par 3 et par 5 et dont le chiffre des centaines est 7. 7

est égal à 3 (ou à un multiple) Alors il est divisible par 3 (ou à un multiple) Division euclidienne a et b désignent deux nombres entiers positifs avec b = 0 Effectuer la division euclidienne de a par b signifie déterminer deux nombres entiers positifs q et r qui vérifient a = b X q + r a b q q s’appelle le quotient de la division euclidienne r s’appelle le reste de la division euclidienne r Diviseurs et multiples a et b désignent deux nombres entiers positifs, avec

12/8 et 8/12 ne sont pas irréductibles. Algorithme d'Euclide : méthode 1) On effectue la division euclidienne du plus grand des deux nombres par le plus petit. 2) On effectue la division euclidienne du diviseur par le reste de la division précédente, jusqu’à ce que le reste de la division soit égal à zéro. 3) Le PGCD est le dernier reste non nul dans la succession des divisions euclidiennes. Diviseurs et multiples Définitions : Pour deux nombres entiers n et d non nuls, d est un

th´or`me. e e e Remarque 1. Voir TP 6, Section 3 (novembre 2009) du cours if1. 1.1.1 En langage courant Remarque 2. Pour calculer le pgcd de deux entiers strictement positifs a et b, on suppose toujours a ≥ b > 0. On effectue la division euclidienne de a par b, c’est-`-dire la d´termination de deux entiers a e positifs q (le quotient) et r (le reste) qui satisfont 0 ≤ r < b et a = b × q + r (ces deux entiers sont bien d´termin´s de mani`re unique). On a e e e q = a/b r = a mod b . – Si

La division décimale de deux entiers au CM1 Introduction : On parle de division décimale quand au moins un des quatre nombre de la division (a, b, q ou r) est décimal. La division peut alors être exacte ou approchée. L’introduction en CM1 de la division décimale de deux entiers est une nouveauté des programmes de 2008. Certains manuels ne sont, en conséquence, pas encore à jour. En outre, cette séquence est prévue comme une initiation, puisque ce point sera revu en 6e. Il ne s’agit donc

-2, -1, 1, 2, 3, 4, 6, 12} 2 Division euclidienne Théorème Soient a un entier relatif et b un entier relatif non nul, il existe un unique couple (q, r) d'entiers vérifiant : a = b⋅q + r et 0 ≤ r < |b| Définition L'opération qui à (a, b) associe (q, r) est la division euclidienne de a par b. • q est le quotient • r est le reste Remarques a) Le reste r est toujours positif et < |b|. b) 18 = 3⋅2 + 12 ne veut pas dire que 12 est le reste de la division euclidienne de 18 par 3 ! 1 Arithmétique

pour tous réels a et b de [0;1] avec : * Loi exponentielle de paramètre ( >0), une loi de densité f telle que Suivant la loi exponentielle: Arithmétique Division euclidienne dans ℤ Soit un entier relatif et un entier relatif non nul. Il existe un unique entier relatif et un unique entier naturel tels que: . C'est la division euclidienne de par où est le quotient et le reste. ( est la partie entière du réel .) Congruences Soit et deux entiers relatifs et signifie que divise par . PGCD: produit

d’un nombre entier relatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Propriétés élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Définition. . . . . . . . . . . . . . . . . . . . . . . . . .