ForHosting KIT · Mathématiques

Résidu puissance n-ième

Indique si un nombre est une puissance k-ième modulo un premier : 2 est un carré modulo 7, car 2 élevé à la puissance 3 laisse un reste de 1. Carrés, cubes et puissances supérieures sont traités avec des entiers exacts. Gratuit dans votre navigateur.

  • Gratuit
  • Fonctionne dans votre navigateur
  • Sans inscription
  • Vos données restent sur votre appareil
Lancer gratuitement Voir l’API
Utilisez-le depuis WebAPIE-mailTelegramApp bientôt

Lancer gratuitement

Exemple résolu

Si vous saisissez
A
2
K
2
Puissance (W)
7
Vous obtenez
A modulo
2
Gcd
2
Ordre du groupe
6
Exposant du critère
3

Un entier a est un résidu de puissance k-ième modulo un premier p lorsqu'il existe un entier x tel que x élevé à k soit congruent à a modulo p. Cette question généralise la residuosité quadratique (le cas k égal à deux) aux cubes, aux puissances supérieures et aux exposants positifs arbitraires utilisés en théorie des nombres de concours et en cryptographie introductive. Cette capacité prend un candidat a, un exposant positif k et un module premier p, réduit a dans l'intervalle de zéro à p moins un, vérifie que p est premier et applique le critère standard du groupe cyclique sur le groupe multiplicatif du corps à p éléments. Lorsque a est divisible par p la réponse est toujours oui pour k au moins un, car zéro à toute puissance positive est zéro.

Ce qu'est un résidu de puissance k-ième modulo un premier

Fixez un module premier p et un entier positif k. Les classes de résidus modulo p forment un corps, et ses éléments non nuls forment un groupe multiplicatif cyclique d'ordre p moins un. Un entier a non divisible par p est un résidu de puissance k-ième modulo p précisément lorsque a appartient à l'image de l'application qui envoie chaque classe non nulle x vers x élevé à k.

Comme le groupe est cyclique, cette image est l'unique sous-groupe d'indice égal au plus grand commun diviseur d de k et de p moins un, et a appartient à ce sous-groupe si et seulement si a élevé à la puissance (p moins un) divisée par d est congruent à un modulo p. Cette unique exponentiation modulaire est la procédure de décision utilisée ici.

Lorsque a est divisible par p, la congruence x à la k congruent à a admet la solution triviale x congruent à zéro pour tout k au moins un, de sorte que zéro est toujours traité comme résidu de puissance k-ième.

Les cas particuliers retrouvent des outils familiers : pour k égal à deux et p premier impair le critère est celui d'Euler pour la residuosité quadratique, la même information que le symbole de Legendre, tandis que pour k égal à p moins un tout a non nul est un résidu par le petit théorème de Fermat.

Le point d'accès n'invente pas de racines en virgule flottante ni de puissances approximatives ; il n'utilise que l'arithmétique modulaire entière exacte afin que les réponses des manuels et les tests automatisés coïncident bit à bit.

Contrat d'entrée, contrôle de primalité et champs de réponse

Envoyez les entiers a, k et p. L'exposant k doit être au moins un et au plus un billion (10^12). Les noms de champs optionnels ne sont jamais remplis avec null : la paire de critère est simplement omise pour le cas résidu zéro.

Contrôles classiques que vous pouvez reproduire à la main : pour a égal à deux, k égal à trois et p égal à sept, le gcd de trois et six est trois, donc l'exposant de critère est deux et deux au carré vaut quatre modulo sept, pas un ; par conséquent deux n'est pas un résidu cubique modulo sept ; en revanche un est toujours un résidu de puissance k-ième pour tout premier car un à toute puissance est un.

Les non-entiers, les champs obligatoires manquants et les exposants inférieurs à un échouent à la validation avec un message clair en anglais.

Où les contrôles de résidus de puissance supérieure interviennent réellement

Les programmeurs de concours ont besoin d'un oracle rapide avant d'extraire des racines cubiques modulaires ou d'ordre supérieur : si le bit de résidu est faux il est inutile de chercher x. Les étudiants en cryptographie vérifient des exercices sur l'image de l'application puissance dans les corps finis, des exemples de calcul d'indice et des constructions pédagogiques qui dépendent de savoir si une classe de message est une puissance k-ième avant d'appliquer une carte.

Les pipelines de recherche et de devoirs qui utilisent déjà les symboles de Legendre ou de Jacobi pour les carrés ont souvent besoin de la même réponse oui ou non pour les cubes et les puissances supérieures sans changer de bibliothèque. Si vous n'avez besoin que de la residuosité quadratique, les outils dédiés résidu quadratique et symbole de Legendre restent disponibles ; cette page est la décision générale de puissance k-ième pour les modules premiers.

Cas d’usage

Contrôles de devoirs et de concours

Décidez si a est une puissance k-ième modulo le premier p pour des exercices de théorie des nombres sans écrire votre propre pipeline d'exponentiation modulaire et de gcd.

Préfiltre avant extraction de racines

Rejetez les non-résidus tôt dans un pipeline qui tenterait autrement des algorithmes de racine cubique ou d'ordre supérieur sur un corps premier.

Enseigner le critère du groupe cyclique

Montrez aux élèves gcd(k, p−1), l'exposant de critère et la puissance modulaire qui prouve ou infirme la residuosité pour des triplets concrets.

Questions fréquentes

Qu'est-ce qu'un résidu de puissance k-ième modulo un premier p ?

Un entier a est un résidu de puissance k-ième modulo le premier p s'il existe un entier x tel que x^k ≡ a (mod p). Cet outil rapporte ce fait via le critère du groupe cyclique sur F_p*.

Pourquoi p doit-il être premier ?

La procédure de décision s'appuie sur le fait que le groupe multiplicatif modulo p est cyclique d'ordre p−1, ce qui vaut pour les modules premiers.

Comment la réponse oui ou non est-elle calculée ?

Soit d = gcd(k, p−1). Si a n'est pas divisible par p, a est un résidu de puissance k-ième si et seulement si a^((p−1)/d) ≡ 1 (mod p).

Quel est le coût ?

L'outil navigateur est gratuit et s'exécute en local.

2 est-il un résidu cubique modulo 7 ?

Non. Le plus grand commun diviseur de 3 et 6 vaut 3, donc le test élève 2 à la puissance 2, ce qui donne 4 modulo 7 au lieu de 1. Aucun entier au cube ne laisse donc un reste de 2.

Outils associés

Vérificateur de résidu quadratiqueMathématiquesNon-résidus quadratiques mod pMathématiquesRacine n-ième modulaireMathématiquesCalculateur de racine primitiveMathématiquesPuissance moduloMathématiquesPetit théorème de FermatMathématiquesCalculatrice d'inverse moduloMathématiquesSymbole de Legendre (a/p)Mathématiques

Pour les développeurs — accès API

Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.

Endpoint

POSThttps://api.kit.forhosting.com/numth/power-residue-check

Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.

Appeler depuis votre stack

curl -X POST https://api.kit.forhosting.com/numth/power-residue-check \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"k":3,"p":7}'

Exemple de requête

{
  "a": 2,
  "k": 3,
  "p": 7
}

Exemple de réponse

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.power_residue_check",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.

Tarifs

par requête$0.002

Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.

Erreurs

HTTPCodeSignification
401unauthorizedClé API absente ou invalide : vérifiez l’en-tête Authorization.
402insufficient_balanceSolde insuffisant : rechargez votre compte pour lancer cette tâche.
404unknown_typeType de tâche inconnu : vérifiez le champ type de votre requête.
429rate_limitedTrop de requêtes : ralentissez la cadence, puis réessayez.

Notes techniques

Contrat d'entrée, contrôle de primalité et champs de réponse

Le module p doit être un premier entre deux et un billion inclus ; les valeurs composées telles que neuf ou quinze sont rejetées avec invalid_input et un message qui nomme le champ et indique que p n'est pas premier, de sorte que ces appels ne sont pas facturés. Le candidat a peut être négatif ou plus grand que p en valeur absolue jusqu'à la même borne d'un billion ; il est réduit à a_mod dans l'intervalle semi-ouvert de zéro inclus à p exclu avant le test. En cas de succès la charge utile inclut toujours a, k, p, a_mod, le booléen is_power_residue, le gcd de k et de p moins un, le group_order égal à p moins un et une courte chaîne d'interprétation en anglais. Lorsque a_mod est non nul la charge rapporte aussi criterion_exp égal à (p moins un) divisé par ce gcd et criterion_value égal à a_mod élevé à cet exposant modulo p, qui vaut un exactement lorsque le bit de résidu est vrai. La même fonction pure alimente l'outil gratuit du navigateur et le chemin API payant.

Où les contrôles de résidus de puissance supérieure interviennent réellement

Les enseignants posent des problèmes tels que décider si trois est un résidu de cinquième puissance modulo onze ou lister les classes qui sont des cubes modulo treize et veulent une réponse JSON déterministe plutôt qu'un tableau manuscrit susceptible d'omettre une classe. Comme la capacité est un moteur parse pur il n'y a ni dérive de modèle, ni clé API externe, ni état stocké : le même triplet produit toujours le même booléen et la même valeur de critère. Le tarif API est la base publiée de $0.002 par élément réussi ; une validation échouée ne consomme pas de solde.

Questions techniques

0 est-il considéré comme résidu de puissance k-ième ?

Oui. Pour tout k ≥ 1 on a 0^k ≡ 0 (mod p), donc a_mod = 0 est toujours un résidu de puissance et les champs d'exposant de critère sont omis.

Consulter la documentation complète du KIT →