Diviseur de (p-1)(q-1) connaissant pq
dans Arithmétique
Bonjour,
Je "travaille" sur un petit projet de factorisation de grand nombre.
Soient p et q deux nombres premiers et N leur produit.
On sait alors que $\Phi(N) = (p-1)*(q-1)$.
Je cherche à trouver des facteurs à $\Phi(N)$ en fonction des restes de divisions euclidiennes de N.
Si N est égal à 1 mod 2, alors $\Phi(N)$ est divisible par 2.
De même pour les résultats suivants :
2 mod 3,
1 mod 4
3 mod 4
5 mod 6
3 mod 8
7 mod 8
5 mod 12
11 mod 12
11 mod 24
23 mod 24
Ma question est la suivante : existe-t-il d'autres diviseurs de la sorte ? Si non, comment peut-on le démontrer ?
Merci de votre aide...
Je "travaille" sur un petit projet de factorisation de grand nombre.
Soient p et q deux nombres premiers et N leur produit.
On sait alors que $\Phi(N) = (p-1)*(q-1)$.
Je cherche à trouver des facteurs à $\Phi(N)$ en fonction des restes de divisions euclidiennes de N.
Si N est égal à 1 mod 2, alors $\Phi(N)$ est divisible par 2.
De même pour les résultats suivants :
2 mod 3,
1 mod 4
3 mod 4
5 mod 6
3 mod 8
7 mod 8
5 mod 12
11 mod 12
11 mod 24
23 mod 24
Ma question est la suivante : existe-t-il d'autres diviseurs de la sorte ? Si non, comment peut-on le démontrer ?
Merci de votre aide...
Réponses
-
Si $p_1^{s_1}p_2^{s_2}...p_k^{s_k}$ est la décomposition en facteurs premiers de n où les $p_i$ sont distincts
on a: \quad$\phi(n)=\phi(p_1^{s_1})\phi(p_2^{s_2})...\phi(p_1^{s_1})$
et si p est premier et $n>0$ est un entier alors:
$\phi(p^n)=p^n-p^{n-1}$ sauf erreur -
Bonjour,
Je reviens sur mon idée de trouver des diviseurs de $\phi(N) = (p-1)(q-1)$ connaissant $pq = N$ (p et q premier):
On connait la propriété suivante :
Si G est un groupe abélien d’ordre $\phi(N)$ et que k divise $\phi(N)$ alors il existe un sous groupe de G d’ordre k.
Ma question est donc :
Existe-t-il des méthodes pour trouver facilement des sous groupes de G lorsqu'on travaille sur $G = \mathbb{Z}/p\mathbb{Z}$, avec p premier ?
Si vous avez des références, je suis preneur,
Merci
++,
Foufoux -
Si $G=\Z/p\Z$ avec $p$ premier, tu n'as pas beaucoup de sous-groupes: $G$ et le groupe trivial.
En particulier, si tu prends n'importe quel $g\in G$ différent du neutre, alors $\{1,g,g^2,\ldots,g^{p-1}\}=G.$ -
Si je fixe $p=5$ et je prends $g = 4$, je tombe sur
$\{1,g,g^2,…,g^{p-1}\} = \{1,4,1,4,1\} \ne G $
où ai je faux ? -
Bonjour,
$\mathbb{Z}/p\mathbb{Z}$ est un groupe additif donc c'est $\{0, g, 2g, 3g, 4g \}$ qui est égal à $G$.
Dans son poste, Greg avait, je pense, en tête un groupe quelconque (même s'il écrit au début $G=\mathbb{Z}/p\mathbb{Z}$) pour lequel on emploie en général la notation multiplicative.
LP -
$\mathbb{Z}/p\mathbb{Z}$ avec $p$ premier muni de la multiplication n'est pas un groupe. Il faut enlever la classe de $0$ pour obtenir un groupe pour cette loi.
-
Je confirme ce que dit LP.
-
Ok, merci pour vos réponses...
Si on prend un groupe $G$ quelconque, y-a-t-il une méthode générique pour trouver des sous groupes de $G$ ?
(autre que celle qui consiste à tester tous les éléments les uns après les autres). -
Pour trouver des sous-groupes tu peux considérer les sous-groupes engendrés par un élément (voire par 2, par 3,...,éléments).
C'est à dire, si g est un élément différent de l'élément neutre (autrement tu obtiens le sous-groupe trivial) tu peux considérer l'ensemble $g,g^2,g^3,...$. Si le groupe $G$ est d'ordre fini, l'ordre d'un élément est fini.
Si $G$ est d'ordre un nombre impair, le sous-groupe de $G$ engendré par un élément différent de l'élément neutre est strictement plus grand que $2$ -
Plus précisément, si tu considères un groupe $G$ et que tu choisis un $x \in G$ tu as deux possibilités :
- $x$ n'engendre pas $G$. Dans ce cas, $< x >$ est un sous-groupe propre de $G$.
- $x$ engendre $G$. Dans ce cas, c'est beaucoup mieux : $G$ est monogène et donc isomorphe à $\mathbb{Z} / N \mathbb{Z}$ (où $N$ est l'ordre de $G$). On connaît alors tous les sous-groupes de $G$ : pour chaque diviseur $d$ de $N$, les éléments d'ordre $d$ sont les éléments $k$ tels que le $N/pgcd(k,N) = d$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres