En 1640, Pierre de Fermat écrit dans une lettre à un ami.

Si pest un nombre premier et aest un entier non divisible par p, alors aᵖ⁻¹ − 1est divisible par p.

Contrairement à la plupart des choses que je dis à mes amis, Fermat avait raison. Fermat ne l'a cependant jamais prouvé. Il a laissé le travail à Leonhard Euler, connu ici comme la personne la plus occupée de toute l'histoire des mathématiques. En 1736, Euler montra que Fermat avait raison et continua également à étendre la revendication.

Le petit théorème de Fermat

Fermat avait de plus gros poissons à faire frire, c'était donc son petit théorème. Il stipule que pour tout nombre premier pet entier aqui est premier avec p: aᵖ⁻¹ % p = 1.

Pourquoi Fermat avait-il raison ?

La liste des nombres a, 2a, 3a, ..., (p-1)asont tous premiers avec p, car pest premier. Si nous mod pchacun de ces nombres, nous sommes assurés de produire une liste de tous les nombres entre 1& p-1. C'est parce qu'il y aura p - 1des résultats distincts. Nous pouvons prouver qu'ils seront distincts.

> if `k` & `m` are two values between `1` & `p - 1`
> to prove they are NOT distinct we would want to find
ka ≡ ma (mod p)
> because of the cancellation rule
k ≡ m (mod p)
> because `k` & `m` were defined as being less than `p`
k = m

Nous avons donc montré qu'étant donné la liste a, 2a, 3a, ..., (p-1)a (mod p), nous obtiendrions l'ensemble complet des nombres 1 -> p - 1. Ordonner ces résultats nous donnerait l'ensemble : 1, 2, ..., p-1.

Un exemple pourrait rendre les choses plus claires :

p = 7, a = 3
> a, 2a, 3a, ..., (p-1)a
1(3), 2(3), 3(3), 4(3), 5(3), 6(3)
3, 6, 9, 12, 15, 18
> all `mod p`
3, 6, 2, 5, 1, 4
> ordering the results
1, 2, 3, 4, 5, 6

> we know that
a, 2a, ..., (p-1)a ≡ 1, 2, ..., p-1 (mod p)
> multiplying all elements
a x 2a x ... x (p-1)a ≡ 1 x 2 x ... x (p-1) (mod p)
> simplifies
aᵖ⁻¹(p-1)! ≡ (p-1)! (mod p)
> cancel `(p-1)!`
> giving us
aᵖ⁻¹ ≡ 1 (mod p)

Théorème d'Euler

Après avoir prouvé le petit théorème de Fermat, Euler décide de continuer. Il a pu montrer que pour deux entiers premiers entre eux, aucun n'est nécessairement premier entre eux : aᵠ⁽ⁿ⁾ ≡ 1 (mod n). fait référence à la fonction Totient d'Euler, que nous avons explorée précédemment . La fonction Totient de tout entier n, renvoie le nombre de ncoprimes inférieur à n.

Contrairement au petit théorème de Fermat, l'extension d'Euler a supprimé la nécessité pour le module d'être un nombre premier. Heureusement, nous avons déjà fait la plupart du travail pour le prouver.

Rappelez-vous comment, avec le petit théorème de Fermat, tous ales multiples de (mod p), donnaient les nombres 1 -> p-1. Cette liste de nombres, 1 -> p-1étaient ples premiers entre eux, étant donné que pc'est premier. Dans ce cas, le module nn'est pas premier, mais la liste des ncoprimes de multipliée par a, tous (mod n), produit toujours nles coprimes de . Par example

> remembering that
(n) = Number of n's coprimes
n = 10
> n's coprimes
1, 3, 7, 9
a x 3a x 7a x 9a ≡ 1 x 3 x 7 x 9 (mod n)
> where n = 10, this gives us the number of "a" factors
aᵠ⁽¹⁰⁾
aᵠ⁽¹⁰⁾ x (1 x 3 x 7 x 9) ≡ (1 x 3 x 7 x 9) (mod n)
> cancel the coprime multiplication
aᵠ⁽¹⁰⁾ ≡ 1 (mod n)

Le petit théorème de Fermat et le théorème d'Euler sont très importants pour la théorie des nombres. Ils aident à résoudre des cas de la fonction Carmichael, que nous avons couverts en profondeur . Ils sont également intéressants isolément, comme exemple d'utilisation de la fonction Totient d'Euler.

Et tout a commencé par une lettre à un ami il y a près de 400 ans.

Suite ?

J'écris la newsletter la plus courte du monde. Une chose rapide que j'ai apprise ou vue ou lue dans la semaine, chaque mercredi.

Je veux que ce soit la newsletter la plus accessible et la plus pertinente que vous receviez.

Cela vaut peut-être la peine d'essayer. La désinscription est également facile.

Cela s'appelle . On se voit là-bas!