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...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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
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
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.$
$\{1,g,g^2,…,g^{p-1}\} = \{1,4,1,4,1\} \ne G $
où ai je faux ?
$\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
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$
- $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$.