Arithmétique (ARI)

January 1, 2023

Attention - Je n’enseigne plus ce cours depuis la rentrée 2023. Cette page n’est donc pas à jour, elle peut servir d’archive (en particulier pour les vidéos !).

Les nombres entiers nous semblent familiers, pourtant ils recèlent bien des mystères. Depuis longtemps ils ont été utilisés pour crypter des messages. Le cours fournira une base mathématique solide des concepts fondamentaux d’arithmétique, permettant (par exemple) de comprendre le fameux cryptage RSA: nombres premiers, congruences, etc. Mais aussi de démontrer pourquoi 1+1=2 (!). Le cours sera illustré par des programmes simples sur ordinateur (python).

Vidéos des cours

Tout le cours a été réalisé et filmé devant un amphi vide (!) pendant la période Covid en 2021… Vous avez maintenant accès à ces vidéos !

Chaîne vidéo Arithmétique

Cours 1:
- Partie 1 Introduction.
- Partie 2 Plan du cours. Entiers.
- Partie 3 (I) Construction des entiers naturels; méthode de Péano (avec Python).
- Partie 4 L’ensemble (infini !) de tous les entiers N. Principe de récurrence.
- Partie 5 Addition et multiplication.
Cours 2:
- Partie 1 Propriétés des opérations. Relation d’ordre.
- Partie 2 Ensembles finis et infinis. N est infini.
- Partie 3 Les entiers sur Python (et autres langages informatiques).
- Partie 4 Les entiers relatifs.
- Partie 5 (II) La division euclidienne: divisibilité.
Cours 3:
- Partie 1 division euclidienne.
- Partie 2 division euclidienne: fin de la preuve et exemples.
- Partie 3 division euclidienne: algorithmes en Python.
- Partie 4 Écriture en base b.
- Partie 5 Critères de divisibilité.
- Partie 6 PGCD, algorithme d’Euclide.
Cours 4:
- Partie 1 (reprise ?) algorithme d’Euclide + version Python.
- Partie 2 PGCD: expérimentations sur ordinateur et graphiques.
- Partie 3 Le cas de la suite de Fibonacci. Complexité de l’algorithme d’Euclide.
Cours 5:
- Partie 1 (III) Le théorème de Bézout.
- Partie 2 Bézout: combinaisons linéaires à coefficients entiers. Méthode de calcul des coefficients par Euclide “étendu”.
- Partie 3 Méthode itérative pour les coefficients de Bézout.
- Partie 4 Bézout: implémentation en Python.
Cours 6:
- Partie 1 Nombres premiers entre eux. Théorème de Bachet-Bézout.
- Partie 2 Lemme de Gauss. Équations linéaires à coefficients entiers. Théorème de Fermat: Star Trek !
- Partie 3 ax + by = c. Méthode de résolution.
- Partie 4 (IV) Nombres premiers. Un ensemble infini.
Cours 7
- Partie 1 Crible d’Ératosthène
- Partie 2 Lemme d’Euclide. Décomposition en facteurs premiers.
- Partie 3 (V) Congruence modulo n.
- Partie 4 Addition et multiplication des classes de congruences. Exemples.
- Partie 5 Inverse modulp n. Petit théorème de Fermat. Théorème d’Euler.
Cours 8:
- Partie 1 (VI) Cryptage RSA. Histoire du cryptage au cours des siècles.
- Partie 2 Histoire de Marie Stuart (reine d’Ecosse). Vigénère, la machine Enigma. Alan Turing.
- Partie 3 Cryptographie à clef publique. Chiffrement RSA.
- Partie 4 Lemme de (dé)chiffrement RSA.

Références

Le cours est librement basé sur deux références:

référence minimale: en quelques pages, l’essentiel ! (sauf le cryptage RSA): http://exo7.emath.fr/cours/livre-algebre-1.pdf (chapitre 4). N’hésitez pas à visiter le reste du site http://exo7.emath.fr.
référence approfondie: https://perso.univ-rennes1.fr/christophe.mourougane/enseignements/2014-15/AR1/poly-test.pdf Il s’agit du poly de l’ancien cours “Algèbre et Arithmétique” de l’université de Rennes 1.

Programmation

Les illustrations du cours seront effectuées dans le language informatique python (version 3). Les codes des séances précédentes sont disponibles sur la page Teams sous forme de notebooks jupyter.

On peut également les exécuter en ligne (et même les modifier !) grâce au lien mybinder: .

Si mybinder ne fonctionne pas, il est aussi facile de tester le code directement en ligne sur internet (de nombreux sites existent, par exemple https://www.tutorialspoint.com/execute_python_online.php ). Pour installer python sur son ordinateur, voir https://www.python.org/shell/ .

ARI01.html (17/01/2023)
ARI02-Division.html (19/01/2021)
ARI03-Bases.html (31/01/2023)
ARI04-Euclide.html (07/02/2023)
ARI04-Fib.html (07/02/2023)
ARI05-Bezout.html (14/02/2023)

Feuilles de TD

Les TD sont assurés par Pierre Houedry, Fabien Narbonne et moi-même. Les exercices à préparer à l’avance seront indiqués lors du cours ou des séances de TD précédentes.

La participation active en TD est fortement conseillée ! Non seulement c’est ainsi que vous apprendrez plus vite, mais elle peut aussi vous gratifier d’un point supplémentaire sur votre note finale (à l’appréciation de l’enseignant de TD).

Informations et contacts: page Teams

Des infos importantes, documents, vidéos de cours, ou autres seront publiés sur la page Teams du cours qui sera indiquée en début de cours. Vous devez absolument y être inscrits et la vérifier régulièrement.

Merci d’utiliser également Teams pour contacter les enseignants.

Contrôles

QCM1, 30min: coefficient 1/4 (note $Q_1$) 06-02-2023
CC, 1h: coefficient 1/2 (note $C_0$) 28-02-2023
QCM2, 30min: coefficient 1/4 (note $Q_2$) 20-03-2023
Examen ’terminal’, 2h: coefficient 1 (note $T$)

La note finale est $\max(T, \frac{T+C}2)$ où $C=Q_1/4+C_0/2+Q_2/4$.

Les cases cochées des QCM sont toutes détectées automatiquement, après scan des copies. Seul l’intérieur des cases comptes (il ne sert donc à rien de les entourer !). Elles doivent donc être fortement cochées ou remplies en noir pour que l’algorithme de détection fasse la différence avec des taches accidentelles du papier.

Le crayon à papier est à proscrire, il ne passe pas bien au scanner.
La couleur bleue (à part très foncée) est à éviter également. En cas de nécessité, la case doit être remplie (une croix est insuffisante).

L’enseignant pourra refuser toute demande de rectification due à des cases mal cochées. Voici quelques exemples:

Cases bien cochées:
- OK:
- OK:
- OK:
Cases mal cochées:
- NON:
- NON:

Équipe pédagogique

Enseignant responsable : San Vũ Ngọc
Groupes de TD : Pierre Houedry, Fabien Narbonne et San Vũ Ngọc
Secrétariat : Sébastien Debroize (ISTIC). En particulier, c’est à M. Debroize que vous devez envoyer tous vos justificatifs d’absence.
Ce cours fait partie du cursus L2 informatique

Vidéo

Applications de l’arithmétique à la quadrature du cercle!