Kala te souhaite la bienvenueKalaMaths
7

Nombres premiers et petit théorème de Fermat

GRATUIT

Fiche élève

Les énoncés du chapitre, à imprimer ou à travailler à l'écran. Sans compte !

Pour aller plus loin

Réservé aux abonnés : la fiche interactive, le corrigé et la fiche prof.

Fiche interactive

Cours + 2 ateliers manipulables + exos auto-corrigés.

🔒 Réservé aux abonnésEssayer un atelier gratuitementS'abonner pour débloquerou ce chapitre seul, 2,99 €, voir plus bas.

Corrigé

La correction détaillée, avec les rappels utiles.

🔒 Réservé aux abonnésS'abonner pour débloquer

Fiche prof

La version enseignant, pour préparer et animer.

🔒 Réservé aux abonnésS'abonner pour débloquer

Juste besoin de ce chapitre ? Débloquez-le pour 2,99 € : paiement unique, accès à vie (fiche interactive, corrigé, fiche prof et corrigés des exercices).

Avec un code de parrainage, c'est −20 % sur cette première commande.

Débloquer ce chapitre – 2,99 €

Cet achat est réservé à un adulte.

Le chapitre en bref

Ce que tu vas savoir faire

  • Reconnaître un nombre premier et savoir qu'il en existe une infinité (Euclide).
  • Dresser le crible d'Ératosthène et tester la primalité d'un entier en s'arrêtant à n\sqrt{n}.
  • Décomposer un entier en produit de facteurs premiers (existence et unicité).
  • En déduire PGCD, PPCM et le nombre de diviseurs d'un entier.
  • Appliquer le petit théorème de Fermat aux restes de grandes puissances et aux inverses modulaires.
  • Comprendre le principe élémentaire du chiffrement RSA.

Le plan du chapitre

  1. 1Nombres premiers et infinité
  2. 2Le crible d'Ératosthène
  3. 3Décomposition en facteurs premiers
  4. 4Le petit théorème de Fermat
  5. 5Applications : inverses modulaires et RSA

À retenir

  • Un nombre premier a exactement deux diviseurs ; 1 n'est pas premier, 2 est le seul premier pair.
  • Pour tester n, on essaie les premiers p≤np \le \sqrt{n} seulement.
  • Décomposition unique en facteurs premiers (théorème fondamental de l'arithmétique).
  • Nombre de diviseurs = (a1a_{1}+1+1)…(aka_{k}+1+1) ; PGCD = exposants minimaux, PPCM = exposants maximaux ; PGCD×PPCM=a×bPGCD \times PPCM = a \times b.
  • Fermat : p premier, p ∤ a ⇒ ap−1≡1[p]a^{p-1} \equiv 1 [p], et apa^{p} ≡ a [p] pour tout a.
  • Pour une grande puissance modulo p premier : on réduit l'exposant modulo p−1p-1 ; et ap−2a^{p-2} est l'inverse de a modulo p.

Les questions éclair

Qu'est-ce qu'un nombre premier ?

Un entier supérieur ou égal à 2 ayant exactement deux diviseurs : 1 et lui-même.

Jusqu'où tester les diviseurs de n ?

Jusqu'à n\sqrt{n} : il suffit d'essayer les nombres premiers p tels que p≤np \le \sqrt{n}.

Comment trouver le nombre de diviseurs de n ?

On décompose n en facteurs premiers, puis on multiplie les (exposant + 1).

Que dit le petit théorème de Fermat ?

Si p est premier et si p ne divise pas a, alors ap−1≡1[p]a^{p-1} \equiv 1 [p].

Comment calculer ana^{n} modulo p (p premier, p ∤ a) ?

On réduit l'exposant n modulo p−1p-1, puis on calcule ara^{r} [p].

Le sais-tu ?

Le chiffrement RSA, publié en 1977 par Rivest, Shamir et Adleman, protège aujourd'hui d'innombrables communications sécurisées (banques, messageries, sites web). Sa solidité repose entièrement sur une idée de ce chapitre : il est facile de multiplier deux grands nombres premiers, mais extrêmement difficile de factoriser leur produit.