Référence mathématique
Rechercher des entiers, des nombres premiers, l'arithmétique modulaire, les générateurs de groupes cycliques, les résidus quadratiques, les équations diophantiennes et le RSA avec des formules et des exemples résolus.
Les puissances successives de 3 visitent chaque résidu non nul avant de revenir à 1.
L'élévation au carré des résidus non nuls produit uniquement 1, 2 et 4.
55 termes
Entiers et fondements
Integer
ℤUn nombre entier qui peut être négatif, nul ou positif.
Utilisez les entiers pour compter avec une direction, des index, des différences et des calculs discrets exacts.
-4, 0 et 27 sont des entiers.Entiers et fondements
Natural number
ℕUn nombre entier ; l'inclusion du zéro dépend de la convention utilisée.
Indiquer la convention avant d'utiliser les nombres naturels dans une preuve, une spécification ou un programme.
Certains livres définissent les nombres naturels comme commençant à 1, vérifiez donc toujours la convention.
This guide uses ℕ = {0, 1, 2, 3, ...}.Entiers et fondements
Absolute value
|a|La distance non négative d'un entier à zéro sur la droite numérique.
Utilisez-le pour exprimer l'amplitude, la distance, l'erreur et les bornes symétriques.
|-7| = 7 and |5 - 12| = 7.Entiers et fondements
Parity
n mod 2La propriété d'un entier d'être pair ou impair.
Utilisez la parité pour la ramification, les motifs alternés, les preuves, les sommes de contrôle et la logique au niveau des bits.
18 mod 2 = 0, so 18 is even.Entiers et fondements
Division algorithm
a = bq + rPour des entiers a et b positifs, il existe des entiers uniques q et r tels que 0 ≤ r < b.
Utilisez-le comme base des algorithmes de quotient, de reste, de l'algorithme euclidien et de l'arithmétique modulaire.
29 = 6 × 4 + 5, so q = 4 and r = 5.Divisibilité
Divisor
d | nUn entier d est un diviseur de n lorsque n = dk pour un certain entier k.
Utilisez les diviseurs pour analyser la structure des facteurs, les facteurs communs et la divisibilité exacte.
6 | 42 because 42 = 6 × 7.Divisibilité
Multiple
n = dkUn nombre obtenu en multipliant un entier par un autre entier.
Utilisez des multiples pour les calendriers, les périodes communes, les systèmes cycliques et l'alignement du dénominateur.
Les multiples de 5 comprennent 0, 5, 10, 15 et 20.Divisibilité
Divisibility test
n mod d = 0Une règle qui détermine si un entier divise un autre sans effectuer une division longue.
Utilisez-le pour les vérifications rapides, l'arithmétique mentale, la validation des entrées et l'enseignement de la structure de la valeur positionnelle.
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.Divisibilité
Greatest common divisor
gcd(a, b)Le plus grand entier positif qui divise les deux entiers exactement.
Utilisez-le pour réduire les fractions, tester la coprimalité, résoudre les congruences et calculer les rapports.
gcd(84, 30) = 6.Divisibilité
Least common multiple
lcm(a, b)Le plus petit entier positif qui est un multiple des deux entiers non nuls.
Utilisez-le pour synchroniser les cycles, combiner les fractions et calculer les calendriers répétitifs.
lcm(12, 18) = 36.Divisibilité
GCD-LCM identity
gcd(a,b)lcm(a,b)=|ab|Une relation reliant le plus grand diviseur commun et le plus petit multiple commun de deux entiers non nuls.
Utilisez-le pour calculer une quantité efficacement lorsque l'autre est déjà connue.
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.Divisibilité
Euclidean algorithm
gcd(a,b)=gcd(b,a mod b)Un algorithme de division euclidienne pour trouver le plus grand diviseur commun.
Utilisez-le pour le calcul rapide de la GCD, même lorsque les entiers d'entrée sont grands.
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.Divisibilité
Extended Euclidean algorithm
ax + by = gcd(a,b)Une extension de l'algorithme euclidien qui trouve également les coefficients de Bézout x et y.
Utilisez-le pour calculer les inverses modulaires et résoudre les équations diophantiennes linéaires.
35×(-1) + 12×3 = 1, donc -1 est un coefficient pour 35.Divisibilité
Coprime integers
gcd(a,b)=1Deux entiers sont premiers entre eux lorsque leur plus grand diviseur commun est 1.
Utilisez la coprimauté pour déterminer l'inversibilité modulo n et pour appliquer le théorème d'Euler.
8 et 15 sont premiers entre eux, même si aucun des deux nombres n'est premier.Nombres premiers et factorisation
Prime number
pUn entier supérieur à 1 dont les seuls diviseurs positifs sont 1 et lui-même.
Utilisez les nombres premiers comme blocs de construction de base de la factorisation des entiers et de la cryptographie à clé publique.
2, 3, 5, 7 et 11 sont des nombres premiers.Nombres premiers et factorisation
Composite number
n = abUn entier supérieur à 1 qui a un diviseur positif autre que 1 et lui-même.
Utilisez-le pour distinguer les entiers factorisables des nombres premiers.
21 is composite because 21 = 3 × 7.Nombres premiers et factorisation
Prime factorization
n=∏pᵢ^aᵢÉcrire un entier comme un produit de puissances de nombres premiers.
Utilisez-le pour calculer les diviseurs, les GCD, les PPCM et les fonctions arithmétiques.
360 = 2^3 × 3^2 × 5.Nombres premiers et factorisation
Fundamental theorem of arithmetic
n=∏pᵢ^aᵢChaque entier supérieur à 1 a une factorisation première qui est unique à l'ordre des facteurs près.
Utilisez-le pour justifier les algorithmes et les preuves basés sur des exposants premiers.
72 = 2^3 × 3^2 est la factorisation première unique de 72.Nombres premiers et factorisation
Sieve of Eratosthenes
Un algorithme qui liste les nombres premiers jusqu'à une limite en marquant à plusieurs reprises les multiples de chaque nombre premier découvert.
Utilisez-le lorsque de nombreuses requêtes de nombres premiers partagent la même limite supérieure modérée.
Pour trouver les nombres premiers inférieurs à 30, marquez les multiples de 2, 3 et 5.Nombres premiers et factorisation
Primality test
Un algorithme qui décide si un entier donné est premier.
Utilisez la division par essais pour les petites entrées et les tests probabilistes tels que Miller-Rabin pour les grandes entrées.
Un test de primalité probabiliste peut nécessiter plusieurs tours ou un ensemble de bases déterministe pour la plage d'entiers prévue.
La division d'essai nécessite uniquement des diviseurs candidats jusqu'à √n.Arithmétique modulaire
Congruence
a ≡ b (mod n)Deux entiers sont congruents modulo n lorsque n divise leur différence.
Utilisez-le pour remplacer les entiers par des résidus équivalents dans les calculs cycliques.
29 ≡ 5 (mod 12) car 12 divise 29 - 5.Arithmétique modulaire
Residue class
[a]ₙL'ensemble de tous les entiers congruents à un entier fixe modulo n.
Utilisez-le pour raisonner sur les valeurs modulaires comme des classes d'équivalence plutôt que comme des nombres isolés.
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.Arithmétique modulaire
Modulo operation
a mod nUne opération qui renvoie un reste représentatif après la division par n.
Utilisez-le pour l'imbrication des indices, les horloges, les compartiments de hachage et les états périodiques.
(23 + 5) mod 24 = 4.Arithmétique modulaire
Modular arithmetic
ℤ/nℤOpérations arithmétiques effectuées sur les classes de résidus avec des résultats réduits modulo n.
Utilisez-le en cryptographie, en théorie du codage, en tampons cycliques et en calculs de calendrier.
(17 × 19) mod 12 = 11.Arithmétique modulaire
Modular inverse
a⁻¹ mod nUne valeur x satisfaisant ax ≡ 1 (mod n) ; elle existe exactement lorsque pgcd(a,n)=1.
Utilisez-le pour la division en arithmétique modulaire, la résolution de congruences et la mise en œuvre d'algorithmes cryptographiques.
N'essayez pas d'effectuer une division modulaire avant de vérifier que le diviseur est premier avec le module.
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).Arithmétique modulaire
Modular exponentiation
a^k mod nCalcul d'une puissance modulo n sans construire d'abord la puissance entière potentiellement énorme.
Utilisez l'élévation au carré répétée en cryptographie, dans les tests de primalité et dans les problèmes à grands exposants.
3^13 mod 7 = 3 using repeated squaring.Arithmétique modulaire
Linear congruence
ax ≡ b (mod n)Une congruence qui recherche des entiers x satisfaisant une équation modulaire linéaire.
Utilisez les conditions du PGCD et les inverses modulaires pour déterminer et calculer les solutions.
3x ≡ 4 (mod 7) donne x ≡ 6 (mod 7).Arithmétique modulaire
Chinese remainder theorem
x ≡ aᵢ (mod nᵢ)Un théorème qui combine des congruences compatibles, donnant une solution unique modulo le produit lorsque les modules sont premiers entre eux.
Utilisez-le pour combiner des contraintes cycliques indépendantes et accélérer le calcul de grands entiers.
x ≡ 2 (mod 3), x ≡ 3 (mod 5) donne x ≡ 8 (mod 15).Arithmétique modulaire
Euler's totient function
φ(n)Le nombre d'entiers de 1 à n qui sont premiers avec n.
Utilisez-le dans le théorème d'Euler, les calculs de clés RSA et les systèmes de résidus réduits.
φ(12) = 4 car 1, 5, 7 et 11 sont premiers avec 12.Arithmétique modulaire
Euler's theorem
a^φ(n) ≡ 1 (mod n)Si a et n sont premiers entre eux, a élevé à φ(n) donne 1 modulo n.
Utilisez-le pour réduire les exposants, prouver les identités modulaires et expliquer RSA.
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).Arithmétique modulaire
Fermat's little theorem
a^(p-1) ≡ 1 (mod p)Pour un nombre premier p et un nombre a non divisible par p, a élevé à p-1 est congru à 1 modulo p.
Utilisez-le pour les inverses modulaires sous un module premier et pour le criblage de primalité.
Le fait qu'un nombre passe un test de Fermat ne prouve pas qu'il est premier, car des pseudopremiers existent.
2^6 ≡ 1 (mod 7).Groupes cycliques et générateurs
Group
(G, *)Un ensemble avec une opération associative, un élément neutre et un inverse pour chaque élément.
Utilisez les groupes pour décrire les structures arithmétiques dans lesquelles les opérations peuvent être composées et inversées.
Les entiers forment un groupe sous l'addition avec l'élément neutre 0 et l'inverse -a pour a.Groupes cycliques et générateurs
Abelian group
a*b=b*aUn groupe dont l'opération est commutative.
Utilisez-le pour l'addition modulaire, l'addition vectorielle et de nombreux groupes arithmétiques où l'ordre des opérations n'a pas d'importance.
(ℤ/nℤ, +) est un groupe abélien.Groupes cycliques et générateurs
Additive group modulo n
(ℤ/nℤ, +)Les classes résiduelles modulo n avec addition effectuée modulo n.
Utilisez-le pour modéliser les compteurs cycliques, les états périodiques et les classes de congruence sous l'addition.
In ℤ/5ℤ, 3+4=2.Groupes cycliques et générateurs
Multiplicative group of units
(ℤ/nℤ)×Les classes résiduelles premières avec n, avec multiplication modulo n.
Utilisez-le pour étudier les inverses modulaires, les racines primitives, le théorème d'Euler et la cryptographie à clé publique.
(ℤ/8ℤ)×={1,3,5,7}.Groupes cycliques et générateurs
Cyclic group
G=⟨g⟩Un groupe dont chaque élément est une puissance ou une somme répétée d'un seul élément.
Utilisez-le pour réduire une opération de groupe à une arithmétique sur les exposants ou les multiples entiers.
Le groupe additif ℤ/6ℤ est généré par 1 et par 5.Groupes cycliques et générateurs
Generator
⟨g⟩=GUn élément dont l'opération de groupe répétée produit chaque élément d'un groupe cyclique.
Utilisez-le pour énumérer les groupes cycliques et définir des opérations cryptographiques basées sur l'exposant.
Indiquez toujours le groupe et l'opération car un élément peut générer une structure mais pas une autre.
Les puissances de 3 modulo 7 produisent 3,2,6,4,5,1, donc 3 génère (ℤ/7ℤ)×.Groupes cycliques et générateurs
Order of an element
ord(g)Le plus petit entier positif k pour lequel g^k est l'élément neutre.
Utilisez-le pour tester si un élément est un générateur et pour déterminer la longueur du cycle.
Modulo 7, ord(2)=3 car 2^3≡1 et aucun exposant positif plus petit ne fonctionne.Groupes cycliques et générateurs
Primitive root
ordₙ(g)=φ(n)Un générateur du groupe multiplicatif des unités modulo n.
Utilisez les racines primitives pour représenter les résidus non nuls sous forme de puissances et pour formuler des logarithmes discrets.
3 est une primitive modulo 7 car son ordre est φ(7)=6.Groupes cycliques et générateurs
Primitive root existence
Les racines primitives modulo n existent exactement pour n=1, 2, 4, p^k, ou 2p^k où p est un nombre premier impair.
Utilisez ce critère avant de rechercher une racine primitive modulo un nombre composé.
Il n'y a pas de racine primitive modulo 8 car 8 ne possède aucune des formes requises.Groupes cycliques et générateurs
Discrete logarithm
g^x=hÉtant donné un générateur g et un élément de groupe h, le logarithme discret recherche un exposant x satisfaisant g^x=h.
Utilisez-le pour comprendre les hypothèses de sécurité de Diffie-Hellman, ElGamal et des courbes elliptiques.
Le logarithme discret peut être facile dans les petits groupes ou les groupes mal choisis, et difficile uniquement sous des paramètres appropriés.
Modulo 7 avec le générateur 3, log₃(5)=5 car 3^5≡5.Groupes cycliques et générateurs
Carmichael function
λ(n)Le plus petit exposant positif m tel que a^m≡1 modulo n pour tout a premier avec n.
Utilisez-le pour obtenir un exposant universel plus serré que φ(n) pour les puissances modulaires et l'analyse RSA.
λ(8)=2 car chaque a impair satisfait a²≡1 (mod 8).Résidus quadratiques
Quadratic residue
x²≡a (mod n)Un résidu a pour lequel la congruence x²≡a modulo n a une solution.
Utilisez-le pour analyser les racines carrées modulaires, les tests de primalité et la cryptographie des résidus quadratiques.
2 est un résidu quadratique modulo 7 car 3²≡2.Résidus quadratiques
Quadratic nonresidue
Un résidu non nul pour lequel x²≡a modulo n n'a pas de solution.
Utilisez-le pour classer les résidus et construire des tests ou des paramètres cryptographiques avec un caractère quadratique connu.
3 est un résidu non quadratique modulo 7.Résidus quadratiques
Modular square root
x=√a mod nUne solution x à x²≡a modulo n.
Utilisez-le dans la décompression de points, les algorithmes de théorie des nombres et la cryptographie basée sur les résidus.
Les racines carrées de 2 modulo 7 sont 3 et 4.Résidus quadratiques
Legendre symbol
(a/p)Pour un nombre premier impair p, une valeur 0, 1 ou -1 indiquant la divisibilité par p ou le statut de résidu quadratique modulo p.
Utilisez-le pour tester le caractère quadratique et énoncer le critère d'Euler et la réciprocité quadratique de manière concise.
(2/7)=1 car 2 est un résidu quadratique modulo 7.Résidus quadratiques
Jacobi symbol
(a/n)Une extension multiplicative du symbole de Legendre aux dénominateurs impairs positifs.
Utilisez-le pour les calculs de caractères efficaces et les algorithmes qui ne nécessitent pas de factorisation de n au préalable.
Un symbole de Jacobi égal à 1 ne garantit pas que a est un résidu quadratique modulo n, un nombre composé.
(5/21)=(5/3)(5/7)=1.Résidus quadratiques
Euler's criterion
a^((p-1)/2)≡(a/p) (mod p)Un critère qui détermine le statut de résidu quadratique modulo un nombre premier impair en utilisant l'exponentiation modulaire.
Utilisez-le pour calculer le symbole de Legendre sans énumérer chaque carré.
Pour p=7, 3^3≡-1 (mod 7), donc 3 est un résidu quadratique non trivial.Résidus quadratiques
Quadratic reciprocity
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)Un théorème reliant le fait qu'un nombre premier impair est un résidu quadratique modulo un autre.
Utilisez-le pour réduire les calculs longs du symbole de Legendre à des calculs plus petits.
Parce que 3 et 11 sont tous les deux 3 modulo 4, (3/11)=-(11/3).Résidus quadratiques
Supplementary laws
(-1/p), (2/p)Formules qui déterminent le caractère quadratique de -1 et 2 modulo un nombre premier impair.
Utilisez-les avec la réciprocité quadratique pour compléter les calculs du symbole de Legendre.
(2/p)=1 lorsque p≡1 ou 7 (mod 8), et -1 lorsque p≡3 ou 5 (mod 8).Résidus quadratiques
Tonelli-Shanks algorithm
Un algorithme pour trouver une racine carrée modulaire d'un résidu quadratique modulo un nombre premier impair.
Utilisez-le lorsque le module est premier et que la simplification simple p≡3 modulo 4 ne s'applique pas.
Pour p=13, l'algorithme de Tonelli-Shanks trouve x=6 ou 7 pour x²≡10 (mod 13).Résidus quadratiques
Square roots modulo a composite
Les racines carrées modulaires sont trouvées modulo les facteurs de puissance premiers et combinées avec le théorème des restes chinois.
Utilisez-le pour analyser les systèmes de type Rabin et les congruences avec des modules composés.
Pour un produit de nombres premiers impairs distincts, une seule racine peut avoir plusieurs racines carrées, de sorte que la sélection de la racine prévue nécessite des informations supplémentaires.
Résoudre x²≡1 modulo 3 et 5, puis combiner les choix de signe modulo 15.Équations entières
Diophantine equation
Une équation pour laquelle seules les solutions entières sont recherchées.
Utilisez la divisibilité, le PGCD, les congruences et les bornes pour déterminer si des solutions entières existent.
3x + 5y = 17 has the integer solution x = 4, y = 1.Équations entières
Linear Diophantine equation
ax + by = cUne équation linéaire dont les inconnues doivent être des entiers ; les solutions existent exactement lorsque pgcd(a,b) divise c.
Utilisez-le pour l'allocation exacte, les problèmes de pièces de monnaie, les calendriers et les contraintes de treillis.
6x + 9y = 30 est résoluble car pgcd(6,9)=3 divise 30.Applications
RSA arithmetic
c ≡ m^e (mod n)Arithmétique à clé publique basée sur l'exponentiation modulaire et la difficulté de factoriser un produit de grands nombres premiers.
Utilisez-le pour comprendre comment la théorie des nombres prend en charge le cryptage et les signatures numériques.
Les valeurs de test sont uniquement à des fins d'apprentissage ; le véritable RSA nécessite un remplissage standard, des tailles de clés sécurisées et des bibliothèques auditées.
Avec les valeurs exemples n=55, e=3, et m=7, c=7^3 mod 55=13.