- 1 - © 2008 - Gérard Lavau - http://pagesperso-orange.fr/lavau/index.htm Vous
- 1 - © 2008 - Gérard Lavau - http://pagesperso-orange.fr/lavau/index.htm Vous avez toute liberté pour télécharger, imprimer, photocopier ce cours et le diffuser gratuitement. Toute diffusion à titre onéreux ou utilisation commerciale est interdite sans accord de l'auteur. Si vous êtes le gestionnaire d'un site sur Internet, vous avez le droit de créer un lien de votre site vers mon site, à condition que ce lien soit accessible librement et gratuitement. Vous ne pouvez pas télécharger les fichiers de mon site pour les installer sur le vôtre. ENTIERS, DENOMBREMENT ET ARITHMETIQUE PLAN I : Les entiers 1) Le principe de récurrence. 2) Propriétés de . 3) La division euclidienne II : Combinaisons 1) Définition 2) Formules de récurrence 3) Formule du binôme de Newton III : L'anneau 1) Diviseurs communs, PGCD 2) Egalité de Bézout 3) Le théorème de Gauss 4) PPCM 5) Les nombres premiers IV : L'anneau des polynômes [X] 1) Algorithme du calcul du PGCD 2) L'égalité de Bézout 3) Le théorème de Gauss 4) Les polynômes irréductibles 5) PPCM Annexe I : nombre d'injections, de surjections et de partitions Annexe II : les axiomes de Peano Annexe III : analyse non standard Annexe IV : Le numéro INSEE Annexe V: Utilisation d'un corps fini dans le codage du Minitel Annexe VI : Utilisation d'un corps fini dans les disques compacts Annexe VII : Cryptographie Annexe VIII : La recherche des grands nombres premiers, le test de Lucas. Annexe IX : Les nombres parfaits Annexe X : Curiosités étranges 1) Problèmes de la factorisation des entiers 2) Un test probabiliste de primalité 3) Les certificats de primalité 4) Le polynôme de Jones 5) Les fractions de Conway et Guy - 2 - I : Les entiers 1– Le principe de récurrence Voici un extrait d'un livre paru en 1993 (Le langage CAML, Weis et Leroy – InterEditions) : Le principe de récurrence s'énonce informellement ainsi ; si une certaine propriété sur les nombres entiers est vraie pour 0 et si la propriété est vraie pour le successeur d'un nombre dès qu'elle est vraie pour ce nombre, alors cette propriété est vraie pour tous les nombres. Formellement : soit P(n) une propriété qui dépend d'un entier n. Si les phrases suivantes sont vraies : 1. P(0) est vraie, 2. si P(n) est vraie, alors P(n+1) est vraie, alors P(n) est vraie pour tout n. Ce principe est en fait évident : les deux propriétés demandées par le principe de récurrence permettent facilement de démontrer la propriété P pour toute valeur entière. Par exemple, supposons que P vérifie les deux propriétés et qu'on veuille démontrer que P est vraie pour 2. Puisque P est vraie pour 0, elle est vraie pour son successeur 1. Mais puisque P est vraie pour 1, elle est vraie pour son successeur, donc elle est vraie pour 2. Il est clair que ce raisonnement se poursuit sans problème pour tout nombre entier fixé à l'avance. Le principe de récurrence est–il évident, ou peut–il se démontrer ? Le texte suivant est tiré de la revue Tangente de Décembre 87 (n° 2). Il affirme démontrer le principe de récurrence. Or il n'en est rien. Il y a une faille1 dans le raisonnement qui n'échappera pas à un esprit sagace. Premièrement : Le principe de descente infinie de Fermat. Il ne peut exister de suite infinie strictement décroissante d'entiers naturels. Démonstration : si (xn) était une telle suite, on aurait xn+1 < xn pour tout n entier naturel, donc xn+1 ≤ xn – 1. En appliquant ceci à n = 0, 1, 2, ..., on trouve successivement : x1 ≤ x0 – 1, x2 ≤ x1 – 1, etc. On en déduit : x2 ≤ x0 – 2, x3 ≤ x0 – 3, ..., xn ≤ x0 – n. En prenant n = x0 + 1, on obtient xn < –1, ce qui contredit le fait que la suite xn est composée d'entiers naturels. Deuxièmement : Le principe du bon ordre. Tout ensemble non vide X d'entiers naturels comporte un plus petit élément. Démonstration : Si X n'avait pas de plus petit élément, alors pour chaque élément de X, il y en aurait un autre, strictement plus petit. Partant d'un élément donné a appartenant à X, on pourrait fabriquer ainsi une suite strictement décroissante : x0 = a, x1 < x0, x2 < x1, etc, infinie, composée d'éléments de X, ce qui contredit le principe précédent. Troisièmement : Le principe de récurrence. Soit X un ensemble d'entiers naturels contenant 0 qui vérifie la propriété suivante : pour tout x appartenant à X, alors x+1 appartient à X. On peut en conclure que X est l'ensemble de tous les entiers naturels. Démonstration : Si X n'était pas l'ensemble de tous les entiers naturels, soit Y l'ensemble des entiers naturels y non éléments de X. D'après le principe du bon–ordre, cet ensemble Y aurait un plus petit élément y0 qui ne serait pas égal à 0, puisque 0 appartient à X. Donc y0 ≥ 1 et par suite y0 – 1 appartient à . Si y0 – 1 appartient à X, on a de par la propriété de X : (y0 – 1) + 1 appartient à X, soit y0 appartient à X, ce qui est impossible. Si y0 – 1 n'appartient pas à X, on a y0 – 1 dans Y, impossible encore car y0 est le plus petit élément de l'ensemble Y. - 3 - On prendra conscience que le principe de récurrence n'est pas une évidence en soi. Il s'agit d'un axiome qui se révèle indispensable par son utilité. Cependant, Douglas Hofstader, dans son livre Gödel, Escher, Bach (InterEditions 1985) exhibe p.507 un prédicat stupéfiant P(n) tel que : pour tout n, il existe une démonstration de P(n) : P(n) il n'existe pas de démonstration de ∀ n, P(n) : non ∀ n, P(n) En effet, la réunion de toutes les démonstrations P(n) n'est pas une démonstration de ∀ n, P(n), car cette réunion est infinie, or une démonstration se doit d'être finie. En outre, il est possible de rejeter l'axiome de récurrence, débouchant ainsi sur une nouvelle théorie, celle de l'analyse non standard (cf Annexe III) Peano (1858-1932) a posé les axiomes qui régissent . (Un axiome est une propriété servant de base à la construction d'une théorie et dont il est impossible de montrer la véracité ou la fausseté. Ils servent à poser les règles de fonctionnement de l'objet que l'on définit) : Il existe un ensemble noté dont les éléments seront appelés entiers naturels et une fonction appelée successeur définie sur cet ensemble, et vérifiant les axiomes suivants : i) 0 est un entier naturel ii) tout entier naturel possède un successeur iii) Deux entiers naturels ayant le même successeur sont égaux iv) 0 n'est le successeur d'aucun entier naturel v) Si une partie A de contient 0 et si le successeur de tout élément de A appartient à A, alors A est égale à v) est à la base du principe de récurrence. Soit P un prédicat (prenant les valeurs vrai ou faux) portant sur les éléments de : si î î P(0) ∀ n ∈ , P(n) ⇒ P(n+1) alors ∀ n ∈ , P(n) On applique en effet l'axiome v) avec A = {n | P(n)} Le successeur de 0 est 1. Le successeur de n permet de définir la somme de n et de 1. Ces axiomes permettent de définir sur l'addition, le produit, la relation d'ordre, avec toutes leurs propriétés bien connues ... Nous ne nous étendrons pas sur ce sujet et nous admettrons (ce qui est bien connu) que : + est associative. + est commutative. + possède un élément neutre 0. Seul 0 possède un symétrique pour +, lui–même. Ces propriétés font de ( ,+) un monoïde. × est associatif. × est commutatif. × possède un élément neutre, 1, successeur de 0. Seul 1 possède un symétrique pour ×, lui–même. × est distributif par rapport à l'addition. On pourra consulter l'annexe II pour plus de détails. - 4 - est construit de façon que tout les éléments de possède un symétrique pour +. ( , +, ×) est alors un anneau. Cet anneau est commutatif (car le produit est commutatif), unitaire (car le produit admet un neutre), intègre (ce qui signifie que : ab = 0 ⇒ a = 0 ou b = 0). est construit de façon que tout élément non nul possède un inverse pour ×. ( , +, ×) est alors un corps. 2– Propriétés de Les propriétés de ce paragraphe paraîtront évidentes en soi. Une démonstration est cependant donnée, car il s'agit de théorèmes se déduisant des axiomes de Peano, et non d'axiomes supplémentaires. PROPOSITION : Toute partie non vide de possède un plus petit élément Démonstration : uploads/Management/ arithmtq.pdf
Documents similaires
-
44
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Mar 03, 2021
- Catégorie Management
- Langue French
- Taille du fichier 0.2346MB