Partition de {1,...,n}
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 !
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 !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
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 ?