Petit théorème de Fermat

Le petit théorème de Fermat affirme que, si p est premier et si a est un entier non divisible par p, alors a élevé à p moins un est congruent à un modulo p. Cette identité sous-tend les tests de primalité de Fermat, les inverses dans un corps premier et les problèmes de concours qui demandent de réduire une énorme puissance sans la développer. Ce calculateur prend une base a et un module premier p, vérifie que p est bien premier, puis renvoie le résidu exact de a à la p moins un modulo p par exponentiation modulaire BigInt déterministe. Lorsque a et p sont premiers entre eux le résidu vaut un, ce qui est le théorème ; lorsque p divise a le résidu vaut zéro.

Ce que dit le petit théorème de Fermat et ce que signifie le résidu

Le petit théorème de Fermat dit que si p est un nombre premier et si a est un entier qui n'est pas un multiple de p, alors a élevé à p moins un est congruent à un modulo p. En symboles, a à la p moins un congruent à un mod p. Une forme équivalente, valable même lorsque p divise a, est a à la p congruent à a modulo p.

La première forme est celle que cette capacité évalue : elle calcule le résidu de a à la p moins un modulo p et le renvoie comme résultat principal. Lorsque a et p sont premiers entre eux le résidu est toujours un, ce qui est le théorème ; c'est la vérification que les élèves écrivent dans les devoirs et l'identité utilisée pour inverser a modulo p en élevant a à la p moins deux.

Lorsque p divise a la puissance s'effondre à zéro modulo p, car toute puissance positive d'un multiple de p reste un multiple de p, de sorte que le résidu vaut zéro et le drapeau coprime est faux. Les bases négatives sont acceptées et réduites dans l'intervalle de zéro à p moins un avant la puissance, ce qui maintient le reste non négatif et correspond à la convention usuelle de cours en arithmétique modulaire.

Contrat d'entrée, algorithme et comportement d'erreur

Les valeurs absolues sont bornées par la limite des entiers sûrs JavaScript afin que chaque produit modulaire intermédiaire reste exact sous BigInt. Après l'analyse, le gestionnaire teste que p est premier par division d'essai pour les valeurs modestes et un ensemble déterministe de bases Miller–Rabin pour les grands entiers sûrs. Si p est composé, égal à un, zéro ou négatif, la requête échoue avec un message qui nomme prime et indique que la valeur n'est pas première ; ces échecs ne sont pas facturés.

Exemple : base deux et premier sept donne le résidu un, car deux à la sixième vaut soixante-quatre et soixante-quatre moins neuf fois sept vaut un. Exemple : base dix et premier cinq donne le résidu zéro, car cinq divise dix. Associez la réponse à vos propres notes si vous avez besoin d'une preuve rédigée ; ce point de terminaison renvoie le résidu et les drapeaux, non une dérivation pas à pas en prose.

Où cette vérification rend service

Les cours de théorie des nombres et les plateformes de concours utilisent un calculateur du petit théorème de Fermat pour que les apprenants confirment a à la p moins un modulo p sans implémenter à la main l'exponentiation modulaire et sans confondre un composé menteur de Fermat avec un premier.

Les carnets de recherche et les scripts récréatifs appellent le même contrat lorsqu'ils veulent un oracle indépendant pour un exemple publié : deux à la sixième modulo sept doit valoir un, trois à la quatrième modulo cinq doit valoir un, et un module composé tel que neuf doit être rejeté plutôt que réduit.

Les ateliers de cryptographie qui présentent les tests de primalité de Fermat ou les inverses dans un corps premier ont besoin d'un outil qui refuse un module composé, car le point pédagogique est l'hypothèse du théorème, non une puissance modulaire silencieuse qui aurait l'air plausible. Une validation échouée ne consomme pas de solde. Traitez une erreur de non-premier comme un résultat de premier plan dans votre suite : c'est le contrat qui empêche un menteur de Fermat d'être noté comme une réussite.