Diviseur de (p-1)(q-1) connaissant pq

Foufoux
Foufoux
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...

Réponses

  • FdP-HLM
    FdP-HLM
    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
  • Foufoux
    Foufoux
    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
  • GreginGre
    GreginGre
    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.$
  • Foufoux
    Foufoux
    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 ?
  • LP
    LP
    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
  • FdP-HLM
    FdP-HLM
    $\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.
  • GreginGre
    GreginGre
    Je confirme ce que dit LP.
  • Foufoux
    Foufoux
    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).
  • FdP-HLM
    FdP-HLM
    Si on prend un groupe G quelconque, y-a-t-il une méthode générique pour trouver des sous groupes de G ? a écrit:

    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$
  • Upa0
    Upa0
    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!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 5

BoulexDomPoirotgerard0manu