Forum de mathématiques - Bibm@th.net

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

répunits

Bonjour
SVP comment montrer qu'il existe toujours un répunits (en base 10) qui est divisible par a où PGCDD(10,a)=1 ?

C'est vérifié pour "a=3", c'est vérifié aussi pour "a" premier >5 ( avec petit théorème de fermat ) mais après je bloque je ne sais pas comment généraliser
Merci d'avance

Glozi

Invité

Re : répunits

Bonsoir,
Déjà un répunit s'écrit $R_n := \sum_{k=0}^{n-1} 10^k$.
Ensuite $pgcd(10,a)=1$ donc (pourquoi ce donc ?) il existe un $r>0$ tel que $10^r \equiv 1 [a]$.
Je te laisse essayer d'avancer un peu.
Bonne soirée

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonsoir et merci pour votre aide
Oui pgcd(10,a)=1 sinon le reste de division de R_n par a serait égale à 1
Ok j'essaye de continuer ; 10^r≡1[a] donc 10^r-1≡0[a] donc (10^r-1)/9≡0[a] (puisque 10^r-1≡0[9]) d'où R_n≡0[a]. C'est correct ?

Glozi

Invité

Re : répunits

Oui pgcd(10,a)=1 sinon le reste de division de R_n par a serait égale à 1

Non, on sait déjà que $pgcd(10,a)=1$, je demande d'en déduire l'existence d'un entier $r>0$ tel que $10^r \equiv 1 [a]$. Indice : penser au groupe $(\mathbb{Z}/a\mathbb{Z})^\times$.

Ok j'essaye de continuer ; 10^r≡1[a] donc 10^r-1≡0[a] donc (10^r-1)/9≡0[a] (puisque 10^r-1≡0[9]) d'où R_n≡0[a]. C'est correct ?

Non c'est incorrect, par exemple si $r=1$ et $a=9$ on a bien $10^r -1 \equiv 0 [a]$ mais pourtant $(10^r-1)/9 \not \equiv 0 [a]$. On ne peut pas diviser n'importe comment la relation de congruence.

Une fois que tu auras obtenu le $r$ demandé, compare plutôt $R_r$ modulo $a$ avec $R_{2r}-R_{r}$ modulo $a$.
Bonne soirée

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonjour et merci pour votre aide

Non, on sait déjà que $pgcd(10,a)=1$, je demande d'en déduire l'existence d'un entier $r>0$ tel que $10^r \equiv 1 [a]$. Indice : penser au groupe $(\mathbb{Z}/a\mathbb{Z})^\times$.

Oui r appartient à a classe [tex]\bar{1}[/tex] n'est ce pas ? on peut prendre en particulier r=a-1

Une fois que tu auras obtenu le $r$ demandé, compare plutôt $R_r$ modulo $a$ avec $R_{2r}-R_{r}$ modulo $a$.

OK si on prend r=a-1 on aura [tex]_{R_{r}}=\sum_{0}^{a-2}{10^{k}}[/tex] et [tex]{R_{2r}}-{R_{r}}=10^{a-1}R_{a-1}[/tex] c'est correct jusque-là ?

Glozi

Invité

Re : répunits

Bonjour,
Non, $r=a-1$ ne convient pas en général.
Exemple : $a=21$ est bien premier avec $10$ pourtant $10^{21-1}\equiv 15 [21]$, $a-1$ marcherait si $a$ est est un nombre premier ce qu'on ne suppose pas.
Je réitère mon conseille de travailler dans le groupe des inversibles $(\mathbb{Z}/a\mathbb{Z})^\times$ (ce n'est pas $r$ qui va vivre dans ce groupe mais plutôt $10$).

Ensuite tu as écris $R_{2r}-R_r = 10^rR_r$, c'est correct, mais qu'est ce que ça donne quand on regarde cette égalité modulo $a$ ?
Bonne journée

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonjour
Je crois que si r=20 on a bien R_r [tex]\equiv [/tex]1[21] puisque R_r-1 [tex]\equiv [/tex]0[3] et R_r-1 [tex]\equiv [/tex]0[7]
pour ce qui est du groupe (Z/aZ) je ne vois pas comment faire, je n'ai pas beaucoup de connaissances sur ce chapitre
Excellente journée

Glozi

Invité

Re : répunits

On parle d'un $r$ tel que $10^r \equiv 1 [a]$ je ne dis rien sur $R_r$ modulo $a$. Par ailleurs si $r=20$ alors $R_r = \sum_{k=0}^{19}10^k \equiv \sum_{k=0}^{19}1^k \equiv 20 \equiv 2[3].$ donc je ne sais pas d'où tu sors ces calculs.

Pour comprendre où je veux en venir avec $\mathbb{Z}/a\mathbb{Z}$ je propose l'exercice suivant :
On dit que $x\in \mathbb{Z}/a\mathbb{Z}$ est inversible s'il existe $y\in \mathbb{Z}/a\mathbb{Z}$ tel que $xy=1$.
On note $(\mathbb{Z}/a\mathbb{Z})^\times$ l'ensemble des éléments inversibles de $\mathbb{Z}/a\mathbb{Z}$.
Question 1 : montrer que si $n\in \mathbb{N}$ alors $\overline{n}$ est inversible si et seulement si $pgcd(a,n)=1$. (indication : utiliser la relation de Bézout)
Question 2 : montrer que si $x,y\in \mathbb{Z}/a\mathbb{Z}$ sont inversibles alors $xy$ est inversible. En déduire que $((\mathbb{Z}/a\mathbb{Z})^\times, \times)$ est un groupe (on précisera qui est l'élément neutre ?)
Question 3 : Si $x\in (\mathbb{Z}/a\mathbb{Z})^\times$, en regardant l'ensemble $\{x^n,\ |\  n\in \mathbb{N}\}$ montrer qu'il existe un $r>0$ tel que $x^r=1$ (égalité de deux élements de $(\mathbb{Z}/a\mathbb{Z})^\times$ et donc de $\mathbb{Z}/a\mathbb{Z}$).

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonjour
Je crois que si r=20 on a bien R_r [tex]\equiv [/tex]1[21] puisque R_r-1 [tex]\equiv [/tex]0[3] et R_r-1 [tex]\equiv [/tex]0[7]

En fait je voulais écrire 10^r-1 à la place de R_r
Merci pour l'exercice je vais essayer de résoudre
Merci

Glozi

Invité

Re : répunits

Toujours pas, modulo $7$ on a :
$10^{20-1} \equiv 3^{19} \equiv 3\times (3^2)^9 \equiv 3 \times 2^9 \equiv 3\times 8^3 \equiv 3\times 1^3 \equiv 3 [7]$.

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonjour, voici mon essai pour l'exercice

1-a/ [tex]\bar{n}[/tex] est inversible [tex]\Rightarrow \exists y\in Z/aZ ; \bar{n}y=1\Rightarrow \left(ak+n \right)y=1\Rightarrow \left(ky \right)a+\left(y \right)n=1\Rightarrow a\wedge n=1[/tex]
  -b/ [tex]a\wedge n=1\Rightarrow \exists \left( k,k'\right)\in Z^2 ; ak+nk'=1\Rightarrow nk'=1-ak\Rightarrow nk'\equiv 1[a]\Rightarrow \bar{n}\bar{k'}=\bar{1}\Rightarrow \bar{n}[/tex] est inversible
2-a/  [tex]x,y\in Z/aZ[/tex] sont inversibles [tex]\Rightarrow \begin{cases}
& \exists\text{ x' } \in Z/aZ; xx'=1  \\
& \exists\text{ y' } \in Z/aZ; yy'=1
\end{cases}\Rightarrow xy\left( x'y'\right)=1\Rightarrow xy[/tex] est inversible
-b/ *  [tex]\text{Soit } \bar{x},\bar{y},\bar{z}\in \left( Z/aZ\right) ;\text{on a }\bar{x}\left( \bar{y}\bar{z}\right)=\bar{x}\bar{y}\bar{z}=\left( \bar{x}\bar{y}\right)\bar{z}\Rightarrow \times \text{est associative sur}\left( Z/aZ\right)^{\times}[/tex]
     *  [tex]\forall \bar{x}\in \left( Z/aZ\right);\bar{1}\times \bar{x}=\bar{x}\times \bar{1}=\bar{x}\Rightarrow \bar{1}\text{ est l'élément neutre de}\left( Z/aZ\right)^{\times}[/tex]
    * je n'ai pas pu exprimer l'inverse
3/ une indication svp ? bien que je la trouve évidente puisque c'est répétitif et merci infiniment

Glozi

Invité

Re : répunits

1a, comment tu passes de $\overline{n}y=1$ à $(ak+n)y=1$ ? (cela est manifestement faux puisque cela impliquerait que $y=\pm 1$)
1b très bien, cependant une remarque générale : ne pas écrire des implications avec dans certaines le symbole $\exists$ et dans d'autres non, car du coup ces implications sont fausses logiquement parlant. (le plus simple est d'écrire en français avec des "il existe $k \in \mathbb{Z}$ tel que" des "donc" etc...).
2a. Oui c'est ça (même remarque sur la rédaction avec les implications).
2b. Pour justifier l'associativité il faudrait à un moment écrire $\overline{x}\times \overline{y}=\overline{xy}$. Pour l'inverse, on ne demande pas de donner son expression mais de montrer qu'il existe.
3. Indication : on peut utiliser le principe des tiroirs (et aussi remarquer que $(\mathbb{Z}/a\mathbb{Z})^\times$ est fini).

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonsoir et merci pour la correction et indications

1-a) 
[tex] \bar{n}\text{ est inversible }\Rightarrow\text{ il existe }y\in Z/aZ\text{ tel que }\bar{n}y= \bar{1}\Rightarrow ny\equiv 1[a]\Rightarrow \text{il existe }k\in Z/aZ\text{ tel que }ny=ak+1\Rightarrow n\wedge a=1\text{ d'après Bézout }[/tex][tex]\Rightarrow n\wedge a=1\text{ \left( d'après Bézout\right) }[/tex]

Dernière modification par Jiaz (25-05-2023 23:43:45)

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonjour,
Est-ce correct comme preuve et rédaction?

[tex]\text{ Soit l'ensemble }\left\{x;x^2;x^3;...x^n;... \right\}\text{ avec infinité d'éléments,
il est clair qu'il est inclus dans }\left( Z/aZ\right)[/tex]
[tex] \text{ Puisque }\left(Z/aZ \right)^{\times} \text{ est fini }\Rightarrow \text{ il existe au moins }x^k\text{ et }x^l\left( \text{ avec  }k>l\right)\text{ tel que leurs reversibles sont égaux }[/tex]
  [tex]\Rightarrow \bar{x^k}=\bar{x^l}\Rightarrow x^k\equiv x^l[a]\Rightarrow x^k-x^l\equiv 0[a]\Rightarrow x^l\left( x^{k-l}-1\right)\equiv 0[a][/tex]   
[tex] \text{ Puisque }x^l\in \left(Z/aZ \right)^{\times}\Rightarrow x\wedge a=1\Rightarrow x^{k-l}-1\equiv 0[a]\Rightarrow x^{k-l}\equiv 1[a][/tex]
[tex] \text{ Donc il suffit de prendre  }r=k-l[/tex]
Merci

Dernière modification par Jiaz (26-05-2023 12:21:04)

Glozi

Invité

Re : répunits

Bonjour,
Oui c'est ça l'idée, pour moi il y a quelques problèmes dans la rédaction :

[tex]\text{ Soit l'ensemble }\left\{x;x^2;x^3;...x^n;... \right\}\text{ avec infinité d'éléments, il est clair qu'il est inclus dans }\left( Z/aZ\right)[/tex]

On ne peut pas dire que cet ensemble a une infinité d'éléments car justement il ne possède qu'un nombre fini d'éléments. Tu peux directement invoquer le principe des tiroirs pour ttouver $x^k=x^l$. Pour le faire très proprement (ce n'est je pense pas nécéssaire sur une copie), on pose $f :\mathbb{N}\to (\mathbb{Z}/a\mathbb{Z})^\times, n\mapsto x^n$. On dit que cette application ne peut être injective sinon $(\mathbb{Z}/a\mathbb{Z})^\times$ serait infini. De la non injectivité, on trouve $k$ et $l$ que tu cherches.

tel que leurs réversibles sont égaux

J'imagine que tu voulais dire tels que $x^k=x^l$ dans $(\mathbb{Z}/a\mathbb{Z})^\times$.

[tex] \text{ Puisque }x^l\in \left(Z/aZ \right)^{\times}\Rightarrow x\wedge a=1\Rightarrow x^{k-l}-1\equiv 0[a]\Rightarrow x^{k-l}\equiv 1[a][/tex]

Là les implications (un peu mal écrites, cf le commentaire de mon message précédent) mériteraient un peu plus de détail.

Bon, on a finalement notre $r>0$ tel que $10^r \equiv 1 [a]$, formidable ! Maintenant il faut poursuivre !

Bonne journée

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : répunits

Bonjour,

Une piste peut-être plus facile à suivre :

1°) Montrer qu'il existe deux repunits différents qui ont même reste dans la division par [tex]a[/tex].
2°) Considérer la différence de ces repunits.

Glozi

Invité

Re : répunits

Bonjour,
Oui effectivement c'est beaucoup plus direct, bien vu !
Cela dit ma méthode va donner un $n$ effectif en fonction de $a$ tel que $R_n$ est divisible par $a$ (mais ce n'était pas demandé).
Bonne journée

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonsoir Glozi et merci infiniment pour vos éclaircissements et explications si précieuses
J'imagine que tu voulais dire tels que $x^k=x^l$ dans $(\mathbb{Z}/a\mathbb{Z})^\times$.

Oui c'est ce que je voulais dire

Bon, on a finalement notre $r>0$ tel que $10^r \equiv 1 [a]$, formidable ! Maintenant il faut poursuivre !

Oui j'essaye toujours mais juste une question svp concernant votre excellente idée de l'application non injective , est ce que je dois prouver la non injectivité ? par un contre exemple par exemple ou simplement on peut dire "d'après le principe de tiroirs"

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonjour,

Une piste peut-être plus facile à suivre :

1°) Montrer qu'il existe deux repunits différents qui ont même reste dans la division par [tex]a[/tex].
2°) Considérer la différence de ces repunits.

Bonsoir michel, oui je crois que c'est une très jolie piste merci beaucoup, je vais essayer de montrer l'existence de ces 2 repunits, après ça ne sera pas difficile de continuer je crois
Merci

Glozi

Invité

Re : répunits

Bonsoir,
Le principe des tiroirs c'est le résultat suivant : si $f :E \to F$ avec $card(E)>card(F)$ alors $f$ est non injective. Vois tu pourquoi ça permet de conclure ?
PS : pour un peu de culture (et aussi pour justifier plus tard l'effectivité dont je parle dans mon message précédent), le $r$ que tu trouves peut toujours être pris égal à l'ordre du groupe $(\mathbb{Z}/a\mathbb{Z})^\times$ (c'est le théorème de Lagrange). Autrement dit on peut prendre $r=\varphi(a)$ où $\varphi$ est la fonction indicatrice d'Euler. (notons que $\varphi(p)=p-1$ si $p$ est un nombre premier).
Bonne soirée

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonsoir
Voila ce que j'ai trouvé
[tex]10^r-1\equiv 0[a]\Leftrightarrow 9R_r\equiv 0[a][/tex] là est ce qu'il faut discuter selon la primalité de a avec 9 ou peut etre il faut trouver un autre répunits en fonction de r ?
Bonne soirée

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : répunits

Si c'est pour suivre la piste que je t'ai indiquée, tu te compliques inutilement la vie !
Ciombien y a-t-il de repunits ?
Combien y a-t-il de restes possibles dans la division par [tex]a[/tex] ?

Glozi

Invité

Re : répunits

Pour la piste à laquelle je pense, tu as obtenu un $r>0$ tel que $10^r\equiv 1[a]$, ensuite on compare $R_r$ et $R_{2r}-R_r$ modulo $a$ puis $R_{3r}-R_{2r}$ etc... (en déduire en fonction de $R_r$ (modulo $a$) à quoi est congru $R_{nr}$ modulo $a$ où $n$ est un entier quelconque). Il n'y aura pas besoin de discuter selon $pgcd(a,9)$.

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Si c'est pour suivre la piste que je t'ai indiquée, tu te compliques inutilement la vie !
Ciombien y a-t-il de repunits ?
Combien y a-t-il de restes possibles dans la division par [tex]a[/tex] ?

Bonsoir
Non c'etait pour Glozi, en ce qui concerne votre piste je dirai puisque y a une infinité de repunits et un nombre fini de restes dans la division par a donc d'après le principe des tiroirs y a forcément R_r et R_r' distincts tq : [tex]R_r\equiv R_{r'}[a]\Leftrightarrow R_r-R_{r'}\equiv 0[a]\Leftrightarrow 10^{r'}R_{r-r'}\equiv 0[a][/tex]
Et comme 10 et a sont premiers entre eux on aura donc [tex]R_{r-r'}\equiv 0[a][/tex]
Voila, est-ce correct ?

Jiaz

Membre

Inscription : 09-03-2023

Messages : 25

Re : répunits

Bonsoir,
OK Grozi voila ce que j'ai trouvé

[tex]\begin{cases}
&  R_{2r}-R_{r}=10^rR_{r}  \\
& R_{3r}-R_{2r}=10^{2r}R_{r}  \\
& \text{   ... }   \\
&  \text{   ... }  \\
&  R_{nr}-R_{\left( n-1\right)r}=10^{\left( n-1\right)r}R_{r} 
\end{cases}\Rightarrow \begin{cases}
& R_{2r}-R_{r}\equiv  R_{r}[a] \\
& R_{3r}-R_{2r}\equiv  R_{r}[a]  \\
& \text{ ... }   \\
& \text{ ... }   \\
& R_{nr}-R_{\left( n-1\right)r}\equiv  R_{r}[a] 
\end{cases}
[/tex]

En additionnant les congruences on aura [tex]R_{nr}-R_{r}\equiv  \left( n-1\right)R_{r}[a]\Leftrightarrow R_{nr}\equiv  nR_{r}[a][/tex]
[tex][/tex]
[tex][/tex]