1...1 divisible par 2007 — Les-mathematiques.net The most powerful custom community solution in the world

1...1 divisible par 2007

jeroMjeroM
dans Arithmétique
Bonjour
Cet exercice est très classique mais je ne vois pas du tout le cheminement.

Énoncé corrigé:
On considère le nombre : $1\cdots 1$ avec $n$ fois le chiffre 1. Montrer qu'un de ces nombres est divisible par 2007.

La méthode classique est d'utiliser le principe des tiroirs.
Je pense qu'il faut considérer les restes de 1...1 par 2007 (il y en a 2007) mais ensuite je ne vois plus.

Merci de m'aider

Réponses

  • MagnoliaMagnolia
    Déjà 1,11,111,1111 ne sont pas divisibles par 2007. Mais 11111 non plus!
  • discretdiscret
    Faudrait déjà que ce soit juste : essaie avec $n=5$ ou $n=6$, par exemple.
  • hh
    Peut-être s'agit de montrer qu'il existe un entier $n$ tel que ... Ça je sais faire de tête.
  • jeroMjeroM
    j'ai édité l'exercice
    désolé
  • hh
    Note $f(n)$ le reste de la division du nombre constitué de $n$ uns par 2007. Une première étape est de noter que cette fonction n'est pas injective, ce que tu as apparemment fait. Que peux-tu déduire ensuite du fait que $f(n)=f(m)$ pour un certain $n$ et un certain $m$ distinct de $n$ ?
  • jeroMjeroM
    Je note $U_n$ le nombre comportant $n$ fois le chiffre 1.

    En supposant que $n<m$ , on peut alors dire que $U_n$ et $U_m$ sont congrus modulo 2007, donc leur différence est divisible par 2007.

    Cette différence s'écrit plutôt comme 1...10...0 avec $n-m$ fois le chiffre 1 et $m$ le chiffre 0.

    On se sert de ce nombre ou je fais fausse piste ?
  • mpif0mpif0
    Notons $f\colon\mathbb{N}\to\mathbb{N}$, $x\mapsto 10x+1$. On remarque que $f$ passe au quotient (modulo 2007), i.e. si $x\cong y\mod 2007$ alors $f(x)\cong f(y)\mod 2007$.

    De plus $f$ est bijective modulo 2007. C'est facile à voire car ajouter 1 est bijective et comme 10 est premier à 2007 multiplier par 10 est aussi bijective.

    Si on part de 0, alors $f(0)=10\times 0+1=1$, $f(1)=10\times 1+1=11$, $f(10)=10\times 11+1=111$, etc.
    Comme $f$ est bijective modulo 2007, Les $f^n(0)\mod 2007$ forment un cycle, i.e. on fini par revenir à 0, i.e. on a $n>0$ tel que $f^n(0)=0\mod 2007$.

    Autre manière (celle suggérée): si 2007 divise 111...111000...0000, alors comme 2007 est premier à 10, il l'est à 1000...0000 et par Gauss 2007 divise 111...111.
  • hh
    Les deux preuves sont à méditer. Note en particulier la manière dont intervient à chaque fois le fait que 10 et 2007 sont premiers entre eux.
  • jeroMjeroM
    OK, 10 et 2007 sont premiers entre eux et on conclut par le théorème de Gauss

    Merci !
  • Professeur RectangleProfesseur Rectangle
    On peut en déduire un exercice plus dur.

    Exercice : Montrer que tout entier a un multiple qui ne s'écrit qu'avec des $0$ et des $1$.
  • PoirotPoirot
    Soit $k$ un entier naturel. Alors $0.k$ ne s'écrit qu'avec des $0$ et des $1$. (:D
  • Fin de partieFin de partie
    Je n'ai pas totalement compris la démonstration de Mpif:

    Si on considère l'ensemble $\{f^{(n)}(0) \mod{2007} \text{avec } n>0\}$ avec $f(x)=10x+1$ il est fini mais je ne vois pas pourquoi cet ensemble devrait contenir la classe de $0\mod{2007}$
  • Fin de partieFin de partie
    Pourtant $f(x)=10x+1 \mod{2007}$ semble bien périodique et de période $666$ ($f^{(666)}(0)\equiv 0\mod{2007}$ ) si je vois bien par calculs. B-)-

    $2007$ et $666$, maintenant vous êtes prévenus pour $2017$ X:-(
  • mpif0mpif0
    C'est lié au fait que $f$ soit bijective, toute permutation se décompose en produit de cycle.

    On a $n>m$ tels que $f^n(0)=f^m(0)\mod 2007$ du coup (en composant avec $f^{-m}$, on obtient $f^{n-m}(0)=f^{m-m}(0)=0\mod 2007$.
  • AP3AP3
    Tout entier impair non divisible par 5 a un multiple dont tous les chiffres sont 1
  • christophe cchristophe c
    fdp a écrit:
    Je n'ai pas totalement compris la démonstration de Mpif:

    A partir du moment où tu as que $1\dots 1 - 1\dots1=1\dots10\dots0 = 2007k$ multiple de 2007, comme il existe $u,v$ des entiers (relatifs) tels que $2007u+10\dots 0v=1$, tu obtiens que $1\dots 1 = 1\dots 1 \times (2007u+10\dots 0v) = $ un certain $k'$ fois $2007 + 2007k$.

    edit: pardon à toi FdP, je te réponds en faisant un edit plutôt qu'un post de plus.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Fin de partieFin de partie
    Christophe:

    Merci, mais j'avais compris le dernier message de Mpif. B-)
  • FoysFoys
    On peut en faire un exo de TD sympa:
    1) Soit $p$ premier différent de $2$ et de $5$. Montrer que pour tout $k \in \N$ il existe $n \in \N$ tel que $p$ divise $\sum_{\ell=0}^{n} 10^{k \ell}$.
    2) Soit $m$ un entier premier avec $10$. Montrer par récurrence sur le nombre de facteurs premiers de $m$ qu'il existe un multiple de $m$ qui ne s'écrit qu'avec des "$1$" en base $10$ (indication: que vaut $(\sum_{j=0}^{k-1} 10 ^j) \times (\sum_{\ell=0}^{n} 10^{k \ell})$ ?)
    3) tout entier non nul a un multiple de la forme $11111...100000...000$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • christophe cchristophe c
    foys a écrit:
    tout entier non nul a un multiple de la forme 11111...100000...000.
    PR a écrit:
    On peut en déduire un exercice plus dur**.
    Exercice : Montrer que tout entier a un multiple qui ne s'écrit qu'avec des 0 et des 1.

    Pourquoi passer par toutes ces étapes (1-2, pour foys, déclaration "dur" pour PR)? :-S .
    Pour tout n non nul, existe k et une écriture 111..100..00=111...11...1 - 111...11 = kn correcte! (C'est d'ailleurs valable pour n'importe quelle suite de chiffres, pas seulement la constante 1, et dans n'importe quelle base)

    ** :-S (j'ai dû rater un épisode ou peut-être Alzheimer me guette)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • FoysFoys
    J'avais lu trop vite les posts ci-dessus et ai voulu répondre notamment à la question de l'auteur du fil. Mais c'est vrai qu'en ajoutant les 2-3 détails manquant c'est plus rapide comme tu dis.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • solandsoland
    Bonjour.
    Encore un autre énoncé :

    Tot nombre a un multiple dont l'écriture en base 11 utilise tous les chiffres (i.e. 123...89X)
  • FoysFoys
    Spoiler
    Puisque si $u$ divise $v$ alors $u 11^k$ divise v $11^k$ il suffit de traiter le cas où l'entier $n$ est premier avec 11. puisque $n$ est inversible modulo $11$, il existe pour tout $a \in \{0,1,...,10\}$, $b \in \N$ tel que le dernier chiffre de $bn$ en base 11 est $a$ (j'identifie "X" et "10" en tant que symboles). On construit une suite par récurrence sur $k=1,...,10$ en exigeant que $a_1 \times n = 1$ mod 11 et pour tout $k>1$, si $x$ est le $k$-ième de $a_{k-1}$ en base $11$, et $y$ est choisi de sorte que $ny=k-x$, alors on pose alors $a_k=11^ky+a_{k-1}$. On vérifie par construction que $a_{10}$ se termine en base 11 par "$123456789X$" et que c'est un multiple de $n$
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • solandsoland
    J'aurais pu me rappeler que j'étais membre du club $7\times77$ (retourne ta langue $7\times77$ fois...)
  • Paul Broussous0Paul Broussous0
    C'est le genre d'exercice dont je donne souvent des variantes en TD. On peut simplement remarquer que le nombre écrit en base 10 : 11...1 (n chiffres) est la somme d'une suite géométrique. C'est donc (10^n -1)/9. A partir de là, on est ramené à résoudre une congruence : 10^n = 1 mod qqchose.
  • Mehdi PascalMehdi Pascal
    Salut,
    Sauf erreur, si 2007 divise 1+10+100+1000+...+10^n, alors n>=222
  • solandsoland
    2007 est un multiple de 9 , $(10^{222}-1)/9$ n'est pas divisible par 2007.
  • Mehdi PascalMehdi Pascal
    Linverse d'un entier x non nul, a un dévloppement décimal périodique si-si pgcd(x,10)=1.
    noton par L(x) la longeur de la periode de la partie decimale de (1/x).
    exemples:
    L(7)=6, car 1/7=0,142857 142857 142857 ...
    L(3)=1, car 1/3=0,3333333...
    on a qlq propriétés,
    1/ si x est premier, alors L(x) divise (x-1)
    exemples
    L(7)=6 divise 7-1
    L(13)=6, divise 13-1 " 1/13=0,076923 076923...
    2/ L(xn))=xn-1L(x)
    3/ si x, y distincts et xy n'est pas une puissace, alors L(xy)=PPCM(L(x),L(y))
    exemple:
    L(21)=PPCM(6,1)=6, 1/21=0,047619 047619...
    Cette partie de la partie decimale de 1/x qui ce repete infiniment, est dite un nombre de tétu, ou nombre à permutation cyclique, on l'a note par T(x)
    exemples:
    T(7)=142857, T(3)=3...

    voir par exemple Villemin gerard

    à la suite, notons par:
    Un=1+10+100+1000+...+10n
    Vn=10n-1
    alors on a:
    L(Un)=n+1
    L(Vn)=n
    xT(x)=10L(x)-1 " exemple 7*142857=999999"
    une note: aucune methode n'est connu pous savoir si L(x, premier) est maximale, c-à-d que L(x,premier)=x-1

    pour repondre à la question en prend un autre exemple, car 2007 est tres grand, soit par exemple 21=3*7
    cherchons la plus petite valeur de n, pour laquelle Un soit divisilbe par 21.
    on a: 21=3*7, alors on prend le facteur dont la longeur L est plus élévé, dans notre cas c'est 7, et T(7)=142857 on verifie que 3 divise T(7), et on a, 7T(7)=999999=9*111111, donc 21 divise 21 divise U5.

    Voilà sauf erreur, et à vous de jouer avec 2007 ou 2000007, car pour tout entier impair x il existe n, tel que x divise Un.

    pour 2007=3*3*223, j'ai verifier avec mon pc que L(223)=222, donc le plus petit n pour le quel 2007 divise Un, est n=221.

    Mehdi Pascal
    Mehdi-Pascal@hotmail.fr
  • solandsoland
    Mon logiciel dit que 2007 ne divise pas 1111.... (à 222 chiffres) :34245
  • RescassolRescassol
    Bonjour,

    Avec Pyzo (Python 3.4.1): 
    diviseur = 2007
expmin = 10
expmax = 10000
for exposant in range(expmin,expmax):
    dividende = (10 ** exposant -  1) // 9
    quotient  = dividende // diviseur
    reste     = dividende % diviseur
    if reste == 0:
        print(exposant,exposant / 666)

    Résultat d'exécution: 
    666 1.0
1332 2.0
1998 3.0
2664 4.0
3330 5.0
3996 6.0
4662 7.0
5328 8.0
5994 9.0
6660 10.0
7326 11.0
7992 12.0
8658 13.0
9324 14.0
9990 15.0

    Il semblerait qu'on ait là la liste des multiples de 666 (la bête !)

    Cordialement,

    Rescassol
  • solandsoland
    J'ai aussi ce nombre cabalistiquement innommable.
  • Mehdi PascalMehdi Pascal
    Salut,
    Je suis navrie pour cette erreur, 11111111....1 (222 fois) ne peut pas etre multiple de 9, car pour qu'il soit, il faut que 9 divise 222, ce qui n'est pas le cas, mais quand meme on peut faire une correction, disons que 2007 divise (10666-1)/9, et sauf erreur 666 est la valeur minimal.

    merci
  • GaBuZoMeuGaBuZoMeu
    Pas très surprenant : $9\times 2007= 3^4\times 223$, et $10$ est d'ordre (multiplicatif) $9$ modulo $3^4=81$. Son ordre modulo $9\times 2007$ est donc un diviseur du ppcm de $9$ et $222$, soit $666$. Et il est effectivement d'ordre $666$.
  • AP3AP3
    En fait on peut démontrer que tout nombre $N$ impair non divisible par 5 admet un multiple constitué que de 1
    via le théorème d'Euler :
    $10^{\psi(9N)} \equiv 1 (9N)$ car $9N$ et $10$ sont premiers entre eux

    et donc , aussi , l'ordre de 10 modulo $9N$ est un diviseur de $10^{\psi(9N)}$

    pour $N=2007$ cet ordre divise donc $54\times 222$ ce qui ici est moins bien que de dire cet ordre divise 666
  • solandsoland
    @ ap : Le critère le plus concis est quand-même
    "Tout nombre premier avec dix ..."
  • GaBuZoMeuGaBuZoMeu
    Pourquoi noter $\psi$ l'indicatrice d'Euler ?
  • AP3AP3
    Je préfère ne rien dire.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!