Entiers

Original: http://www.efgh.com/math/algebra/integers.htm

 
LOGOPhilip J. Erdelsky
12 décembre 2002
S’il vous plaît e-mail des commentaires, des corrections et des ajouts au webmestre à pje@efgh.com.
1. Сaractériser les entiers
L’ensemble Z + d’entiers positifs {1, 2, 3,…} est simple et familier, mais décrivant de manière parfaitement rigoureuse n’est pas négligeable. Beaucoup de nos théorèmes semblera être tellement évident qu’ils ne devraient pas exiger la preuve.
Comme toujours, en mathématiques, nous devons commencer avec certains postulats. Nous essayons de choisir un ensemble minimal des caractéristiques plus simples et la plus évidentes des entiers.
Certaines propriétés des entiers positifs sont faciles à l’État. Chaque nombre entier positif est suivie d’un autre nombre entier positif, que l’on appelle son successeur. Le numéro 1 est le premier entier positif, n’est pas le successeur de n’importe quel autre nombre entier positif. Tout autre nombre entier positif est le successeur d’un et un seul entier positif.
Le successeur de n s’écrira que n + 1. Toutefois, à ce stade nous avons défini pas n’importe quel autre type d’addition.
Nous pouvons définir 2 rigoureusement comme 1 + 1, 3 comme 2 + 1, etc., continuant la séquence seulement que requis pour une discussion particulière.
Une autre propriété est nécessaire, car il y a plusieurs systèmes différents des entiers positifs qui possède toutes ces propriétés. Un tel système se compose des entiers positifs, avec la relation habituelle de successeur et aussi deux autres éléments A et B, qui sont les successeurs des uns des autres.
La propriété est celui qui indique, en effet, que chaque nombre entier positif est 1, ou 2, ou 3 ou 4, et ainsi de suite indéfiniment. Malheureusement, « et ainsi de suite indéfiniment » a pas sa place dans une définition rigoureuse, même si nous pensons que nous savons ce que cela signifie.
Heureusement, il existe une alternative.
Un sous-ensemble de Z + est dit être fermé en vertu de l’obligation du successeur s’il contient les successeurs de tous ses éléments ; autrement dit, si n est le sous-ensemble, alors n + 1 est aussi dans le sous-ensemble. Par exemple, {1, 2} n’est pas fermé en vertu de l’obligation du successeur, mais {3, 4, 5,…} est.
Maintenant, nous pouvons affirmer la propriété required finale des entiers positifs : tout sous-ensemble de Z + qui contient 1 et fermée en vertu de l’obligation du successeur contient tous les entiers positifs.
En fait, nous pouvons faire faire à des conditions légèrement plus faibles, que l’on appelle les postulats de Peano :
  1. Chaque nombre entier positif a un successeur.
  2. Le numéro 1 n’est pas le successeur d’un entier positif.
  3. Chaque entier positif autre que 1 est le successeur au plus un entier positif.
  4. N’importe quel ensemble d’entiers strictement positifs qui contient 1 et fermée en vertu de l’obligation du successeur contient tous les entiers positifs.
Deux autres propriétés assez évidentes des entiers positifs peuvent être prouvées comme un théorème.
Théorème 1.1. Chaque entier positif autre que 1 est le successeur d’exactement un nombre entier positif, et aucun nombre entier positif n’est son propre successeur.
Preuve. Supposer, aux fins de la contradiction, que le nombre entier positif n est différent de 1 et n’est pas le successeur d’un entier positif ou est son propre successeur. Puis, dans les deux cas l’ensemble Z + {n} viole Peano postulat (4).
Théorème 1.1 peut aussi dire de manière plus concise. La fonction de successeur f (n) = n + 1 est une bijection de Z + sur Z + {1}.
Il est maintenant facile de montrer que 1, 2, 3 et 4 sont toutes distinctes. Si 1 = 2, 1 = 3 ou 1 = 4, puis 1 serait le successeur de 1, 2 ou 3, respectivement. Si 2 = 3, 3 = 4, puis 2 ou 3 serait son propre successeur. Si 2 = 4 alors 1 = 3, parce que chaque entier est le successeur d’un seul entier, et 1 = 3 a déjà été exclu. Des arguments semblables peuvent être utilisés pour n’importe quel nombre d’entiers qui peuvent être énumérés et traitées de manière exhaustive.
Nous n’avons pas défini de soustraction encore, mais pour un nombre entier positif n, autre que 1, nous allons utiliser la notation n-1 pour désigner le nombre entier dont le successeur est n.
2. L‘induction et la récursivité
Postulat de Peano (4) est souvent appelé le postulat de l’induction mathématique, car il peut être casté dans ce formulaire.
La technique d’induction mathématique comprend deux étapes. Prendre une déclaration sur l’entier n.
  • Étape 1: Prouver la déclaration pour n = 1.
  • Étape 2: Assumer que l’affirmation est vraie pour n et puis le prouver pour n + 1.
La déclaration doit alors être vraie pour tous les entiers positifs. À l’étape 2, l’hypothèse que l’affirmation est vraie pour n est souvent appelée l’hypothèse inductive. La technique est donnée une justification formelle par le théorème suivant.
Théorème 2.1. Que S soit une déclaration sur un entier positif et suppose que
  1. S est vraie pour 1,
  2. pour tout n, si S est vrai pour n puis c’est vrai pour n + 1.
Alors S est vraie pour tous les entiers positifs.
Preuve. Soit T l’ensemble de tous les entiers positifs qui S est vrai. Puis le postulat de Peano (4) affirme que T contienne tous les entiers positifs.
Dans certains cas nous devons utiliser double induction.
Théorème 2.2. Laissez S (m, n) être une déclaration au sujet de deux entiers positifs et suppose que
  1. S (1, 1) est vrai,
  2. pour tous les m, n, S (m, n) implique S (m + 1, n) et S (m, n + 1).
Alors S (m, n) est vraie pour toutes les paires d’entiers positifs.
Preuve. Soit T(n) la déclaration « S (m, n) est vraie pour tous les entiers m ». Puis nous prouver T(n) par induction.
Pour n = 1, T(1) devient « S (m, 1) est vrai pour tous les m ». Cela peut être prouvé par induction sur m :
Pour m = 1, S (m, 1) est vrai par hypothèse (1).
Si S (m, 1) est vraie, alors S (m + 1, 1) est vrai par hypothèse (2).
Ensuite, nous supposons T(n), qui devient « S (m, n) est vraie pour tous les m ». Par hypothèse (2), « S (m, n + 1) est vrai pour tous les m », qui est T(n+1).
C’est pourquoi T(n) est vraie pour tout n, qui était le but recherché.
Étroitement liés à la mathématique de l’induction est une technique appelée la récursivité. Nous pouvons définir une fonction f en définissant f (1) et en définissant www.com/~Stan/problemColumns/FQ/fqinfo.html sur le plan n et f (n). Le théorème suivant montre que cette technique ne définit une fonction unique sur les entiers positifs.
Théorème 2.3. Soit R un ensemble non vide. Soit F: R Z + R et soit A être tout élément de R. Il y a un seul et qu’une fonction f: Z + R tels que
  1. f (1) = A
  2. f(n+1) = F(f(n), n)
Preuve. Tenez compte de tous les sous-ensembles S de Z + R qui obéissent aux deux conditions suivantes :
  1. (1, A) ∈ S,
  2. if (n, r) ∈ S then (n+1, F(r,n)) ∈ S.
Soit T l’intersection de ces sous-ensembles. Alors clairement T aussi obéit aux mêmes conditions de deux, et T est un sous-ensemble propre à chaque autre jeu qui obéit à des conditions.
Ensuite, nous prouvons par induction que pour tout n entier positif, il existe un et un seul r tel que (n, r) est en T.
Pour n = 1 ce qui revient à l’assertion que (1, A) est le seul couple T avec le premier élément 1. Supposer, aux fins de la contradiction, que (1, B) est en T pour certains B r autres qu’a. Puis le set T {(1, B)} obéit à ces deux conditions mais T n’est pas un sous-ensemble propre à elle.
Maintenant supposons que l’hypothèse est vraie pour n et (n, r) est la seule paire en T avec le premier élément égal à n. Alors (n + 1, F(r,n)) est aussi dans le T. supposer, aux fins de la contradiction, que (n + 1, C) est en T pour certains C r autre que F(r,n). Puis le set T {(n + 1, C)} obéit à ces deux conditions mais T n’est pas un sous-ensemble propre à elle.
Pour tout entier positif n, que f (n) être l’élément d’A tel que (n, f(n)) appartient à T. Ensuite, il est facile de montrer que f est la fonction requise.
Il est facile de prouver, par induction, que la fonction f est unique.
Il y a essentiellement qu’un seul système d’entiers positifs, comme le montre le théorème suivant.
Théorème 2.4. Les deux systèmes obéissant les postulats de Peano sont isomorphes ; c’est-à-dire, si X et Y sont deux de ces systèmes, il y a un f correspondance biunivoque: X Y tel que f (1) = 1 et f(n+1) = f(n)+1.
Preuve. Par le théorème précédent, il y a une fonction f: X Y tels que
  1. f(1) = 1
  2. f(n+1) = f(n)+1
La fonction f est l’isomorphisme nécessaire, pourvu que c’est un à un et son aire de répartition est l’ensemble de Y.
Tout d’abord, nous montrons que f est un à un, c’est-à-dire que f(a) = f(b) implique qu’ a = b. Nous utilisons l’induction sur le n de valeur commune de f(a) et f(b).
Pour n = 1, nous avons f(a) = f(b)= 1. Si un n’est pas égal à 1, alors a = c + 1 pour certains c entier et donc f(a) = f(c+1) = f (c) + 1, qui n’est pas égal à 1. Donc a = 1. De même, b = 1.
Supposons maintenant que f (a) = f(b) = n implique qu’ a = b et envisager de f(c) = f(d) = n+1. C ne peut être égal à 1, alors c = g + 1 pour certains entiers g. d’où f(c) = f(g+1) = f(g)+1 = n+1, donc f(g) = n. De même, d = h + 1 et f (h) = n. Par hypothèse inductive, g = h. Donc c = g+1 = h+1 = d.
Nous avons maintenant montrent que la gamme de f est les Y. clairement 1 est de l’ordre, et si n est de l’ordre, donc est n + 1. Par induction mathématique, tous les éléments y sont de l’ordre.
3. Ajout
Les entiers positifs ont aussi une opération d’addition. Jusqu’ici, nous avons vu qu’un seul exemple d’addition, n + 1. Nous voudrions plus d’être compatible avec cet exemple et à obéir aux lois associatives et commutatives :
  1. n + 1 est le successeur de n
  2. m+(n+p) = (m + n) + p (l’addition est associative)
  3. m + n = n + m (l’addition est commutative)
Théorème 3.1. Il y a exactement un moyen de définir l’addition sur Z + telle que l’addition est associative et n + 1 est le successeur de n pour tout n entier positif.
Preuve. Soit m un entier positif. Par le théorème 2.3 il y a une fonction fm telle que :
  • fm(1) = m+1,
  • fm(n+1) = fm(n)+1 pour tout n entier positif.
Définissez ensuite les m + n pour être fm(n). Il est clair que pour tous les entiers strictement positifs m et n,
  • m + 1 est le successeur de m,
  • m+(n+1) = (m + n) + 1 pour tout n entier positif.
Nous devons maintenant montrer que cette opération est associative, même lorsque l’opérande dernier n’est pas 1, c’est-à-dire que m+(n+p) = (m + n) + p pour tous les entiers strictement positifs m, n et p.
Nous utilisons l’induction sur p. Pour p = 1 il a déjà fait ses preuves. Alors si m+(n+p) = (m + n) + p,
m+(n+(p+1)) = m+((n+p)+1) = (m+(n+p)) + 1 = ((m+n) + p) + 1 = (m+n)+(p+1),
Il est également vrai pour p + 1.
Si ++ est une autre opération associative tels que m ++ 1 = m + 1, alors on peut facilement démontrer par induction sur m que m ++ n = m + n pour tout n entier positif donc l’opération est unique.
On n’a pas besoin de plus d’être commutative, mais nous pouvons prouver qu’il est.
Théorème 3.2. Pour tout entiers strictement positifs m et de n, m + n = n + m.
Preuve. Nous avons d’abord prouver le cas particulier 1 + n = n + 1 par induction sur n. Pour n = 1 c’est évident. Si 1 + n = n + 1, puis 1+(n+1) = (1 + n) + 1 = (n + 1) + 1.
Maintenant, nous le prouvons le m cas général + n = n + m par induction sur m. Pour m = 1, il réduit au cas particulier. Si m + n = n + m puis (m + 1) + n = m+(1+n) = m+(n+1) = (m + n) + 1 = (n + m) + 1 = n+(m+1).
Nous n’avons pas soustraction encore, mais nous avons un droit d’annulation.
Théorème 3.3.  Si m + p = n + p pour tout entiers strictement positifs m, n et p, alors m = n.
Preuve. Nous utilisons l’induction sur p. Pour p = 1 l’affirmation est identique au postulat de Peano (3). Si m+(p+1) = n+(p+1) puis (m + p) + 1 = (n + p) + 1, donc m + p = n + p par le même postulat et m = n par l’hypothèse inductive.
Les théorèmes suivants peuvent sembler évidents, mais nous aurons besoin d’eux dans la section suivante.
Théorème 3.4. Pour tout entiers strictement positifs m et de n, m + n n’est pas égal à m ou n.
Preuve. Nous utilisons l’induction sur n. Pour n = 1, m + 1 n’est pas égal à 1 car 1 n’est pas le successeur d’un entier positif. Si m + n n’est pas égale à n, alors m + n + 1 n’est pas égal à n + 1 parce que différents entiers ne peut pas avoir le même successeur.
Puisque l’addition est commutative, m + n n’est également pas égal à m.
Théorème 3.5. Pour tous les entiers strictement positifs m et n, un et un seul des éléments suivants est titulaire :
  • (1) m = n.
  • (2) il existe un entier positif p tel que m + p = n.
  • (3) il existe un entier positif q tel que m = n + q.
Preuve. Théorème 3.4 montre que (1) est incompatible avec (2) ou (3). De plus, si (2) et (3) ont été tous deux true, alors m = m + p + q, ce qui est impossible par théorème 3.4. Cela montre que seulement une des conditions peut contenir.
L’autre partie est de la double induction sur m et n. Si m = n = cales 1 puis (1). Supposons maintenant qu’une des conditions est titulaire.
Si m = n, alors obéissent à m et n + 1 (2), et obéissent à m + 1 et n (3).
Si m + p = n, nous considérons les deux cas.
Si p = 1, puis m + 1 = n, alors obéissent à m + 1 et n (1), et obéissent à m et n + 1 (2) parce que m + 1 + 1 = n + 1, donc m + 2 = n.
Si p n’est pas 1, alors p = r + 1 pour certains r, alors m + r + 1 = n. Puis obéissent à m + 1 et n (2) et le faire si m et n + 1.
La preuve dans le cas m = n + q est similaire.
4. Vous passez votre commande
L’ordre des entiers positifs (1, 2, 3, etc.) est un des leurs propriétés plus familiers, mais il est assez difficile d’examiner rigoureusement.
Théorème 4.1 Il y a un et seulement une commande linéaire des entiers positifs tels que n < n + 1 pour chaque nombre entier positif n et m < n si et seulement si, il existe un entier positif p tel que m + p = n.
Preuve. Décrivez m < n s’il existe un entier positif p tel que m + p = n. Si n < s il y a un t entier positif tel que n + t = s. Puis (m + p) + t = s, donc m + (p + t) = s et la relation est transitive. Théorème 3.5 montre que c’est un ordre linéaire.
Laissez < être n’importe quel ordre linéaire telle que n < n + 1 pour tout n. Puis nous montrons, par induction sur p, que m < m + p pour n’importe quel entier positif p. Pour p = 1 il est vrai par hypothèse. Si m < m + p, puis m + p < m + p + 1 par hypothèse et m < m + p + 1 car l’opération est transitive. Si m < n par l’ordre linéaire, puis par le théorème de 3,5 m = n ou il existe un p ou q tel que m + p = n ou m = n + q. La première possibilité est éliminée parce que l’opération est un ordre linéaire. La troisième possibilité implique que n < m, ce qui est également éliminé. Donc m + p = n.
À ce stade, nous pouvons commencer à utiliser certaines des propriétés plus évidentes des entiers positifs.
5. Comptage
Deux ensembles A et B ont le même nombre d’éléments, s’il y a une correspondance biunivoque entre eux, c’est-à-dire une fonction f: A B tel que f (x) = y si et seulement si x = y. On montre facilement qu’il s’agit d’une relation d’équivalence.
Laissez [1, n] représentent l’ensemble de tous les entiers positifs inférieurs ou égaux à n, c’est-à-dire {m Z + | m n}. Nous disons que cet ensemble a n éléments. N’importe quel jeu qui a le même nombre d’éléments que [1, n] également a n éléments. En outre, le critère pour cela, une correspondance biunivoque entre [1, n] et un ensemble A, est une description formelle du processus de comptage tous les jours.
Théorème 5.1 Les ensembles [1 m] et [1, n] ont le même nombre d’éléments si et seulement si m = n.
Preuve. Si m = n, alors [1 m] et [1, n] sont identiques. L’inverse peut être prouvé par induction sur m. Si [1,1] et [1, n] ont le même nombre d’éléments, toute correspondance bi-univoque entre eux doit porter 1 fois 1 et n (et autres éléments de [1, n]). C’est impossible sauf si n = 1.
Supposons maintenant [1, m + 1] et [1, n] ont le même nombre d’éléments et soit f une correspondance biunivoque entre eux. L’argument précédent montre que n = 1 n’est pas possible, donc n-1 est un entier positif.
Si f(m+1) = g n, laisser être f ; Sinon, définissez g par
  • g(m+1) = n,
  • g (f-1(n)) = f(m+1), et
  • g(p) = f (p), pour tous les p pas égal à m + 1 ou f-1 (n).
Puis g(m+1) = n et g limitée à [1 m] est une correspondance biunivoque avec [1, n-1]. Par induction hypothèse m = n-1, qui est équivalent à m + 1 = n.
Théorème 5.2 Si A et B sont des ensembles disjoints avec m et n éléments, respectivement, alors l’union C entre A et B a m + n éléments.
Preuve. Laissez f: A [1 m] et g: B [1, n] être correspondance biunivoque. Définissez ensuite h: C [1, m + n] la manière évidente :
  • h (x) = f (x) si x est dans A,
  • h (x) = m + g (x) si x est dans B.
La fonction h peut être démontré un à un. Si x y, puis clairement h (x) h(y) si x et y sont tous deux a ou en B. Si x est dans A et y est b, alors nous pouvons utiliser les propriétés de l’ordre établies dans la section précédente pour montrer que h (x) h(y).
De même, nous pouvons montrer que h est sur [1, m + n]. Laissez y être en [1, m + n]. Alors envisager les cas y < m, y = m et y > m. Si y < m ou y = m, puis h-1(y) = f-1(y). Si y > m alors y = m + p pour certains p et h-1(y) = g-1(p).
À ce stade, nous pouvons affirmer une extension assez simple d’induction mathématique.
Théorème 5.3 Let S être une déclaration sur un entier positif et suppose que
  1. S est vraie pour 1,
  2. pour tout n, si S est vrai pour [1, n] alors c’est vrai pour n + 1.
Alors S est vraie pour tous les entiers positifs.
Preuve. Appliquer le théorème 2.1 pour l’instruction « S est vrai pour tous les entiers compris entre 1 et n, inclusive ».
Cette variante de l’induction mathématique est plus pratique dans bien des cas, car l’hypothèse inductive permettant de prouver un État S à n + 1 est un peu plus générale. On peut supposer que S est titulaire pour une ou l’ensemble des entiers compris entre 1 et n, inclusivement.
6. Multiplication
La multiplication des entiers positifs est une autre opération familier. Officieusement, multiplication peut être définie comme une addition répétée :
mn = m + m + m + + m (n fois)
Ceci suggère les propriétés formelles suivantes :
  1. m1 = m
  2. m(n+1) = mn + m
Il n’y a qu’une seule opération avec ces propriétés.
Théorème 6.1. Il y a exactement une seule façon de définir la multiplication des entiers positifs tels que m1 = m et m(n+1) = mn + m.
Preuve. Soit m un entier positif. Par le théorème 2.3 il y a une unique fonction fm telle que :
  • fm(1) = m
  • fm(n+1) = fm(n) + m pour tout n entier positif
Nous définissons mn = fm(n). Suivent les propriétés désirées directement à partir de la définition de f.
Multiplication possède trois propriétés qui requièrent la preuve.
Théorème 6.2. Multiplication des entiers positifs a les propriétés suivantes :
  • m(n+p) = mn + mp (la multiplication est distributive sur l’addition)
  • m(np) = p (mn) (la multiplication est associative)
  • mn = nm (la multiplication est commutative)
Preuve. Nous prouvons la distributivité par induction sur p. Pour p = 1 distributivité découle de la façon de multiplication a été définie. Supposons maintenant que m(n+p) = mn + mp. Puis
m(n+(p+1)) = m((n+p)+1) = m(n+p) + m = (mn + mp) + m = mn+(mp+m) = mn+m(p+1).
Nous prouvons associativité par induction sur p. Pour p = 1 associativité est triviale. Supposons maintenant m(np) = p. (mn) puis
m(n(p+1)) = m (np + n) = m(np) + mn = p (mn) + mn = (mn)(p+1).
Nous prouvons commutativity en deux étapes. Tout d’abord, nous prouvons par induction sur m que 1m = m1 = m. Pour m = 1 c’est trivial. Supposons maintenant 1m = m. puis
1(m+1) = 1 m + 1 = m + 1.
Maintenant, nous prouvons que mn = nm par induction sur n. Pour n = 1, c’est le résultat vient de prouver. Supposons maintenant mn = nm. Puis
m(n+1) = mn + m = nm + m = m + nm = m(1+n) = m(n+1).
Car la multiplication est commutative, distributivité fonctionne de deux façons :
  • m(n+p) = mn + mp,
  • m (n + p) = nm + pm.
Une des propriétés de la multiplication et la commande est facile à prouver :
Théorème 6.3. Si m, n, p et q sont des entiers positifs et m > n et p > q, puis mp > nq.
Preuve. Par définition, il sont a des entiers positifs vous et v tel que m = n + vous et p = q + v. Par la législation associative et distributive :
mp = (n+u)(q+v) = q (n + u) + (n + u) v = nq + uv uq + nv = nq + (uq + nv + uv).
Donc mp > nq par définition.
7. Zero
Le concept du zéro est venu assez tard dans l’histoire des mathématiques. Les méthodes géométriques de l’antiquité n’a pas besoin il.
De nombreuses propriétés des entiers positifs sont plus facilement décrites si nous définissons un entier supplémentaire 0. Le système de numération prolongé s’appelle l’ensemble des nombres entiers. La propriété fondamentale de 0, c’est que c’est une identité d’additif :
n + 0 = 0 + n = n n est un entier non négatif
Il est facile de montrer que l’addition de nombres entiers est associative et commutative, lors de l’ajout de 0 est défini de cette manière. Il peut aussi être établi que 0 est la seule identité d’additif ; c’est-à-dire que
m + n = n implique que m = 0.
Nous voulons définir multiplication par 0, alors la loi distributive est toujours vraie :
mn = m(n+0) = mn + m0.
Ceci est possible seulement si m0 = 0. Si la multiplication doit être commutative, 0 m = 0, trop.
Il est facile de montrer que les lois commutatives, distributives et associatifs détiennent pour l’addition et la multiplication de nombres entiers lors de l’addition et la multiplication par 0 sont définis à ces égards.
Nous étendons la relation commande en définissant 0 < n pour tout n entier positif. Il est facile de montrer que le lien étendu est un ordre linéaire.
8. Négative entiers et soustraction
Nous pouvons développer davantage le système de numération en définissant un nombre entier négatif (-n) correspondant à chaque nombre entier positif n. Nous définissons l’addition d’un entier positif et sa les correspondants négatif entier comme suit :
n + (-n) = (-n) + n = 0.
Les entiers positifs, le zéro et les entiers négatifs sont appelés ensemble d’entiers et sont généralement représentés par Z.
Pour être complet, nous définissons (-0) à 0 ; et si (-n) est un nombre entier négatif, puis nous définissons (-(-n)) pour être n. d’où l’identité ci-dessus vaut pour tout entier n. En outre,
-(-n) = n
pour tout entier n, si positif, négatif ou zéro.
Pour tout entier n, on définit la valeur absolue |n| n comme suit :
  • Si n est positif ou nul, |n| = n,
  • Si n est un entier négatif, puis |n| = (-n).
Comme nous l’avons fait avec 0, que nous voulons définir les autres opérations avec des nombres négatifs pour la plupart des propriétés des nombres entiers tiendra toujours.
L’ajout d’un nombre négatif et 0 doit préserver le statut spécial de 0 comme l’identité de l’additif :
(-n) + 0 = 0 + (-n) = (-n).
Lorsque deux nombres négatifs sont ajoutées, nous remarquons que, si la législation associative et commutative continue de tenir, puis
(-m) + (-n) + (m + n) = (-m) + m + (-n) + n = 0 + 0 = 0.
Par conséquent, nous sommes tenus de définir l’addition de deux nombres négatifs comme suit :
(-m) + (-n) = (-(m+n)).
Quand un m nombre positif et un nombre négatif (-n) sont ajoutées, il y a trois possibilités :
  1. Si m = n, alors m + (-n) = m + (-m) = 0.
  2. Si m > n, alors m = n + p pour certains p positive et donc m + (-n) = n + p + (-n) = n + (-n) + p = 0 + p = p.
  3. Si m < n, alors n = m + p pour certains p positive et donc m + (-n) = m + (-(m+p)) = m + (-m) + (-p) = 0 + (-p) = (-p).
Il peut être démontré que l’addition d’entiers, avec ces définitions pour l’addition des entiers négatifs, est toujours associative et commutative.
Étonnamment, il est plus facile d’étendre la définition de la multiplication des entiers négatifs.
Si m et n sont des entiers positifs, alors si la loi distributive continue à détenir pour les entiers négatifs
m(-n) + mn = m((-n)+n) = m(0) = 0,
et nous devons définir
m(-n) = (-(mn)).
Si la multiplication est commutative, puis
(-n) m = (-(nm)).
De même,
(-m). (-n) + (-m) n = (-m)((-n)+n) = (-m) 0 = 0,
et nous devons définir
(-m). (-n) = (-((-m)n)) = mn.
On montre que les lois commutatives, associatives et distributives tenir lorsque la multiplication est définie de cette façon.
Nous avons déjà prouvé que m < n s’il existe un entier positif p tel que m + p = n. Pour maintenir cette propriété lorsque m ou n ou les deux, peuvent être négatifs, il faut définir
  • m < n lorsque m est négatif et n est non négative
  • m < n chaque fois que m et n sont tous deux négatifs et (-n) < (-m)
Nous sommes maintenant en mesure de définir la soustraction :
m n = m + (-n).
Si m et n sont positifs et m > n, alors ceci est en accord avec la définition usuelle de la soustraction. Dans ce cas m = n + p pour certains p positive, alors m n = n + p + (-n) = p + n + (-n) = p + 0 = p.

 

L’utilisation de nombres négatifs simplifie les calculs dans de nombreux cas, même dans les applications les nombres négatifs n’apparaissent pas dans les données ou les résultats. Par exemple, dans un système sans négatif nombres une expression comme 5 + 6-7 peut être évaluée comme (5 + 6) -7, mais pas comme 5+(6-7) parce que 6-7 n’existerait pas.
9. Division
Entiers peuvent être ajoutés, soustrait ou multipliés. Division n’est pas toujours possible, à moins que nous permettent les restes. Le théorème suivant est souvent appelé l’algorithme de division.
Théorème 9.1. Si n (le dividende) est un entier et d (diviseur) est un entier positif, alors il existe q entiers uniques (le quotient) et r (le reste) tel que
n = qd + r et 0 r < d.
Preuve. Tout d’abord nous prouver que q et r existent toujours.
Si n = 0 alors q = r = 0. Si d = 1 alors q = n et r = 0. Si n = 1 et d > 1 alors q = 0 et r = 1.
Pour n &gt; 1 et d > 1, nous utilisons l’induction sur n. Par hypothèse inductif,
n = qd + r et 0 r < d.
Alors clairement
n + 1 = qd + r + 1.
Si r + 1 < d, c’est le résultat requis pour n + 1. Non, r + 1 = d. puis
n + 1 = qd + r + 1 = qd + d = (q + 1) d,
qui est le résultat requis pour n + 1 avec r = 0.
Si n < 0 then -n est positif, alors
-n = qd + r et 0 r < d.
C’est pourquoi
n = (-q) d r
Si r = 0 c’est le but recherché. Si r &gt; 0 then
n = (- q – 1) d + d r,
et r-d est dans la gamme des valeurs requises.
Supposons maintenant que q’ et r’ sont tels que
n = q a + r’ et 0 r’ < d.
Puis
0 = (q-q’) d + (r-r’) et -d < r-r’ < d.
De manière équivalente,
(q-q’) d = r’-r et -d < r’-r < d.
Mais si q-q’ 1 puis (q-q’) d d et si q-q’ -1 alors (q-q’) d-d. d’où q-q’ = 0 et r’-r = 0.
Bien que nous ne pouvons pas toujours diviser, nous avons un droit d’annulation pour la multiplication :
Théorème 9.2. Si m, n et d sont des entiers, md = nd et d n’est pas zéro, alors m = n.
Preuve. Si d est positif, puis par l’algorithme de division, il y a unique entiers q et r tels que
md = nd = qd + r, 0 r < d,
Nous remarquons que q = m et r = 0 ou q = n et r = 0 sont deux paires qui remplissent ces conditions. Étant donné que les entiers sont uniques, m = n.
Si d est non nul et n = qd reste zéro, alors nous disons que
  • n est divisible par d, ou
  • d divise n, ou
  • d est un diviseur de n, ou
  • d|n
et q = n/j.
Quelques résultats sur la divisibilité sont évidents :
  • Tout entier non nul se divise.
  • Tout entier non nul a divise zéro.
  • Les seuls diviseurs de 1 sont 1 et -1.
  • Les entiers de 1 et -1 divisent tout entier.
  • Si m divise n et n divise m, alors m = n ou m = – n.
  • Si m divise n et n divise p, m divise p.
  • Si m et n sont des entiers positifs et m > n, puis m ne divise pas n.
  • Si m divise n et p, puis m divise n + p et n-p.
  • Si m divise n ou p, m divise np.
Dans le cadre de notre enquête de divisibilité, nous ne considérons que des entiers positifs ; dans la plupart des cas, l’extension à des entiers négatifs est triviale.
Je m et n deux entiers positifs. Nous disons que g est le plus grand commun diviseur de m et n
  • g divise les m et n, et
  • chaque nombre entier positif qui divise les deux m et n divise aussi g.
Le théorème suivant indique non seulement que tout deux entiers positifs ont un plus grand commun diviseur, mais suggère également une méthode pratique de calcul il. On l’appelle l’algorithme d’Euclide.
Théorème 9.3. Tout deux entiers strictement positifs m et n ont un plus grand commun diviseur g, et il existe des entiers a et b tels que
am – bn = g.
Preuve. Laisser z = m + n-1. Nous utilisons l’induction sur z. Si z = 1, alors clairement m = n = 1, g = 1, a = 1 et b = 0.
Si z > (si m > n, nous pouvons utiliser le même argument avec m et n inversés.) Par le théorème 9.1 il y a des nombres entiers q et r tels que
n = qm + r, 0 r < m.
Si r = 0, alors a = 1, b = 0 et g = m, et il est clair que g est le plus grand commun diviseur de m et n.
Si r n’est pas zéro, puis nous remarquons tout d’abord que chaque diviseur de m et n est aussi un diviseur de r, et que chaque diviseur de m et r est aussi un diviseur de n. par conséquent, le plus grand commun diviseur de m et r est le même que le plus grand commun diviseur de m et n.
Depuis m≤n, r < n et m + n-1 < m + r-1. Donc nous pouvons utiliser l’hypothèse inductive sur m et r pour obtenir des nombres entiers a’, b’ et g telle que :
a’m – b’r = g.
Alors il est facile de montrer que g et les valeurs suivantes d’a et b satisfaire toutes les exigences :
a = a’ + b ‘ q, b = b’.
Le plus grand commun diviseur de m et n sont en général écrites (m, n) ou pgcd.
10. Nombres premiers
Un nombre premier p est un entier supérieur à 1, ce qui n’est pas divisible n’importe quel entier positif sauf 1 et p.
Théorème 10.1. Tout entier supérieur à 1 est premier ou un produit de nombres premiers.
Preuve. Nous utilisons l’induction. Clairement l’affirmation est vraie pour 1, quoique ridiculement.
Si un entier supérieur à 1 est un nombre premier, la déclaration est clairement vraie. Si pas, alors il peut être pris en compte dans deux petits entiers, ni de qui est 1. Par hypothèse inductive, chacun d’eux est soit premier, soit un produit de nombres premiers. D’où le nombre lui-même est un produit de nombres premiers.
Si pgcd = 1, m et n sont censées être relativement privilégiée.
Théorème 10.2. Si un nombre premier p divise la mn de produit de deux entiers positifs, alors il divise m ou n (ou les deux).
Preuve. Supposons, dans le but de contradiction, que p ne divise pas soit m ou n. Puisque p est un nombre premier, ses seuls diviseurs sont 1 et p. Étant donné que p ne divise pas m, le seul diviseur commun de p et m doit être 1. Puis par théorème 9.3, il y a des nombres entiers a et b tels que
ap bm = 1.
De même, il existe des entiers c et d tels que
cp dn = 1.
Multipliant ces deux équations donne
acp2 – adnp – cbmp + bdmn = 1.
Ensuite chaque trimestre sur le côté gauche est divisible par p, mais le membre de droit n’est pas divisible par p. C’est la contradiction désirée.
Corollaire 10.3. Si un nombre premier divise le produit de trois ou plus des entiers positifs, il divise au moins un d’entre eux.
Théorème 10.4. Laissez p1 p2 … pm = q1 q2 … qn, tous les facteurs sont premier. Alors m = n et le droit membre contient les mêmes facteurs que le membre de gauche, différant au plus dans l’ordre.
Preuve. Nous utilisons l’induction sur m. Si m = 1, puis n doit être également 1, sinon p1 serait un produit de nombres premiers et ne saurait s’amorcer. Donc  p1 = q1.
Si m>1; puis par corollaire 10.3 p1 doit diviser au moins un des facteurs dans q1 q2 … qn. Étant donné un nombre premier ne peut pas diviser un nombre premier différent, p1 doit être égale au moins un des facteurs dans q1 q2 … qn
Nous utilisons le théorème 9.2 de grève ce premier commun des deux côtés. Ensuite, nous utilisons l’hypothèse inductive sur ce qui reste.
Le théorème suivant découle directement des théorèmes 10.1 et 10.4. On l’appelle le théorème fondamental de l’arithmétique.
Théorème 10.5. Tout entier supérieur à 1 peut être pris en compte dans un ou plusieurs nombres premiers de manière unique en dehors de l’ordre des facteurs.
10. L‘arithmétique modulaire
Soit M un entier positif. Deux entiers m et n sont censés être en harmonie en ce qui concerne le module M si le leur différence m-n est divisible par N. C’est parfois abrégé en « congrus modulo M », ou simplement « congruent » lorsque le module est compris. Dans les symboles, la relation s’exprime tant que m n (mod M) ou m n lorsque le module est compris.
On montre facilement que la congruence en ce qui concerne un module particulier est une relation d’équivalence :
  • Elle est réflexive: n n.
  • Il est symétrique: m n implique que m n.
  • Il est transitif: m  n et n p implique que m p.
Congruence possède d’autres propriétés en commun avec l’égalité. Entiers congrus ont congruentes sommes, des différences et des produits ; c’est-à-dire, si a ≡ b et c d puis a+c ≡ b+d, a-c ≡ b-d et ac ≡ bd. (Cependant, a/c n’est pas nécessairement congrus à b/d, même si les quotients existent.)
Nous pouvons définir puis addition et la multiplication modulo M pour l’ensemble {0, 1, 2,, M-1}. Si m et n sont dans cette série, alors la somme modulaire et le produit de m et n sont les restes quand m + n et mn, respectivement, sont divisés par arithmétique de M. modulaire de ce type obéissent aux mêmes lois de commutatives, associatives et distributives arithmétique ordinaire. Les relations de commandes ne s’appliquent pas, mais zéro conserve son statut comme l’identité de l’additif et chaque nombre entier n a un négatif M-n. Le symbole ZM est utilisé pour représenter l’ensemble {0, 1, 2,, M-1} avec ces opérations.
Congruence pour un module particulier étant une relation d’équivalence, il y a des classes d’équivalence, qui sont souvent appelés les classes de résidus modulo M. L’algorithme de division montre que n’importe quel entier est congru à un seul des 0, 1, 2,, M-1 modulo M ; à savoir, le reste quand il est divisé par M. Ce numéro est parfois appelé ses résidus modulo M. Les classes d’équivalence servent parfois au lieu de l’ensemble {0, 1, 2,, M-1} les nombres en arithmétique modulaire. Toutefois, cette approche ne produit pas des résultats très différents.
Si le module M est un nombre premier, nous pouvons aussi diviser par un nombre différent de zéro. Si n est dans {1, 2,, M-1}, alors le plus grand commun diviseur de n et M est 1, et y sont des entiers un et b tel an + bM = 1, donc un 1 et m amn pour n’importe quel entier m. donc le résidu d’am est m/n.
Le théorème suivant est souvent appelé le petit théorème de Fermat (pour le distinguer du dernier théorème de Fermat de la plus célèbre) :
Théorème 10.1. Soit p un nombre premier et soit n un nombre entier. Puis n p ≡ n (mod p).
Preuve. Il y a plusieurs preuves de ce théorème. La plus élémentaire utilise induction sur n et la formule du binôme.
Le théorème est évident pour n = 0 et n = 1.
Pour plus grandes valeurs de n, utiliser la formule du binôme pour écrire
(n + 1) p = n p + p n p-1 + (p(p-1)/2!) n p-2 + (p(p-1)(p-2)/3!) n p-3 + … + 1
Chaque coefficient binomial sauf le premier et le dernier est divisible par p. (c’est le fait que p est un nombre premier est utilisé.) C’est pourquoi (n + 1) p ≡ n p + 1. En outre, n p ≡ n par hypothèse inductive. C’est pourquoi (n + 1) p ≡ n+1
Ce qui prouve le théorème pour tout n positif. Pour n négatif lorsque p ≠ 2, n p = (-1) p (-n) p = (-1)(-n) = n.
Dans le cas particulier p = 2, le théorème affirme que n 2 et n sont les deux même ou les deux impairs, qui est assez évident.
Le théorème est parfois énoncé sous une forme équivalente :
Corollaire 10.2. Soit p un nombre premier et soit n un entier non divisible par p. Puis n p-1 ≡ 1 (mod p).

Comments are closed.