Partition de {1,...,n}

Petit mathématicien
Petit mathématicien
dans Algèbre
Bonjour,
dans la solution d'un exercice, je lis (sans justification).

On a : $[1, n] = \bigcup_{ d \mid n} \{k \in [1, n] \mid \mathrm{pgcd}(k,n) = d\}$.

J'aimerais montrer rigoureusement cette formule.

Tout d'abord, après quelques investigations, je m'aperçois qu'on peut définir une relation d'équivalence de $\{1,\ldots,n\}$ en faisant $x \sim y \iff \mathrm{pgcd}(n,x)=\mathrm{pgcd}(n,y)$. On a donc une partition de $\{1,\ldots,n\}$ par les classes d'équivalences.
Les classes d'équivalences pour cette relation sont $\bar{x}=\{y \mid \mathrm{pgcd}(n,x)=\mathrm{pgcd}(n,y)\}$.
On a donc $\{1,\ldots,n\}= \bigcup_{x=1}^n \{ y \mid \mathrm{pgcd}(n,x)=\mathrm{pgcd}(n,y) \}$.

Et ensuite ?
Merci par avance !

Réponses

  • Poirot
    Poirot
    Bah le pgcd de $n$ et de n'importe quel entier est un diviseur de $n$. Chaque classe d'équivalence est donc de la forme $$\{y \in [1, n] \mid \text{pgcd}(n,y)=d\}$$ avec $d$ divisant $n$.
  • Math Coss
    Math Coss
    Autre version. Soit $D(n)$ l'ensemble des diviseurs de $n$. On définit une application \[f:\{1,\dots,n\}\to D(n),\quad k\mapsto \mathrm{pgcd}(k,n).\] Alors $\{1,\dots,n\}$ est la réunion disjointe des images réciproques des éléments de $D(n)$ : \[\{1,\dots,n\}=\bigcup_{d\in D(n)}f^{-1}\bigl(\{d\}\bigr)=\bigcup_{d\mid n}\{k,\ \mathrm{pgcd}(k,n)=d\}.\](Note que les $f^{-1}\bigl(\{d\}\bigr)$ sont exactement les classes d'équivalence de ta relation $\sim$.)
  • Petit mathématicien
    Petit mathématicien
    Bonsoir, je reste perplexe..

    n'y a-t-il pas une égalité ensembliste qui permette de justifier l'égalité : $$

    \bigcup_{x=1}^n \{ y \mid \mathrm{pgcd}(n,x)=\mathrm{pgcd}(n,y)= \bigcup_{d\mid n} \{ y \mid d=\mathrm{pgcd}(n,y) \}.

    $$ ou sinon une piste pour une double inclusion ?
    Merci.
  • Maxtimax
    Maxtimax
    Bah si la double inclusion ça marche très bien quelle étape te pose problème ?
  • Petit mathématicien
    Petit mathématicien
    c'est l'inclusion droite vers gauche qui me pose problème: quel est le candidat pour x ?
  • Maxtimax
    Maxtimax
    $y$ ?
  • Petit mathématicien
    Petit mathématicien
    mon problème c'est comment passer des d|n à x allant de 1 à n ?
  • Maxtimax
    Maxtimax
    Donc ce n'est plus l'inclusion droite vers gauche ton problème ? Je réessaie.

    Soit $y$ dans le bonhomme de gauche, alors $\mathrm{pgcd}(y,n) \mid n$ par définition de pgcd (plus grand commun diviseur). Soit $d= \mathrm{pgcd}(y,n)$. Alors $y\in \{x , \mathrm{pgcd}(x,n)=d\}$ donc $y\in \bigcup_{d\mid n} \{x, \mathrm{pgcd}(x,n) = d\}$.

    Soit $y$ dans le bonhomme de droite. Alors $\mathrm{pgcd}(y,n) = \mathrm{pgcd}(y,n)$ donc $y\in \{x, \mathrm{pgcd}(x,n) = \mathrm{pgcd}(y,n)\}$ donc $y\in \bigcup_{x=1}^n \{k, \mathrm{pgcd}(k,n) = \mathrm{pgcd}(x,n)\}$.

    D'où double inclusion, d'où égalité. Qu'est-ce que tu ne comprends pas là-dedans ?
  • Math Coss
    Math Coss
    Attention toutefois : dans le membre de gauche de l'égalité \[\bigcup_{x=1}^n \bigl\{ y \mid \mathrm{pgcd}(n,x)=\mathrm{pgcd}(n,y)\bigr\}= \bigcup_{d\mid n} \bigl\{ y \mid d=\mathrm{pgcd}(n,y) \bigr\},\] les différentes parties ne sont pas disjointes en général, il y a des répétitions. C'est bien évident : à gauche on a $n$ parties ; à droite, on en a autant que de diviseurs de $n$ ; en général ce n'est pas le même nombre.
  • Petit mathématicien
    Petit mathématicien
    Merci beaucoup, c'est compris.
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 21

ChaurienCidrolinJLTbiguine_equationgai requinssi +15 Invités