Congruence sur les entiers

Term L spé La congruence Exercice 26 1. Dîtes si les nombres suivants sont des cubes d’entier naturel : a. 9 b. 27 c. 33 ×73 2. d. 119 ×196 ×673 e. 22 ×53 ×11 reaux non découpé qui auront été posés. 2. Le sol de la cuisine est un rectangle de longueur 4,55 m et de largeur 3,85 m. On veut carreler cette pièce avec un nombre entier de dalles carrées, sans aucune découpe. a. Donner la liste des diviseurs de 455 puis la liste des diviseurs de 385. b. Donner la liste des diviseurs communs à 455 et

Exercices sur les congruences Exercice 1 Déterminer les congruences suivantes : 1) Modulo 5 des nombres suivants : 12 ; 45 ; 87 ; 12 ; 104 2) Modulo 7 des nombres suivants : 14 ; 85 ; 24 ; 46 3) Modulo 8 des nombres suivants : 12 ; 204 ; 36 ; 48 Exercice 2 Compléter la table de congruence suivante modulo 5 N 0 1 2 3 4 2N² Compléter la table de congruence suivante modulo 7 N 0 1 2 3 4 5 6 3N – 5 Compléter la table de congruence suivante modulo 4 N 0 1 2 3 N² - 2N + 3

+, est une loi de composition interne sur Z. L'ensemble des entiers naturels N est une partie de Z, stable pour l'addition. 2) Soit E un ensemble non vide et soit F(E) = {f | f : E → E application}. La composition des applications, notée o, est une loi de composition interne sur F(E). Si on note par S(E) = {f ∈ F (E) | f bijective} alors S(E) est une partie de F(E), stable pour la loi o. 3) Soit n ∈ N∗ et soit ≡ la relation de congruence modulo n dénie sur Z par : x ≡ y mod (n) ⇔ x − y est divisible

Chapitre 1. Divisibilité et congruences Corrigés des « Pour se tester » 33. Questions sur le cours a) b divise a signifie qu’il existe un entier k tel que a  bk . b) Si a divise b et si b divise c, alors a divise c. c) Si d divise a et b, alors pour tous entiers relatifs m et n, ma  nb est divisible par d (ou ma  nb est un multiple de d). d) La division euclidienne de a par b se traduit par a  bq  r où q et r sont des entiers naturels tels que 0  r  b . e) a  b (mod m) signifie

deux visions de la conjecture de Goldbach, une vision alg´brique et e e une vision g´om´trique, toutes deux bas´es sur l’´tude des restes modulaires e e e e des entiers selon des modules premiers. Les d´composants de Goldbach d’un e entier pair 2a sont les nombres premiers inf´rieurs ou ´gaux ` a solutions de e e a syst`mes de congruence g´n´ralis´s d´coulant de cette repr´sentation. Enfin, sera e e e e e e pr´sent´e une conjecture portant sur le partage des d´composants de Goldbach e e e et qui donne

coefficients entiers a Soient a, b, c trois entiers relatifs. On consid`re l’´quation : ax + by = c, dont on recherche les solutions dans Z2 . e e 1) Donner une condition n´c´ssaire et suffisante pour que cette ´quation admette une solution. e e e 2) Soit (x0 , y0 ) une solution du probl`me de B´zout : ax0 + by0 = d. D´terminer toutes les solutions de ax + by = c e e e en fonction de a, b, c, d, x0 et y0 . 3) R´soudre dans Z2 : 2520x − 3960y = 6480. e ´ Exercice 2. Equations ` coefficients entiers a R´soudre

1 . Soient a et b deux entiers > 0. (a) Montrer que si a et b sont premiers entre eux, il existe un unique couple d’entiers > 0 (u, v) tel que au − bv = 1 v´rifiant u < b et v < a. e (b) Montrer que a et b sont non premiers entre eux si et seulement s’il existe deux entiers > 0 u et v tels que au = bv, avec u < b et v < a. e e 2 . : Le th´or`me chinois : (a) D´terminer tous les entiers relatifs qui deviennent divisibles par 5 si on leur ˆte 1, et divisible par e o 4 si on leur ajoute 1. (b) Soit a

l’ensemble des entiers relatifs II - Division euclidienne III - Congruence modulo n (n entier au moins égal à 2) IV - PGCD de deux entiers relatifs non nuls V - Algorithme d’Euclide VI - Théorème de Bézout VII - Théorème de Gauss VIII - PPCM de deux entiers relatifs non nuls IX - Propriétés du PGCD et du PPCM X - Nombres premiers XI - Décomposition d’un entier naturel n en facteurs premiers I - Divisibilité dans l’ensemble des entiers relatifs Définition Soit a et b des entiers relatifs. Lorsqu’il

Mourougane sur la base d’un texte ant´rieur d’Antoine Chambert-Loir. e e e Que ces deux auteurs soient ici remerci´s. e 25 septembre 2009 ` ´ ALGEBRE ET ARITHMETIQUE 1 ` TABLE DES MATIERES Partie I. Logique, th´orie des ensembles, nombres entiers naturels. . . . . . . . . . . . . . e 1. Logique et th´orie des ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 1.1. Un peu de logique. . . . . . . . . . . . . . . . . . . . . . . .

d'arithmétique 1 Multiple et diviseur d'un nombre Définition Soient a et b deux entiers relatifs. S'il existe un entier relatif k tel que : a = k⋅b - On dit que a est un multiple de b ou que b est un diviseur de a. - On dit encore que a est divisible par b ou que b divise a. Théorème Soient a, b et c des entiers relatifs quelconques. Si a divise b et c, alors a divise toute combinaison linéaire de b et c: u⋅b+v⋅c, où u et v sont des entiers relatifs. En particulier, a divise b+c et b-c. Remarque Dans 9 l'ensemble