Inscription / Connexion Nouveau Sujet
Déterminer multiple d'un nombre
Bonjour,
Sachant que "Tout nombre premier avec 10, possède au moins un multiple qui peut s'écrire qu'avec des "1" " et que la formule pour écrire un nombre qu'avec des "1" est donnée par la relation :
(10^k -1 ) / 9
Il y à t-il une façon pour déterminer le nombre s'écrivant qu'avec des "1" qui soit multiple d'un nombre donné..?
Exemple :
Le nombre 7 a pour multiple 111111.
Il y à t-il une façon pour déterminer ce multiple autre qu'une voie itérative ..?
Par exemple pour le nombre 43....?
édit Océane : forum modifié
Bonjour,
Merci @Crpediem pour le lien qui est très intéressant.
Mais je ne vois pas où il traiterait le sujet
étant donné un nombre premier p il est peut-être effectivement difficile de déterminer s'il existe un rep-unit multiple de p .... (c'est facile à montrer pour 2 et 5, et 11 !!!, pour 7 et donc 37 on peut)
par contre il est aisé de montrer que s'il en a un il en a une infinité ...
d'autre part ::
rn et rn+1 sont premiers entre eux.
si rn est premier alors n est premier. La réciproque est-elle vraie ?
...
Bonjour,
le plus petit repunit (nombre formé que de "1") multiple de n est lié à la période de la fraction 1/n
on sait que cette période est un diviseur de 
(n), l'indicateur d'Euler de n (le nombre de nombres < n et premiers avec n)
que l'on peut calculer en deux coups de cuillère à pot si on a la décomposition de n en nombres premiers.
trouver le diviseur de n qui convient, c'est à dire le plus petit k, diviseur de (n), tel que 10k 
1 modulo n, est alors un problème uniquement calculatoire (savoir calculer des puissances modulo un nombre donné "rapidement" et efficacement)
on peut par exemple sans trop de difficulté montrer que le plus petit repunit multiple de 153 est formé de 144 chiffres "1" !
poser cette division à la calculette est bien entendu impossible, mais on est sauvé par le calcul des congruences modulo 153
si n est premier c'est sans problème puisque (p), p premier, est tout simplement = p-1
une petite difficulté est soulevée si n est un multiple de 3 (n'est pas premier avec 9)
Bonsoir,
Merci pour vos réponses.
@Matafou, penses-tu finalement que l'on puisse élaborer un algorithme ( par exemple avec Maple ), qui pourrait calculer assez rapidement le plus petit répunit multiple d'un nombre PREMIER donné...?
Pourrais-tu expliciter s'il te plaît la notion de période de "1/n"...?
Pour 7 par exemple on
1/7 = 0.1428571428571429....
La période est-ce 6, c'est à dire le nombre de chiffres avant qui se répètent dans l'écriture décimale de 1/7...?
Et quel rapport avec la période..?
Si on prenait ce "grand" nombre premier, pourrais-tu trouver le repunit cherché..?? :
Nombre premier = 37975227936943673922808872755445627854565536638199
oui, la période était bien en ce sens
et la période de 1/n est le plus petit entier k tel que 10k - 1 soit divisible par n
si n est premier avec 9, on peut en déduire que (10k - 1)/9 est divisible par n
et donc que (10k - 1)/9 est le plus petit repunit divisible par n
quant à chercher ça avec de grands nombres ... bon courage
est alors un problème uniquement calculatoire (savoir calculer des puissances modulo un nombre donné "rapidement" et efficacement)
(n)...
si n est premier (que l'on va rebaptiser p pour éviter toute ambigüité) il est à fortiori (si p
3) premier avec 9 et donc pas de "subtilité" sur la relation entre la période et le repunit
le calcul de
(p) est "instantané" "par définition" : (p) = p-1
il faut donc trouver les diviseurs de p-1 ce qui avec de grands nombres est "calculatoirement difficile"
un exemple avec p = 53
on trouve bien entendu instantanément
(53) = 52 et donc un repunit multiple de 53 est le nombre formé de 52 chiffres 1 (comme souligné par carpediem il en existe une infinité)
de même un repunit multiple de ton grand nombre premier 37975227936943673922808872755445627854565536638199
est formé de 37975227936943673922808872755445627854565536638198 chiffres 1
mais la difficulté est de trouver le plus petit repunit multiple de p
avec p = 53 il s'agit donc de trouver le plus petit diviseur k de 52 tel que 10k - 1 soit multiple de 53
que l'on écrit avec les congruences 10k
1 [mod 53]
53 est suffisamment petit pour qu'on puisse calculer son inverse à la calculette (une bonne, ou un logiciel, avec 30 chiffres après la virgule)
la calculette de Windows me donne 1/53 = 0.01886792452830188679245283018868... dans lequel j'ai souligné la période, qui est donc de longueur 13.
ce qui montre que 1013 - 1 est multiple de 53 et donc le repunit formé de 13 chiffres 1 seulement est le plus petit repunit multiple de 53 :
1111111111111 = 20964360587 × 53
ici on pouvait aboutir rapidement parce que la calculette donnait instantanément la période de 1/53
si la période est plus longue et qu'on ne peut pas observer deux périodes complètes avec la calculette, cette méthode échoue
illustrons donc la méthode plus générale avec les calculs modulo 53
c'est à dire les diviseurs de 52 = 2, 4, 13 et 26 (on sait déja que 52 marche, pas la peine de le recalculer)
10² = 100
47 [mod 53] n'est pas 1
104 = (10²)²
47² 36 [mod 53] n'est pas 1
108 = (104)2
24 [mod 53]
1012 = 108 × 104
24 ×36 16 [mod 53]
1013 = 1012 × 10
16 × 10 1 [mod 53]
bingo, la période est 13
noter la façon de calculer les puissances nèmes de 10 modulo 53, aucun nombre calculé n'est plus grand que 53² = 2809
de plus comme on connait les diviseurs de 52, on ne vise que ces puissances de 10 là
et les calculs intermédiaires des puissances d'exposant une puissance de 2 (en décomposant l'exposant à calculer en binaire c'est à dire ici pour calculer 1013 on utilise 13 = 8 + 4 + 1)
évidemment faire ça avec de grands nombres revient à calculer les diviseurs de
(p) = p-1
c'est à dire de trouver les diviseurs de 37975227936943673922808872755445627854565536638198
37975227936943673922808872755445627854565536638198 =
2 x 3167 x 3613 x 587546788471 x 3263521422991 x 865417043661324529
et a donc 26 = 64 diviseurs
(obtenu par le calculateur de "alpertron" :
)
cela nécessite des méthodes puissantes et un bon paquet de chance
voir difficulté de craquer RSA, c'est pareil
les calculs de 10k modulo p nécessitent déja un logiciel adapté !!
(utilisation de nombres entiers de longueur limitée par la seule taille mémoire)
j'ai "la flemme" de faire ces calculs pour les 64 diviseurs de ce nombre là ... (bon, 62 seulement à essayer, 1 et p-1 lui-même sont inutiles, le résultat est connu d'avance)
il y a des calculateurs BigInt dans Java, et dans tous les bons logiciels de calcul...
Bonsoir,
Merci beaucoup @Matafou, c'est bien expliqué.
Juste une dernière question, pour le nombre premier 37975227936943673922808872755445627854565536638199, penses-tu que le repunit cherché pourrait être composé de plus de 10 000 chiffres "1"....?
aucune idée ...
à priori n'importe quel diviseur de p-1 est un candidat possible
et la seule façon de le savoir est d'essayer (dans l'ordre) ces diviseurs
mais on est sûr que le nombre repunit lui même étant un multiple (impair) de p qui a 50 chiffres, ce repunit possède au moins 50 chiffres !
et vu que le plus petit diviseur > 50 de p-1 est 3167, le plus petit repunit multiple de p a au moins 3167 chiffres
le trouver est faire exactement comme j'ai fait, mais avec un logiciel (un programme, parce que calculer une par une les puissances de 10 ainsi est hors de question) utilisant un package BigInt, vu la taille des nombres, puisqu'il doit calculer avec au moins 100 chiffres exacts (carré d'un nombre de 50 chiffres).
si ça se trouve ça existe même tout fait un logiciel qui calcule l'ordre de 10 (de b) modulo p, en ligne sur internet, et donc qui permet de trouver cette longueur, voire même de trouver le repunit écrit en une base b quelconque au lieu de 10 (calculs identiques de (bk - 1)/(b-1) en base b quelconque)
en tapant MultiplicativeOrder[10,37975227936943673922808872755445627854565536638199] dans la zone de saisie de Wolfram-alpha , on fait calculer ça par Mathematica,
et on obtient :
18987613968471836961404436377722813927282768319099 (juste la moitié de p-1)
qui est donc le nombre de chiffes 1 du plus petit repunit multiple de ton nombre.
comme tu le vois c'est largement plus de 10 000 chiffres 1 !!
Bonsoir,
@Matafou, vraiment merci pour ton aide !
P.S.: Autre chose qui n'a rien à voir, je monte un site, je cherche qqn pour m'aider à intégrer une partie forum dans le site..?
Voici l'adresse du site : " guimzo.free.fr "
Faut pas mettre de "www" mais juste "guimzo.free.fr"
@+
ça n'a effectivement aucun rapport avec les maths ici.
pour les forums il y a PhpBB qui parait-il n'est pas mal du tout, mais ce n'est pas le seul.
chez Free il y a un certain nombre de contraintes et je suppose que tu es au courant de toutes ces règles.
rappel au cas où : les possesseurs d'un compte page perso chez Free sont fortement conseillés de fréquenter le groupe de discussion usenet proxad.free.services.pagesperso sur le serveur de free news.free.fr, et de consulter le site les.pages.perso.chez.free.fr )
si tu ne le savais pas déja
pour l'installation de PhpBB chez Free, au besoin en demandant de l'aide et des conseils sur le groupe de discussion. (il n'y a pas que des demandes de réactivation sur ce forum, il y a aussi des "pointures" susceptibles d'aider techniquement)
et bien entendu en commençant par consulter ce que renvoie google en demandant : phpbb chez free
pour d'autres CMS (gestionnaires de sites et forums) "autorisés" avec leurs prérequis et obligations chez Free voir les.pages.perso.chez.free.fr
pour utiliser des forums "simplifiés" qui stockent les messages autrement qu'en base de donnée sql (directement en fichiers), ils sont tout simplement interdits chez Free, de même que les paramètrages qui serait trop gourmands en ressources (historiques, cache mal géré etc)
Annuler
connectez vous