s
19 708 Pages

L 'arithmétique modulaire (Parfois appelé horloge arithmétique à cause de ce principe est basé le calcul des heures à 12 ou 24 cycles) est une branche importante de mathématiques. Il trouve des applications dans cryptographie, en la théorie des nombres (En particulier dans la recherche Les nombres premiers) Et il est la base de la plupart des tâches les plus courantes arithmétique et algébrique.

Il est un système arithmétique plein, dans lequel les numéros « wrap sur eux-mêmes » à chaque fois qu'ils atteignent les multiples d'un nombre donné n, dire forme. L'arithmétique modulaire et la notation habituelle de congruence ont été introduits officiellement par Carl Friedrich Gauss dans son traité Disquisitiones Arithmeticae, publié en 1801.

La relation de congruence

arithmétique modulaire est basée sur le concept de congruence modulo n. trois entiers de données à, b, n, avec n ≠ 0, on dit que à et b Ils sont le module congruent n, ou que a est congru à b modulo n, lorsque la différence (à - b) Il est multiple de n. Dans ce cas, nous écrivons

Par exemple, nous pouvons écrire

depuis 38-14 = 24, ce qui est un multiple de 12.

Si les deux chiffres sont positifs, vous pouvez aussi dire que à et b Ils sont le module congruent n si elles ont le même reste dans division pour n. On peut donc dire que 38 est conforme à 14 module 12 à la fois 38 et 14 ont le 2 reste lorsqu'il est divisé par 12.

Propriétés de congruence

équation équivalence

La congruence est un relation d'équivalence entre des nombres entiers mis en évidence par les propriétés suivantes:

  • propriétés réfléchissantes: Chaque numéro est conforme à lui-même forme n, pour chaque n différent de 0 fixé.
démonstration: Vous a - = 0. Mais comme on le sait, chaque entier est non nul diviseur de 0. Donc, n scissions (A - a)
  • propriétés symétriquessi à Il est conforme à b forme n puis b il est raisonnable de à forme n
démonstrationsi n scissions (A - B) , puis n divise aussi le contraire (B - a) = - (a - b)
  • propriété transitivesi à Il est conforme à b forme n et b Il est conforme à c forme n alors même à Il est conforme à c forme n.
démonstrationsi n scissions (A - B) et n scissions (B - C) puis, pour la propriété distributive de la division de la somme, n également divisé [(A - B) + (b - c)] = [a - b + b - c] = (a - c).

Invariance par rapport aux opérations arithmétiques

Une autre caractéristique importante de la relation de congruence est le fait d'être préservé des opérations arithmétiques habituelles entre les nombres entiers:

  • invariance addition: L'augmentation ou la diminution du même montant deux nombres congruents modulo n, les nouveaux chiffres obtenus sont encore en harmonie entre eux forment n. plus succinctement
démonstration: Nous écrivons (A - B) = (A - B + C - c) = (A + C) - (b + c)
  • invariance multiplication: On multiplie par une même forme de montant deux nombres congruents n, les nouveaux chiffres obtenus sont encore en harmonie entre eux sous forme n.
démonstrationsi n scissions (A - B) puis n scissions (A - B) × C
noteCette propriété ne peut être inversée si MCD (n,c) = 1.
  • Invariance par rapport à all'elevamento puissance: Forme élévatrices deux nombres congruents n à la même puissance k, les chiffres obtenus sont encore en harmonie entre eux sous forme n.
démonstrationsi a ≡ b ≡ 0 (mod n) la proposition est triviale. si a ≡ b (mod n) ne sont pas nuls, supposons que nous savons que . En multipliant les deux termes pour à grâce à l'invariance par multiplication, nous allons . Nous commençons maintenant à partir de la congruence a ≡ b (mod n) et multiplier les deux côtés par , toujours grâce à l'invariance par multiplication. Nous obtenons:. En comparant les deux expressions, et en utilisant la propriété symétrique et transitive, on en déduit que . Étant donné que la proposition est vraie pour k = 1 et le fait qu'il est vrai pour k-1 Cela implique qu'il est vrai pour k, pour principe d'induction la proposition est vraie pour chaque k.
noteCette propriété ne peut être inversée si k Il est différent de 0.

Le reste des classes de modules n

Les propriétés de réflexion, symétrique et transitive décrit ci-dessus indiquent que la relation de congruence du module n est un relation d'équivalence et par conséquent, il définit un ensemble quotient.

La division euclidienne d'ensemble à pour n, par quoi

à savoir

Il vous permet de diviser l'ensemble naturel les classes (sous-ensembles) en fonction de la relation d'équivalence suivante: on dit que l'ensemble de Il est équivalent à si et seulement si la différence Il est un multiple relatif de . Elle définit ainsi l'ensemble de quotient par rapport à cette relation d'équivalence et formé par n cours

appel classes de formulaire de repos .

Chacun du reste de la classe [r] Il représente, en plus de r mêmes, tous les nombres entiers de la forme à = k×n + r pour un certain nombre entier k.

Par exemple, dans la congruence modulo 7, le reste de la classe [5] représente, en plus du numéro 5, le numéro 12 (= 1 x 7 + 5), le numéro 19 (= 2 x 7 + 5), le nombre 2308 (= 329 x 7 + 5), etc. En outre, [5] représente également le nombre -2 (-1 = x 7 + 5), le nombre -9 (= -2 x 7 + 5), et ainsi de suite.

Le module de congruence arithmétique n

L'invariance décrit ci-dessus par rapport à l'addition et la multiplication indiquent que ces opérations sont bien définies également au quotient. Ces opérations continuent de se rencontrer commutativité, adhésion et distributif. Les éléments neutres pour l'addition et la multiplication sont les classes [0] et [1].

Les classes de formulaire n avec la formation d'une somme groupe abélien: Plus précisément, une forme groupe cyclique fini. Avec la somme et la forme de produit une anneau. Contrairement à ce qui se passe pour entiers, le produit de deux éléments non nuls peut être nulle. Par exemple:

si .

Cela ne se produit pas quand n est un premier numéroDans ce cas, en fait, les classes forment une domaine solidaire (Et même terrain).

Parmi les propriétés sont les suivantes:

racines primitives

icône Loupe mgx2.svg Le même sujet en détail: Générateur (théorie des nombres).

En raison de la présence éventuelle de partitions 0, n'est pas, en général, un groupe avec le produit. En fait Intercalaires 0 ont inverses. Mais quand il n'y a pas de 0 diviseurs non nulles (dans les cas avec n en premier) la multiplication forme un groupe multiplicatif et la bague Il est un champ. Cependant, si nous nous limitons à des classes dont les représentants sont me couvrir avec n, Cette propriété réapparaît. Il est facile de prouver par le recours à 'identité Bezoutsi à Il est coprime n, Il y a deux plein x et y de telle sorte que

à savoir, le module réduisant n,

puis chaque à Il a un revers. En outre, la multiplication continue d'être à l'intérieur de l'anneau et de posséder la associativité et commutative, et la classe [1] est l'élément neutre.

Un résultat important, déjà trouvé par Gauss, est que ce groupe est cyclique ssi n est 2, 4, la puissance d'un nombre premier impair ou le double de la puissance d'un premier nombre impair. Les générateurs de ce groupe cyclique sont parfois appelés racines primitives forme n.

Polynômes en arithmétique modulaire

icône Loupe mgx2.svg Le même sujet en détail: polynomiale congruences.

aussi il est possible, à travers les opérations définies avant, parler polynômes. Les propriétés de ceux-ci diffèrent dans bien des cas, des propriétés « régulières » observées lors de l'examen de polynômes champs comment ou , ou cliquez sur anneaux comment . Par exemple, le principe de l'identité des polynômes (deux polynômes prendre des valeurs égales si et seulement si leurs coefficients sont égaux à un pour un) n'est pas valide, bien que la valeur d'une version modifiée.

Même dans l'étude de ce sujet, ainsi que dans la plupart arithmétique modulaire, il existe deux types de comportements très différents quand n Il est d'abord et quand n Il est fait. Dans ce dernier cas, ne pas être ou un champ ou d'une domaine solidaire, le comportement des polynômes peut être très « étrange »: par exemple, le congruence polynomiale de degré 2 a quatre solutions (1, 3, 5 et 7) lorsqu'il est dans les champs sans fin tels que rationnel, réel ou complexe, le nombre de solutions ne peut pas dépasser le degré du polynôme.

dureté

les anneaux ils fournissent également une façon d'étudier l'irréductibilité des polynômes avec des coefficients entiers (et, par conséquent, pour la lemme de Gauss, même ceux qui ont des coefficients rationnel). En fait, si un polynôme est réductible dans l'anneau de polynômes avec des coefficients entiers que fa(X) =g(X)h(X), alors la même pour tout d'un premier module p:

Cette propriété peut être utilisé pour construire un critère irréductibilitéSi un polynôme non pris en compte , avec p premier qui ne divise pas le coefficient du terme de degré maximum, alors il n'a pas été pris en compte (par exemple est irréductible) dans .

L'inverse est pas vrai: Il est irréductible , mais dans Il est pris en

équations diophantiennes

De même, l'étude de l'irréductibilité des polynômes, dans l'étude des équations diophantiennes Il étudie parfois la même équation forment un ensemble n, de fournir des conditions nécessaires à la solvabilité de l'équation elle-même. Par exemple, l'équation

Il ne peut pas avoir des solutions entières, parce que s'il y avait une solution une telle solution serait par exemple également dans l'anneau du module de congruences 7; à-dire doit être congruence résoluble

qui n'a pas de solution, car les valeurs possibles qui suppose sont égaux à 0, 1 et 6.

bibliographie

  • H. Davenport, plus arithmétique, Zanichelli, Bologne, 1994, ISBN 88-08-09154-6, chapitre II.
  • Tom M. Apostol (1976): Introduction à la théorie analytique des nombres, Springer-Verlag, New-York, ISBN 0-387-90163-9, chapitre 5.

Articles connexes

D'autres projets