petit théorème de Fermat

petit théorème de Fermat (répertoire)

voir le cours du CNED : maths spécialité
pour le petit théorème de Fermat :
On trouve des démonstrations niveau terminale sur internet, mais ce n'est pas au programme de la terminale.
La base de la démonstration est que les nombres (k p) (avec 0 ≤ k ≤ p−1) engendrent tout Z/pZ quand p est premier.
Démonstration de wikipédia :
- Nous supposons que a n'est pas divisible par p
- N = a.2a.3a. . . . .(p − 1)a
  En réordonnant les facteurs : N = 1.2. . . . .(p−1).a^p−1 = (p − 1)! a^p−1
- Soit r_k = reste de la division euclidienne de ka par p, pour tout entier k de 1 à (p − 1).
  ka ≡ r_k [p]
  N ≡ r₁.r₂. . . . .r_p−1 (mod p).
  Si dans un produit on remplace un facteur par un entier qui lui est congru modulo p alors le nouveau produit est congru modulo p à l'ancien.
  En remplaçant dans N, un par un, chaque ka par r_k, le résultat est donc congru à N modulo p.
- Or r₁.r₂. . . . .r_p−1 = (p − 1)!
  car (r₁, r₂, . . . , r_p−1) est une permutation de (1, 2, . . . , p−1)
  - Par définition du reste : 0 ≤ r_k ≤ p − 1
  - aucun r_k n'est nul, car aucun ka n'est pas divisible par p :
    - p ne divise pas a
    - 1 ≤ k ≤ p−1 ne peut pas être divisible par p
  - les r_k sont distincts deux à deux,
    - car si r_i = r_j alors (i − j)a est divisible par p, impossible comme pour ka
- Des points précédents on déduit : N = (p − 1)! a^p−1 ≡ (p − 1)! (mod p),
  autrement dit (p − 1)! (a^p−1 − 1) est divisible par p.
  - p ne peut divier aucun facteur de (p − 1)!
  - donc p divise (a^p−1 − 1)

Exercice préliminaire : avec 2 amphores de x et y litres, et autant d'eau que l'on veut,
si x et y sont premiers entre eux, on peut créer exactement 1 litre (ou toute autre valeur ≤ x+y)
( 1 litre → cela rappelle le théorème de Bézout )

exemple : 2 amphores d'exactement 4 L et 7 L
On note : [ contenu de 4 | contenu de 7 ]
on remplit 4, on le verse dans 7,
on remplit 4, on complète 7, il reste 1 litre dans 4 (terminé) (on a obtenu 1)

Algorithme produisant 4 k modulo 7

si plein : on vide 7	si vide : on remplit 4	on verse 4 dans 7	on a obtenu
[ 0 \| 0 ]	[ 4 \| 0 ]	[ 0 \| 4 ]	4
	[ 4 \| 4 ]	[ 1 \| 7 ]	8
[ 1 \| 0 ]		[ 0 \| 1 ]	1
	[ 4 \| 1 ]	[ 0 \| 5 ]	5
	[ 4 \| 5 ]	[ 2 \| 7 ]	9
[ 2 \| 0 ]		[ 0 \| 2 ]	2
	[ 4 \| 2 ]	[ 0 \| 6 ]	6
	[ 4 \| 6 ]	[ 3 \| 7 ]	10
[ 3 \| 0 ]		[ 0 \| 3 ]	3
	[ 4 \| 3 ]	[ 0 \| 7 ]	7
[ 0 \| 0 ]			0

Algorithme produisant 7 k modulo 4

si plein : on vide 4	si vide : on remplit 7	on verse 7 dans 4	on a obtenu
[ 0 \| 0 ]	[ 0 \| 7 ]	[ 4 \| 3 ]	7
[ 0 \| 3 ]		[ 3 \| 0 ]	3
	[ 3 \| 7 ]	[ 4 \| 6 ]	10
[ 0 \| 6 ]		[ 4 \| 2 ]	6
[ 0 \| 2 ]		[ 2 \| 0 ]	2
	[ 2 \| 7 ]	[ 4 \| 5 ]	9
[ 0 \| 5 ]		[ 4 \| 1 ]	5
[ 0 \| 1 ]		[ 1 \| 0 ]	1
	[ 1 \| 7 ]	[ 4 \| 4 ]	8
[ 0 \| 4 ]		[ 4 \| 0 ]	4
[ 0 \| 0 ]			0

On a obtenu la même séquence de nombres que 4 k modulo 7, mais dans l'ordre inverse.
⇒ pour faire 3 L, il vaut mieux commencer par remplir 7

Maintenant, vérification expérimentale du petit théorème de Fermat :

énoncé : a^p−1 ≡ 1 mod p (pour a ≢ 0 [p])
On imprime la suite {a¹, a², . . . , aⁿ⁻¹, aⁿ} dans Z / nZ (Z modulo n)
d'abord quand n n'est pas premier :
n = 6 (il y a 2 diviseurs de 0 : 2 × 3 ≡ 0 [6])
```
(Z / 6Z) a^k mod 6 (pour k = 1 à 6) : première colone = a
 0  0  0  0  0  0	0^k ≡ 0 [6]
 1  1  1  1  1  1	1^k ≡ 1 [6]
 2  4  2  4  2  4	2^k engendre {2, 4}
 3  3  3  3  3  3	3^k ≡ 3 [6]
 4  4  4  4  4  4	4^k ≡ 4 [6]
 5  1  5  1  5  1	5^k engendre {1, 5}
```
aⁿ⁻¹ ≢ 1
et même : aⁿ⁻¹ ≡ a (est-ce un hasard ? c'est vrai pour 6, 10, 14, 22, 26, 30, 34, . . .)
Exercice : démontrer que aⁿ⁻¹ ≡ a [n] pour n = 2 p (avec p premier ≠ 2)

n = 10 (il y a 2 diviseurs de 0 : 2 × 5 ≡ 0 [10])

(Z / 10Z) a^k mod 10 (pour k = 1 à 10) : première colone = a
 0  0  0  0  0  0  0  0  0  0	0^k ≡ 0 [10]
 1  1  1  1  1  1  1  1  1  1	1^k ≡ 1 [10]
 2  4  8  6  2  4  8  6  2  4	2^k engendre {2, 4, 6, 8}
 3  9  7  1  3  9  7  1  3  9	3^k engendre {1, 3, 7, 9}
 4  6  4  6  4  6  4  6  4  6	4^k engendre {4, 6}
 5  5  5  5  5  5  5  5  5  5	5^k ≡ 5 [10]
 6  6  6  6  6  6  6  6  6  6	6^k ≡ 6 [10]
 7  9  3  1  7  9  3  1  7  9	7^k engendre {1, 3, 7, 9}
 8  4  2  6  8  4  2  6  8  4	8^k engendre {2, 4, 6, 8}
 9  1  9  1  9  1  9  1  9  1	9^k engendre {1, 9}

aⁿ⁻¹ ≢ 1

maintenant, avec n = p, nombre premier
n = 7

(Z / 7Z) a^k mod 7 (pour k = 1 à 7) : première colone = a
 0  0  0  0  0  0  0	0^k ≡ 0 [7]
 1  1  1  1  1  1  1	1^k ≡ 1 [7]
 2  4  1  2  4  1  2	2^k engendre {1, 2, 4}
 3  2  6  4  5  1  3	3^k engendre (Z / 7Z) → 3 est un générateur de (Z / 7Z)
 4  2  1  4  2  1  4	4^k engendre {1, 2, 4}
 5  4  6  2  3  1  5	5^k engendre (Z / 7Z) → 5 est un générateur de (Z / 7Z)
 6  1  6  1  6  1  6	6^k engendre {1, 6}

On constate que pour p = 7 : a^p−1 ≡ 1 [p]
remarque : (Z / 7Z) possède 2 générateurs : {3, 5}
pour les autres nombres a, on trouve 1 avant la fin (k = p−1) : la suite n'engendrera plus de nouveaux nombres.
je me demande quelle est la condition pour qu'un élément unique soit générateur ?

n = 11

(Z / 11Z) a^k mod 11 (pour k = 1 à 11) : première colone = a
 0  0  0  0  0  0  0  0  0  0  0	0^k ≡ 0 [11]
 1  1  1  1  1  1  1  1  1  1  1	1^k ≡ 1 [11]
 2  4  8  5 10  9  7  3  6  1  2	2^k engendre (Z / 11Z) → 2 est un générateur de (Z / 11Z)
 3  9  5  4  1  3  9  5  4  1  3	3^k engendre {1, 3, 4, 5, 9}
 4  5  9  3  1  4  5  9  3  1  4	4^k engendre {1, 3, 4, 5, 9}
 5  3  4  9  1  5  3  4  9  1  5	5^k engendre {1, 3, 4, 5, 9}
 6  3  7  9 10  5  8  4  2  1  6	6^k engendre (Z / 11Z) → 6 est un générateur de (Z / 11Z)
 7  5  2  3 10  4  6  9  8  1  7	7^k engendre (Z / 11Z) → 7 est un générateur de (Z / 11Z)
 8  9  6  4 10  3  2  5  7  1  8	8^k engendre (Z / 11Z) → 8 est un générateur de (Z / 11Z)
 9  4  3  5  1  9  4  3  5  1  9	9^k engendre {1, 3, 4, 5, 9}
10  1 10  1 10  1 10  1 10  1 10	10^k engendre {1, 10}

On constate que pour p = 11 : a^p−1 ≡ 1 [p]
remarque : (Z / 11Z) possède 4 générateurs : {2, 6, 7, 8}

n = 13

(Z / 13Z) a^k mod 13 (pour k = 1 à 13) : première colone = a
 0  0  0  0  0  0  0  0  0  0  0  0  0		0^k ≡ 0 [11]
 1  1  1  1  1  1  1  1  1  1  1  1  1		1^k ≡ 1 [11]
 2  4  8  3  6 12 11  9  5 10  7  1  2		2^k engendre (Z / 13Z) → 2 est un générateur de (Z / 13Z)
 3  9  1  3  9  1  3  9  1  3  9  1  3		3^k engendre {1, 3, 9}
 4  3 12  9 10  1  4  3 12  9 10  1  4		4^k engendre {1, 3, 4, 9, 10, 12}
 5 12  8  1  5 12  8  1  5 12  8  1  5		5^k engendre {1, 5, 8, 12}
 6 10  8  9  2 12  7  3  5  4 11  1  6		6^k engendre (Z / 13Z) → 6 est un générateur de (Z / 13Z)
 7 10  5  9 11 12  6  3  8  4  2  1  7		7^k engendre (Z / 13Z) → 7 est un générateur de (Z / 13Z)
 8 12  5  1  8 12  5  1  8 12  5  1  8		8^k engendre {1, 5, 8, 12}
 9  3  1  9  3  1  9  3  1  9  3  1  9		9^k engendre {1, 3, 9}
10  9 12  3  4  1 10  9 12  3  4  1 10		10^k engendre {1, 3, 4, 9, 10, 12}
11  4  5  3  7 12  2  9  8 10  6  1 11		11^k engendre (Z / 13Z) → 11 est un générateur de (Z / 13Z)
12  1 12  1 12  1 12  1 12  1 12  1 12		12^k engendre {1, 12}

On constate que pour p = 13 : a^p−1 ≡ 1 [p]
remarque : (Z / 13Z) possède 4 générateurs : {2, 6, 7, 11}

Applications : divisibilité d'expressions de n
- rappels :
  - q divise n ⇔ n ≡ 0 [q] ⇔ ∃ k ∈ Z : n = q k
    le petit théorème de Fermat démontre la divisibilité de (n^p−1 − 1) par p (si n ≢ 0 [p])
    ou encore : n (n^p−1 − 1) = (n^p − n) divisible par p ∀ n
    - ou bien p divise n
    - ou bien p divise (n^p−1 − 1) si p ne divise pas n
  - x ≡ y [n] ⇒ x^k ≡ y^k [n]
    n^p−1 ≡ 1 [p] ⇒ (n^p−1)^x ≡ 1^x [p]
    n^x(p−1) ≡ 1 [p]
  - Il y a aussi la démonstration par récurrence.
- démontrer que x divise N :
  - décomposer x en facteurs premiers. (exemple : 42 = 2 × 3 × 7)
  - Appliquer le petit théorème de Fermat à chaque facteur :
    - (n² − n) est divisible par 2
      n² ≡ n [2] ⇔ n³ ≡ n² ≡ n [2] . . .
      n^k ≡ n [2] donc (n^k − n) = n (n^k−1 − 1) est divisible par 2
      remarque : n ou (n^k−1 − 1) est pair, l'autre impair
    - (n³ − n) est divisible par 3
      n³ ≡ n [3] ⇒ n (n² − 1) est divisible par 3
      si n ≢ 0 [3] : n^2k ≡ 1 [3] ⇒ (n^2k − 1) est divisible par 3
      n (n^2k − 1) est divisible par 3
      ou bien n ≡ 0 [3] : 3 divise n
      ou bien n ≢ 0 [3] : 3 divise (n^2k − 1)
- liens obtenus par google (petit theoreme de fermat applications) :
  unisciel (classique)
  lesbonsprofs (difficile)
  . . .

retour aux menus : cours 2015 math TS math

si plein : on vide 7	si vide : on remplit 4	on verse 4 dans 7	on a obtenu
[ 0 \| 0 ]	[ 4 \| 0 ]	[ 0 \| 4 ]	4
	[ 4 \| 4 ]	[ 1 \| 7 ]	8
[ 1 \| 0 ]		[ 0 \| 1 ]	1
	[ 4 \| 1 ]	[ 0 \| 5 ]	5
	[ 4 \| 5 ]	[ 2 \| 7 ]	9
[ 2 \| 0 ]		[ 0 \| 2 ]	2
	[ 4 \| 2 ]	[ 0 \| 6 ]	6
	[ 4 \| 6 ]	[ 3 \| 7 ]	10
[ 3 \| 0 ]		[ 0 \| 3 ]	3
	[ 4 \| 3 ]	[ 0 \| 7 ]	7
[ 0 \| 0 ]			0

si plein : on vide 4	si vide : on remplit 7	on verse 7 dans 4	on a obtenu
[ 0 \| 0 ]	[ 0 \| 7 ]	[ 4 \| 3 ]	7
[ 0 \| 3 ]		[ 3 \| 0 ]	3
	[ 3 \| 7 ]	[ 4 \| 6 ]	10
[ 0 \| 6 ]		[ 4 \| 2 ]	6
[ 0 \| 2 ]		[ 2 \| 0 ]	2
	[ 2 \| 7 ]	[ 4 \| 5 ]	9
[ 0 \| 5 ]		[ 4 \| 1 ]	5
[ 0 \| 1 ]		[ 1 \| 0 ]	1
	[ 1 \| 7 ]	[ 4 \| 4 ]	8
[ 0 \| 4 ]		[ 4 \| 0 ]	4
[ 0 \| 0 ]			0