#Logique et Arithmétique
Diapositives de synthèse du module. Les preuves complètes, exemples détaillés et exercices corrigés figurent dans les sections du cours.
#Plan du cours
- Logique propositionnelle et quantificateurs
- Méthodes de preuve
- Ensembles, relations, applications
- Arithmétique des entiers : divisibilité, PGCD, Bézout
- Congruences et cryptographie
#Logique : Connecteurs
| Connecteur | Symbole | Sens |
|---|---|---|
| Négation | Non P | |
| Conjonction | P et Q | |
| Disjonction | P ou Q (inclusif) | |
| Implication | Si P alors Q | |
| Équivalence | P si et seulement si Q |
Équivalences à connaître :
#Quantificateurs
- Universel () : « Pour tout... »
- est vraie si vaut pour tous les éléments ; réfutée par un seul contre-exemple.
- Existentiel () : « Il existe... »
- est prouvée par un témoin explicite ; réfutée en montrant que tous les éléments violent .
Négations :
Attention à l'ordre ! (y dépend de x) n'est pas (un même y pour tous les x).
#Méthodes de preuve
| Méthode | Principe | Quand l'employer |
|---|---|---|
| Direct | de vers | chemin naturel disponible |
| Contraposée | démontrer | négation de la conclusion plus exploitable |
| Absurde | supposer et aboutir à une contradiction | irrationalité, infinité, non-existence |
| Disjonction | traiter tous les cas d'une partition | parité, signe, reste modulo n |
| Récurrence | initialisation + hérédité | propriétés indexées par |
Pièges : l'hérédité sans initialisation ne prouve rien ; la négation d'une implication est une conjonction, jamais une implication.
#Arithmétique : Divisibilité
Soient . On dit que divise (noté ) s'il existe tel que .
Division euclidienne : pour tout et , il existe un unique couple tel que :
Euclide : ; le dernier reste non nul est le PGCD.
Bézout : admet des solutions ; en particulier .
Gauss : et .
#Nombres premiers
Un entier est premier s'il admet exactement deux diviseurs positifs : 1 et lui-même.
Test de primalité : est premier ssi aucun premier ne le divise.
Théorème fondamental de l'arithmétique : tout entier se décompose de manière unique (à l'ordre près) en produit de facteurs premiers :
Euclide : l'ensemble des nombres premiers est infini (preuve par l'absurde avec ).
PGCD et PPCM par factorisation : , , et .
#Congruences et Fermat
- ; compatible avec puissances.
- Inverse modulaire : existe modulo (calcul par Euclide étendu).
- Petit Fermat : premier, ; d'où .
- Euler : , avec .
- Restes chinois : modules deux à deux premiers entre eux solution unique modulo le produit.
- RSA : , , avec .
#Réflexes d'examen
- Nier une proposition : inverser les quantificateurs, nier le prédicat ; une implication niée devient une conjonction.
- Euclide étendu : toujours vérifier numériquement après la remontée.
- Équation : solutions ssi ; forme générale .
- Puissances modulaires : réduire l'exposant modulo (Fermat) ou (Euler), puis carrés successifs.
- Égalité d'ensembles : double inclusion ; propriété d'une relation : vérifier chaque axiome, réfuter par contre-exemple.