division euclidienne et théorie des groupes
dans Arithmétique
Bonjour,
une simple division euclidienne (dividende = diviseur x quotient + reste) peut-être une manière plus ou moins consciente de réviser les fondamentaux de la théorie des groupes.
Les concepts de base de l'algèbre abstraite apportent un éclairage différent sur des problèmes arithmétiques comme par exemple celui du développement décimal périodique.
Quand on muni l'ensemble $\{1, 2, 3, 4, 5, 6\}$ de la multiplication modulo $7$ et qu'on "dresse" la table de multiplication de ce groupe, on voit que la ligne $3$ est le cycle $(132645)$. En effectuant bien docilement la division de $1$ par $7$, les restes successifs qui apparaissent lors du processus de division forment précisément le cycle de la ligne $3$. Ce cycle contient tous les restes possibles et sa longueur est donc maximale.
Quel cycle obtient-on avec un dénominateur égal à $13$ et des numérateurs compris entre $1$ et $12$ ?
$\displaystyle 1/13 = 0,\overline{076923} \quad 3/13=0,\overline{230769} \quad 9/13=0,\overline{692307}$,...
Mais:
$\displaystyle 2/13 = 0,\overline{153846} \quad 5/13=0,\overline{384615} \quad11/13 = 0,\overline{846153}$,...
Dans la division par $13$, les quotients se répartissent en deux groupes.
Les fractions $2/13, 5/13, 6/13, 7/13, 8/13, 11/13$ ont le même développement décimal périodique, chacun commençant à un rang différent.
Les fractions $1/13, 3/13, 4/13, 9/13, 10/13, 12/13$ ont le leur.
Dans les deux cas, ces développements s'apparentent à des permutations circulaires de suites spécifiques aux deux groupes de fractions.
Posons la division euclidienne de $5$ par $13$, en nous concentrant cette fois, non pas sur les décimales du quotient mais sur les restes successifs obtenus sous le dividende.
Lors de cette division, à chaque fois qu'on obtient un reste par soustraction, on abaisse un $"0"$ à droite, ce qui revient à multiplier le reste par $10$ puis à le réduire modulo le diviseur.
Multiplions $\displaystyle \frac{5}{13}$ par $10$:
\begin{equation}
10\big(\frac{5}{13}\big) = \frac{50}{13} = 3,\overline{846153}.
\end{equation}
Mais $50 = 5.10 \equiv 11 \pmod {13}$ et $\displaystyle \frac{50}{13} = \frac{11}{13} + 3$
Donc $\displaystyle \frac{11}{13} = 0,\overline{846153}$.
En décalant une décimale vers la gauche, la multiplication par $10$ permet de passer de la fraction $5/13$ à la fraction $11/13$.
Le nouveau numérateur $11$ est multiplié par $10$:
\begin{equation}
11.10 = 110 \equiv 6 \pmod {13}.
\end{equation}
Exprimé en fonction du numérateur originel, cela s'écrit:
\begin{equation}
5.10^2 \equiv 6 \pmod {13}.
\end{equation}
Or: $\displaystyle \frac{110}{13} = \frac{6}{13} + 8$. Donc $\displaystyle \frac{6}{13} = 0,\overline{461538}$.
Le nouveau numérateur est multiplié par $10$:
\begin{equation}
6.10 \equiv 8 \pmod {13}.
\end{equation}
Or: $\displaystyle \frac{60}{13} = \frac{8}{13} + 4$ donc $\displaystyle \frac{8}{13} = 0,\overline{615384}$.
Et ainsi de suite jusqu'à ce que recommence un nouveau cycle... Rien que de très banal sauf que ces petits calculs mettent en évidence la nature cyclique qui unit les restes avec les décimales du quotient.
En général, si $5.10^k \equiv r \pmod {13}$, avec $0 \leq r < 13$, alors $\displaystyle \frac{r}{13}$ a pour développement décimal celui de $\displaystyle \frac{5}{13}$ mais décalé de $k$ rangs vers la gauche.
Tous ces cycles sont de longueur $6$ et après $6$ décalages, on revient au cycle initial.
Ainsi, nous avons pour chaque reste $r$, une fraction $\displaystyle \frac{r}{13}$ telle que pour un certain $k$:
\begin{equation}
r \equiv 5.10^k \pmod {13}
\end{equation}
Dans le groupe multiplicatif $\mathbb{Z}/13\mathbb{Z}^*$, l'ensemble $\{5.10^k \pmod {13}: \ k=1,2, …\}$ est la classe d'équivalence du sous-groupe cyclique $\langle 10 \pmod {13} \rangle$.
Dans la division de $1$ par $13$, le premier reste rencontré est $10$. La suite des restes sera donc:
$\displaystyle H = \{10, 10^2, 10^3, 10^4, 10^5, 10^6\}\pmod{13} = \{10, 9, 12, 3, 4, 1 \}$.
Elle se répète après $1$ qui ramène à la division initiale car on atteint un $k$ tel que $10^k \equiv 1 \pmod {13}$.
Tout le monde aura reconnu dans $k$, l'ordre de l'élément $10$ dans le groupe des inversibles de $\mathbb{Z}/13\mathbb{Z}$ et l'ensemble:
$\displaystyle H = \{10, 10^2, 10^3, 10^4, 10^5, 10^6 \equiv 1 \} \pmod {13} = \{10, 9, 12, 3, 4, 1\}$ est un sous-groupe cyclique de $\mathbb{Z}/13\mathbb{Z}^*$ généré par $10$.
Mais, on l'a vu, la division de $2$ par $13$ fournit une deuxième suite de restes: $\displaystyle 2H = \{7, 5, 11, 6, 8, 2 \}$.
Ils se déduisent de l'ensemble $H$ en multipliant chacun des éléments de $H$ par $2$ et en réduisant modulo $13$.
En effet, les calculs se faisant dans $\mathbb{Z}/13\mathbb{Z}$, le produit de deux restes $x$ et $y$ est $xy \mod 13$.
Ainsi $2. 10 \equiv 7 \pmod {13}$, $5 = 2.10^2 = 18 \equiv 5 \pmod {13}$, $11 = 2.10^3 = 24 \pmod {13}$, $6 = 2.10^4 \pmod {13}$, etc…
$2H$ contient tous les éléments de $\mathbb{Z}/13\mathbb{Z}*$ de la forme $2 \times 10^j$.
C'est la classe d'équivalence de $2$ modulo le sous-groupe $H$.
Les éléments $\displaystyle 1/13$ et $\displaystyle 2/13$ peuvent-être vus comme des représentants des deux classes d'équivalence $H$ et $2H$ dont la réunion est égale à $\mathbb{Z}/13\mathbb{Z}^*$.
On peut conclure avec deux exemples.
•Pour $n=41$ premier, le sous-groupe cyclique, généré par $10$, de $\mathbb{Z}/41\mathbb{Z}^*$ est $H = \{10, 10^2, 10^3, 10^4, 10^5, 10^6 \equiv 1\} = \{10, 18, 16, 37, 1 \}$.
Les classes modulo $H$ sont: $2H = {20, 36, 32, 33, 2}$, $3H = \{30, 13, 7, 29, 3 \}$, $4H = \{40, 31, 23, 25, 4 \}$, $5H = \{9, 8, 39, 21, 5 \}$, $6H = \{19, 26, 14, 17, 6 \}$, $7H = 3H$, $8H = 5H = 9H$, $10H = H$, $11H = \{28, 34, 12, 38, 11 \}$, …, $15H = \{27, 24, 35, 22, 15 \}$.
Si on calcule $\displaystyle \frac{7}{31}$, $7$ étant dans la classe d'équivalence $3H$, les restes de la division seront dans l'ordre: $7, 29, 3, 30, 13$ et retour à $7$…
Pour $\displaystyle \frac{26}{41}$, il suffit de parcourir $6H: 26, 14, 17, 6, 19$ et retour à $26$...
•Si le module est un nombre composé comme $39$, il faut lister les fractions irréductibles ayant 39 au dénominateur. L'ensemble des numérateurs sera $G = \{1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 23, 25, 28, 29, 31, 32, 34, 35, 37, 38 \}$.
Muni de la multiplication modulo $39$, G est un groupe: $\mathbb{Z}/39\mathbb{Z}^*$, de cardinal $\varphi(39)=24$.
Comme précédemment, la période du développement décimal de $\displaystyle \frac{1}{39}$ est égale à l'ordre du sous-groupe de $\mathbb{Z}/39\mathbb{Z}^*$ généré par $10$.
Puisque l'ordre d'un sous-groupe de $G$ divise l'ordre de $G$, pour un $x$ donné, la période de $\displaystyle \frac{x}{39}$ doit-être un des diviseurs de $24$: $1, 2, 3, 4, 6, 8, 12$ ou $24$ lui-même. Ce dernier est exclu puisqu'un résultat de théorie des nombres dit que $\mathbb{Z}/n\mathbb{Z}^*$ n'est pas cyclique si $n$ possède plus d'un facteur premier impair.
Un calcul montre que $10^6 \equiv 1 \pmod {39}$: l'ordre de $10$ est $6$ et le sous-groupe $H$ généré par $10$ est:
\begin{equation}
\{10, 10^2, 10^3, 10^4, 10^5, 10^6 \} \pmod {39} = \{10, 22, 25, 16, 4, 1 \}.
\end{equation}
Ce sont les restes successifs dans la division de $1$ par $39$.
$H$ étant de cardinal $6$, les $24$ restes possibles à partir desquels se reforment les $24$ fractions, se répartissent en $4$ classes d'équivalence: $H, 2H, 7H, 14H$, chacune contenant $6$ éléments.
Le nombre de ces classes, $4$, est l'indice de $H$ dans $\mathbb{Z}/39\mathbb{Z}^*$.
Enfin, il est possible de donner à cet ensemble de classes, une structure de groupe en définissant une multiplication modulo $39$.
Si on multiplie entre eux les éléments de la classe $2H$ avec les éléments de la classe $14H$: le résultat est la classe $7H$.
Ainsi, les éléments d’un groupe peuvent être des ensembles.
La conclusion de tout cela ? Les frontières entre les différentes disciplines mathématiques ne sont pas aussi nettes qu'on le croit.
L'Américain T.J. Fletcher a pour sa part mis en évidence les liens entre les développements décimaux périodiques et le mélange des cartes à jouer. Mais c'est une autre histoire.
références:
F.J. Budden-La fascination des groupes. éd: OCDL.
L. Brenton-remainder wheels and group theory.
Keith Conrad-cyclic groups.
H.Rademache et O.Toeplitz-the enjoyment of math-Princeton University Press.
...
une simple division euclidienne (dividende = diviseur x quotient + reste) peut-être une manière plus ou moins consciente de réviser les fondamentaux de la théorie des groupes.
Les concepts de base de l'algèbre abstraite apportent un éclairage différent sur des problèmes arithmétiques comme par exemple celui du développement décimal périodique.
Quand on muni l'ensemble $\{1, 2, 3, 4, 5, 6\}$ de la multiplication modulo $7$ et qu'on "dresse" la table de multiplication de ce groupe, on voit que la ligne $3$ est le cycle $(132645)$. En effectuant bien docilement la division de $1$ par $7$, les restes successifs qui apparaissent lors du processus de division forment précisément le cycle de la ligne $3$. Ce cycle contient tous les restes possibles et sa longueur est donc maximale.
Quel cycle obtient-on avec un dénominateur égal à $13$ et des numérateurs compris entre $1$ et $12$ ?
$\displaystyle 1/13 = 0,\overline{076923} \quad 3/13=0,\overline{230769} \quad 9/13=0,\overline{692307}$,...
Mais:
$\displaystyle 2/13 = 0,\overline{153846} \quad 5/13=0,\overline{384615} \quad11/13 = 0,\overline{846153}$,...
Dans la division par $13$, les quotients se répartissent en deux groupes.
Les fractions $2/13, 5/13, 6/13, 7/13, 8/13, 11/13$ ont le même développement décimal périodique, chacun commençant à un rang différent.
Les fractions $1/13, 3/13, 4/13, 9/13, 10/13, 12/13$ ont le leur.
Dans les deux cas, ces développements s'apparentent à des permutations circulaires de suites spécifiques aux deux groupes de fractions.
Posons la division euclidienne de $5$ par $13$, en nous concentrant cette fois, non pas sur les décimales du quotient mais sur les restes successifs obtenus sous le dividende.
Lors de cette division, à chaque fois qu'on obtient un reste par soustraction, on abaisse un $"0"$ à droite, ce qui revient à multiplier le reste par $10$ puis à le réduire modulo le diviseur.
Multiplions $\displaystyle \frac{5}{13}$ par $10$:
\begin{equation}
10\big(\frac{5}{13}\big) = \frac{50}{13} = 3,\overline{846153}.
\end{equation}
Mais $50 = 5.10 \equiv 11 \pmod {13}$ et $\displaystyle \frac{50}{13} = \frac{11}{13} + 3$
Donc $\displaystyle \frac{11}{13} = 0,\overline{846153}$.
En décalant une décimale vers la gauche, la multiplication par $10$ permet de passer de la fraction $5/13$ à la fraction $11/13$.
Le nouveau numérateur $11$ est multiplié par $10$:
\begin{equation}
11.10 = 110 \equiv 6 \pmod {13}.
\end{equation}
Exprimé en fonction du numérateur originel, cela s'écrit:
\begin{equation}
5.10^2 \equiv 6 \pmod {13}.
\end{equation}
Or: $\displaystyle \frac{110}{13} = \frac{6}{13} + 8$. Donc $\displaystyle \frac{6}{13} = 0,\overline{461538}$.
Le nouveau numérateur est multiplié par $10$:
\begin{equation}
6.10 \equiv 8 \pmod {13}.
\end{equation}
Or: $\displaystyle \frac{60}{13} = \frac{8}{13} + 4$ donc $\displaystyle \frac{8}{13} = 0,\overline{615384}$.
Et ainsi de suite jusqu'à ce que recommence un nouveau cycle... Rien que de très banal sauf que ces petits calculs mettent en évidence la nature cyclique qui unit les restes avec les décimales du quotient.
En général, si $5.10^k \equiv r \pmod {13}$, avec $0 \leq r < 13$, alors $\displaystyle \frac{r}{13}$ a pour développement décimal celui de $\displaystyle \frac{5}{13}$ mais décalé de $k$ rangs vers la gauche.
Tous ces cycles sont de longueur $6$ et après $6$ décalages, on revient au cycle initial.
Ainsi, nous avons pour chaque reste $r$, une fraction $\displaystyle \frac{r}{13}$ telle que pour un certain $k$:
\begin{equation}
r \equiv 5.10^k \pmod {13}
\end{equation}
Dans le groupe multiplicatif $\mathbb{Z}/13\mathbb{Z}^*$, l'ensemble $\{5.10^k \pmod {13}: \ k=1,2, …\}$ est la classe d'équivalence du sous-groupe cyclique $\langle 10 \pmod {13} \rangle$.
Dans la division de $1$ par $13$, le premier reste rencontré est $10$. La suite des restes sera donc:
$\displaystyle H = \{10, 10^2, 10^3, 10^4, 10^5, 10^6\}\pmod{13} = \{10, 9, 12, 3, 4, 1 \}$.
Elle se répète après $1$ qui ramène à la division initiale car on atteint un $k$ tel que $10^k \equiv 1 \pmod {13}$.
Tout le monde aura reconnu dans $k$, l'ordre de l'élément $10$ dans le groupe des inversibles de $\mathbb{Z}/13\mathbb{Z}$ et l'ensemble:
$\displaystyle H = \{10, 10^2, 10^3, 10^4, 10^5, 10^6 \equiv 1 \} \pmod {13} = \{10, 9, 12, 3, 4, 1\}$ est un sous-groupe cyclique de $\mathbb{Z}/13\mathbb{Z}^*$ généré par $10$.
Mais, on l'a vu, la division de $2$ par $13$ fournit une deuxième suite de restes: $\displaystyle 2H = \{7, 5, 11, 6, 8, 2 \}$.
Ils se déduisent de l'ensemble $H$ en multipliant chacun des éléments de $H$ par $2$ et en réduisant modulo $13$.
En effet, les calculs se faisant dans $\mathbb{Z}/13\mathbb{Z}$, le produit de deux restes $x$ et $y$ est $xy \mod 13$.
Ainsi $2. 10 \equiv 7 \pmod {13}$, $5 = 2.10^2 = 18 \equiv 5 \pmod {13}$, $11 = 2.10^3 = 24 \pmod {13}$, $6 = 2.10^4 \pmod {13}$, etc…
$2H$ contient tous les éléments de $\mathbb{Z}/13\mathbb{Z}*$ de la forme $2 \times 10^j$.
C'est la classe d'équivalence de $2$ modulo le sous-groupe $H$.
Les éléments $\displaystyle 1/13$ et $\displaystyle 2/13$ peuvent-être vus comme des représentants des deux classes d'équivalence $H$ et $2H$ dont la réunion est égale à $\mathbb{Z}/13\mathbb{Z}^*$.
On peut conclure avec deux exemples.
•Pour $n=41$ premier, le sous-groupe cyclique, généré par $10$, de $\mathbb{Z}/41\mathbb{Z}^*$ est $H = \{10, 10^2, 10^3, 10^4, 10^5, 10^6 \equiv 1\} = \{10, 18, 16, 37, 1 \}$.
Les classes modulo $H$ sont: $2H = {20, 36, 32, 33, 2}$, $3H = \{30, 13, 7, 29, 3 \}$, $4H = \{40, 31, 23, 25, 4 \}$, $5H = \{9, 8, 39, 21, 5 \}$, $6H = \{19, 26, 14, 17, 6 \}$, $7H = 3H$, $8H = 5H = 9H$, $10H = H$, $11H = \{28, 34, 12, 38, 11 \}$, …, $15H = \{27, 24, 35, 22, 15 \}$.
Si on calcule $\displaystyle \frac{7}{31}$, $7$ étant dans la classe d'équivalence $3H$, les restes de la division seront dans l'ordre: $7, 29, 3, 30, 13$ et retour à $7$…
Pour $\displaystyle \frac{26}{41}$, il suffit de parcourir $6H: 26, 14, 17, 6, 19$ et retour à $26$...
•Si le module est un nombre composé comme $39$, il faut lister les fractions irréductibles ayant 39 au dénominateur. L'ensemble des numérateurs sera $G = \{1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 23, 25, 28, 29, 31, 32, 34, 35, 37, 38 \}$.
Muni de la multiplication modulo $39$, G est un groupe: $\mathbb{Z}/39\mathbb{Z}^*$, de cardinal $\varphi(39)=24$.
Comme précédemment, la période du développement décimal de $\displaystyle \frac{1}{39}$ est égale à l'ordre du sous-groupe de $\mathbb{Z}/39\mathbb{Z}^*$ généré par $10$.
Puisque l'ordre d'un sous-groupe de $G$ divise l'ordre de $G$, pour un $x$ donné, la période de $\displaystyle \frac{x}{39}$ doit-être un des diviseurs de $24$: $1, 2, 3, 4, 6, 8, 12$ ou $24$ lui-même. Ce dernier est exclu puisqu'un résultat de théorie des nombres dit que $\mathbb{Z}/n\mathbb{Z}^*$ n'est pas cyclique si $n$ possède plus d'un facteur premier impair.
Un calcul montre que $10^6 \equiv 1 \pmod {39}$: l'ordre de $10$ est $6$ et le sous-groupe $H$ généré par $10$ est:
\begin{equation}
\{10, 10^2, 10^3, 10^4, 10^5, 10^6 \} \pmod {39} = \{10, 22, 25, 16, 4, 1 \}.
\end{equation}
Ce sont les restes successifs dans la division de $1$ par $39$.
$H$ étant de cardinal $6$, les $24$ restes possibles à partir desquels se reforment les $24$ fractions, se répartissent en $4$ classes d'équivalence: $H, 2H, 7H, 14H$, chacune contenant $6$ éléments.
Le nombre de ces classes, $4$, est l'indice de $H$ dans $\mathbb{Z}/39\mathbb{Z}^*$.
Enfin, il est possible de donner à cet ensemble de classes, une structure de groupe en définissant une multiplication modulo $39$.
Si on multiplie entre eux les éléments de la classe $2H$ avec les éléments de la classe $14H$: le résultat est la classe $7H$.
Ainsi, les éléments d’un groupe peuvent être des ensembles.
La conclusion de tout cela ? Les frontières entre les différentes disciplines mathématiques ne sont pas aussi nettes qu'on le croit.
L'Américain T.J. Fletcher a pour sa part mis en évidence les liens entre les développements décimaux périodiques et le mélange des cartes à jouer. Mais c'est une autre histoire.
références:
F.J. Budden-La fascination des groupes. éd: OCDL.
L. Brenton-remainder wheels and group theory.
Keith Conrad-cyclic groups.
H.Rademache et O.Toeplitz-the enjoyment of math-Princeton University Press.
...
Réponses
-
@df
Il ne sera pas dit que ton fil est ``resté veuf''. Bien d'accord avec toi qu'il y a plein de choses à faire avec l'ordre de 10 dans $(\Z/m\Z)^\times$ quand $m \wedge 10 = 1$. Tiens un témoin de cette histoire qui remonte pour moi à un certaine époque. Souvenirs, émotions ... -
Une jolie remarque due à un collègue marseillais randonneur : pourquoi $142857$ ? Parce que
\[\frac{1}{7}=\frac{7}{49}=\frac{14}{98}=\frac{14}{100}\Bigl(1-\frac{2}{100}\Bigr)^{-1}=\frac{14}{10^2}+\frac{28}{10^4}+\frac{56}{10^6}+\frac{8\times14}{10^8}+\cdots\]
et il se trouve qu'il y a une retenue, ce qui est bien normal puisque $8\times14>100$. -
Merci pour vos interventions. Ce modeste fil (inspiré toutefois par de grands noms des mathématiques comme Otto Toeplitz, un disciple de Hilbert) réunit deux traumatismes étudiants: la brave division et les ensembles d'ensembles.
Concernant ces derniers: à partir du moment où une opération en bonne et due forme a été définie entre éléments d'un ensemble, il n'y a plus vraiment de questions à se poser sur la nature de ces éléments. La psychothérapie peut attendre.
... -
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
- 52 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
In this Discussion
Qui est en ligne 3
3 Invités