Nombres premiers
Bonjour à tous,
confinement oblige, je revois un cours d'initiation à la cryptographie (test de Miller Rabin RSA etc...)
J'ai regardé les classes de congruence modulo un nombre premier des nombres premiers plus petits que 100 000.
par exemple pour 3 : [1, 4784, 4806] Parmi les nombres plus petits que 100 000 j'ai un nombre premier égal à 0 mod 3(là ce n'est pas un scoop) mais 4784 nombres premiers congrus à 1 mod3 et 4806 nombres premiers congrus à 2 mod3
pour 5 : [1, 2387, 2411, 2402, 2390]
pour 7 : [1, 1593, 1583, 1613, 1601, 1604, 1596]
J'ai regardé avec d'autres nombres, on a l'impression que l'on a à peu près la même proportion dans chaque classe de congruence. Il y a des résultats connus concernant ce fait ?
Merci d'avance
Robert
confinement oblige, je revois un cours d'initiation à la cryptographie (test de Miller Rabin RSA etc...)
J'ai regardé les classes de congruence modulo un nombre premier des nombres premiers plus petits que 100 000.
par exemple pour 3 : [1, 4784, 4806] Parmi les nombres plus petits que 100 000 j'ai un nombre premier égal à 0 mod 3(là ce n'est pas un scoop) mais 4784 nombres premiers congrus à 1 mod3 et 4806 nombres premiers congrus à 2 mod3
pour 5 : [1, 2387, 2411, 2402, 2390]
pour 7 : [1, 1593, 1583, 1613, 1601, 1604, 1596]
J'ai regardé avec d'autres nombres, on a l'impression que l'on a à peu près la même proportion dans chaque classe de congruence. Il y a des résultats connus concernant ce fait ?
Merci d'avance
Robert
Réponses
-
Oui, c'est le théorème des nombres premiers en progressions arithmétiques :
Si $\pi(x; q, a)$ désigne le nombre de nombres premiers $p \leq x$ tels que $p \equiv a [q]$ alors si $a$ et $q$ sont premiers entre eux, on a $$\pi(x; q, a) \underset{x \to +\infty}{\sim} \frac{1}{\varphi(q)} \frac{x}{\log x},$$ où $\varphi(q)$ est le nombre de classes inversibles modulo $q$. En particulier, l'équivalent donné ne dépend pas de $a$ ! Les classes modulo $q$ des nombres premiers s'équirépartissent dans les classes inversibles modulo $q$ : asymptotiquement, si $a$ et $b$ sont premiers avec $q$ alors la proportion des $p$ tels que $p \equiv a [q]$ et la proportion des $p$ tels que $p \equiv b [q]$ sont les mêmes (égales à $\frac{1}{\varphi(q)})$. -
Merci beaucoup Poirot.
C'est un très beau résultat. J'ai vérifié avec x plus grand, ça colle bien avec l'équivalent.
Bonne journée
Robert
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 804 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres