c ⃝Christophe Bertault - MPSI Arithmétique des entiers relatifs 1 Division dans

c ⃝Christophe Bertault - MPSI Arithmétique des entiers relatifs 1 Division dans Z 1.1 Relation de divisibilité Définition (Divisibilité, diviseur, multiple) Soient a, b ∈Z. On dit que a divise b, ou que a est un diviseur de b, ou que b est divisible par a, ou que b est un multiple de a, s’il existe k ∈Z tel que b = ak. Cette relation se note a|b. Théorème (Propriétés de la relation de divisibilité) Soient a, b, c, d ∈Z. (i) La relation de divisibilité | sur Z est réflexive et transitive. Elle n’est cependant pas antisymétrique puisque : a|b et b|a ⇐ ⇒ |a| = |b| ⇐ ⇒ a = b ou a = −b. En revanche, sa restriction à N l’est : c’est une relation d’ordre. (ii) Combinaisons linéaires : Si d|a et si d|b, alors d|(au + bv) pour tous u, v ∈Z. (iii) Produit : Si a|b et si c|d, alors ac|bd. En particulier, si a|b, alors ak|bk pour tout k ∈N. (iv) Multiplication/division par un entier : Si d ̸= 0 : a|b ⇐ ⇒ ad|bd. Démonstration (i) La réflexivité et la transitivité de | ont été démontrées dans le chapitre sur les relations d’ordre. Contentons- nous de montrer l’équivalence relative au défaut d’antisymétrie de |. L’une des deux implications est triviale : si |a| = |b|, i.e. a = b ou a = −b, il est clair que a|b et que b|a. Réciproquement, faisons l’hypothèse que a|b et b|a. Alors il existe k, l ∈Z tels que b = ak et a = bl. Du coup b = bkl. Deux cas se présentent alors : si b = 0, alors a = bl = 0 et on a donc bien |a| = |b| ; si au contraire b ̸= 0, alors kl = 1 et donc, puisque k et l sont entiers, on a soit k = l = 1, soit k = l = −1, i.e. a = b ou a = −b, i.e. |a| = |b| comme voulu. (ii) Faisons l’hypothèse que d|a et d|b. Il existe donc k, l ∈Z tels que a = dk et b = dl. Alors au+bv = d(ku+vl) avec ku + vl ∈Z pour tous u, v ∈Z, et donc d (au + bv) comme annoncé. (iv) Supposons d ̸= 0. Si a|b, alors comme par ailleurs d|d, l’assertion (iii) affirme que ad|bd. Réciproquement, supposons que ad|bd. Il existe alors k ∈Z tel que bd = kad, et donc tel que b = ak. Ceci montre bien que a|b. ■ 1.2 Relation de congruence Définition (Congruence modulo un entier) Soient n ∈N et a, b ∈Z. On dit que a est congru à b modulo n si n (b −a), i.e. s’il existe k ∈Z tel que b = a + kn. Cette relation se note a ≡b mod n.    Explication La relation de congruence est une généralisation de la relation de divisibilité. Il faut à tout prix avoir en tête le cas particulier suivant : n|a ⇐ ⇒ a ≡0 mod n. Théorème (Propriétés de la relation de congruence) Soient a, a′, b, b′ ∈Z et m, n ∈N. (i) Relation d’équivalence : La relation · ≡· mod n est réflexive, symétrique et transitive. (ii) Somme : Si a ≡b mod n et si a′ ≡b′ mod n, alors a + a′ ≡b + b′ mod n. (iii) Produit : Si a ≡b mod n et si a′ ≡b′ mod n, alors aa′ ≡bb′ mod n. En particulier, si a ≡b mod n, alors ak ≡bk mod n pour tout k ∈N. (iv) Multiplication/division par un entier : Si m ̸= 0 : a ≡b mod n ⇐ ⇒ am ≡bm mod mn. 1 c ⃝Christophe Bertault - MPSI Démonstration (i) La réflexivité et la symétrie de · ≡· mod n sont immédiates. Montrons seulement la transitivité. Trois entiers a, b, c ∈Z étant donnés, faisons l’hypothèse que a ≡b mod n et b ≡c mod n. Alors n (b −a) et n (c −b), donc par somme n (c −b) + (b −a)
, i.e. n (c −a), ou encore a ≡c mod n. (ii) Si a ≡b mod n et si a′ ≡b′ mod n, alors n (b −a) et n (b′ −a′), donc par somme n (b −a) + (b′ −a′)
, i.e. n (b + b′) −(a + a′)
, ou encore a + a′ ≡b + b′ mod n. (iii) On remarque que bb′ −aa′ = b(b′ −a′) + a′(b −a). Du coup, si a ≡b mod n et si a′ ≡b′ mod n, alors n (b−a) et n (b′ −a′), et donc par combinaison linéaire n b(b′ −a′)+ a′(b−a)
, i.e. n (bb′ −aa′), ou encore aa′ ≡bb′ mod n. (iv) Enfin : a ≡b mod n ⇐ ⇒ n (b −a) m̸=0 ⇐ ⇒ mn m(b −a) ⇐ ⇒ am ≡bm mod mn. ■ 1.3 Division euclidienne Théorème (Division euclidienne) Soient a ∈Z et b ∈N∗. Il existe un unique couple (q, r) ∈Z × N tel que : a = bq + r et 0 ⩽r ⩽b −1 (ce qu’on peut aussi écrire : 0 ⩽r < b). Dans cet énoncé, a est appelé le dividende, b le diviseur, q le quotient et r le reste. On a : q = ja b k et r ≡a mod b.    Explication • Le théorème de la division euclidienne est un résultat d’existence et d’unicité : voilà l’essentiel. • En termes de congruences, le théorème de la division euclidienne affirme simplement que tout entier relatif a est congru modulo b à un entier unique entier r compris entre 0 et b −1. Par exemple, on peut ramener l’entier a = 12839 à l’un des entiers 0, 1, 2, 3 ou 4 modulo b = 5. Précisément : 12839 | {z } a = 5 |{z} b × 2567 |{z} q + 4 |{z} r , et donc 12839 ≡4 mod 5. • L’idée de la démonstration est fort simple. Si a est positif, nous allons retrancher à a l’entier b une fois, deux fois, trois fois. . . jusqu’au moment où a aura presque complètement fondu, c’est-à-dire jusqu’au moment où le résultat sera compris entre 0 et b −1. Si a est négatif, l’idée est la même mais on ajoute b au lieu de le retrancher. Le principe est donc simple mais un problème se pose tout de même : comment garantir avec rigueur que l’on finit bien par obtenir un entier compris entre 0 et b −1 ? Démonstration • Existence du couple (q, r) : On démontre d’abord l’existence de (q, r) dans le cas où a ⩾0. Introduisons pour cela l’ensemble Q = n k ∈N/ a −bk ⩾0 o . Cet ensemble Q est une partie non vide de N — non vide car elle contient 0. Mais par ailleurs Q est majoré (par a). En effet, pour tout k ∈Q, a −bk ⩾0 donc k ⩽bk ⩽a. L’ensemble Q possède donc un plus grand élément q. Alors a −bq ⩾0. Mais comme (q + 1) / ∈Q, a −b(q + 1) < 0. Ces deux inégalités s’écrivent aussi 0 ⩽a −bq ⩽b −1. Posons donc r = a −bq. Alors tout va bien : nous l’avons trouvé, notre couple (q, r). Etendons à présent le résultat au cas où a < 0. Or si a < 0, alors −a ⩾0 et on est ramené au cas précédent : il existe un couple (q, r) ∈Z × N tel que −a = bq + r et 0 ⩽r ⩽b −1. Là encore, distinguons deux cas : 1) Si r = 0, posons q′ = −q et r′ = 0. Alors a = −bq −r = bq′ + r′ et 0 ⩽r′ ⩽b −1. 2) Si r ⩾1, posons q′ = −q −1 et r′ = b −r. Alors a = −bq −r = bq′ + r′ et 0 ⩽r′ ⩽b −1. Et voilà ! • Unicité du couple (q, r) : Donnons-nous deux couples (q, r), (q′, r′) ∈Z × N tels que a = bq + r = bq′ + r′, 0 ⩽r ⩽b −1 et 0 ⩽r′ ⩽b −1. Alors |r′ −r| ⩽b −1, mais par ailleurs b(q −q′) = r′ −r. Supposons q ̸= q′. Alors |q −q′| ⩾1, donc b|q −q′| ⩾b. On a donc : b ⩽b|q −q′| = |r′ −r| ⩽b −1, donc b ⩽b −1. Contradiction. Donc q = q′. On en déduit aussitôt que r = a −bq = a −bq′ = r′ comme voulu. • Enfin, les conditions sur q et r peuvent se réécrire ainsi : 0 ⩽a −bq < b, puis : a b −1 < q ⩽a b . On retrouve ici la définition de ja b k . ■ 2 c ⃝Christophe Bertault - MPSI    En pratique (Algorithme de la division euclidienne) Comment calcule-t-on de fait le couple uploads/Management/ cours-arithmetique-des-entiers-relatifs.pdf

Documents similaires

Fiche de lecture « Introduction à l’analyse de l’image » de Martine Joly Fiche 0 0

Actes du congrès de l’Actualité de la recherche en éducation et en formation (A 0 0

Introduction générale : I- Le contexte et l'intérêt de recherche : Considéré de 0 0

Rectorat de Créteil - Mission collège Groupe de travail Liaison collège/voie pr 0 0

Thomas Reverdy, Sociologie des Organisations 1 Manager la transversalité La com 0 0

UNIVERSITE ABDERRAHMANE MIRA DE BEJAIA FACULTE DES SCIENCES ECONOMIQUES, COMMER 0 0

Assurer la performance de l’organisation quotidienne d’un Mémo Version 1 entrep 0 0

1 Management 1 Chap 0. Introduction générale et développement industriel Chap 1 0 0

InnovaTech ASBL | Rue Auguste Piccard, 20 | 6041 Charleroi (Belgique) Tél : +32 0 0

1 L’ENTREPRISE FACE AUX DEFIS DE SON ENVIRONNEMENT Mr. Le coordonnateur : - Abd 0 0

• Détails
• Publié le Fev 14, 2021
• Catégorie Management
• Langue French
• Taille du fichier 0.1606MB