Enigme Arithmétique modulaire @ Prise2Tete

nodgim · #1

Bonjour à tous.

On écrit un nombre selon ses restes modulo p, premiers successifs.
Par exemple 23=1,2,3,2,1 qui sont les restes modulo 2,3,5,7,11.
Quel est le plus petit nombre qui s'écrit 1,2,3,4,5,6,7,8,9 ?

Usage de l'informatique à éviter, mais calculette autorisée.....

Bon amusement

gwen27 · #2

On est bien sur quelque chose du genre :

x=2a+1 = 3b+2 = 5c+3 = 7d+4 = 11e+5 = 13f+6 = 17g+7 = 19h+8 = 23i+9

411 770 573 ???

snapy · #3

Au pif : 188677703 ...

nodgim · #4

C'est une bonne réponse.
Du coup Gwen est tombé trop haut, il a donné le second nombre et non le premier...

Bamby2 · #5

en progressant petit a petit j'obtiens 188677703:

on recherche le plus petit nombre satisfaisant la 1ere équation, puis on les rajoute une a une, en faisant des calculs modulo, le début donne :

1 = 1 modulo 2, ok.
puisque 2 =2 modulo 3, et que l'on cherche a obtenir 2
on doit ajouter 2*2 a 1 pour obtenir 2: 5=2 modulo3.

5 = 0 modulo 5
2*3=6=1 modulo 5
on doit arriver a 3 on doit donc ajouter 3 fois 6pour arriver a 3
donc 3*6+5 = 23.

23 = 2 modulo 7
2*3*5=30=2modulo 7
je doit atteindre 4 donc je dois ajouter 1 fois 30.
1*30+23 = 53.

53 = 9 modulo 11
2*3*5*7=210=1modulo 11
je dois arriver a 5 donc je dois ajouter 7 fois 210
7*210 +53 = 1523

etc
etc
j'obtiens alors
29243
299513
4382593
puis
188677703.

nodgim · #6

C'est une bonne réponse et c'était aussi ma méthode.

Yanyan · #7

On va utiliser le petit théorème de Fermat. Soit [latex]A_j=\prod_{i\neq j}p_{i}^{p_j-1}j[/latex] et [latex]A=\prod_i p_i[/latex] alors le reste de [latex]\sum_j A_j[/latex] par [latex]A[/latex] est la réponse.

clement.boulonne · #8

Bonjour,

Le premier nombre qui réalise ces conditions est : 188677703

Justification plus tard !

gwen27 · #9

J'avais oublié le modulo 2x3x5x7x11x13x17x19x23 ...

188677703

scarta · #10

Je dirais 188677703 (+/-223092870.k)
C'est un problème de restes chinois, mais on peut le traiter de manière différente.

Un nombre congru à 1 modulo 2 vaut 1+2k
1 est congru à 1 modulo 3, et 2 à 2: on regarde pour k=0, 1 ou 2 quelle valeur donne 1+2k modulo 3 = 2; on trouve k =2
Donc notre nombre est congru à 5 modulo 6

5 est congru à 0 modulo 5, 6 à 1; donc si 5+6k est congru à 3 modulo 5, k%5 = 3. Du coup, notre nombre vaut 23+30k

23 est congru à 2 modulo 4, et 30 à 2: pour k%7 = 1, on a 23+30k = 4 modulo 7; donc notre nombre vaut 53+210k

... et ainsi de suite

nodgim · #11

OK pour Scarta (résultat et méthode) et Clémentboulonne.

Yanyan · #12

Et moi Nodgim, c'est bon ?

nodgim · #13

Yanyan, c'est peut être bon, je ne connais pas cette facette de Fermat. Applique le et dis moi ce que ça donne en résultat, mais il me semble que Aj donne un résultat très élevé, même pour une calculette.

Yanyan · #14

Cette utilsation du petit théorème de Fermat donne un inverse formellement simple de l'inverse, [latex]a^{p-1}=1[p][/latex] donc [latex]a^{p-2}[/latex] est l'inverse de [latex]a[/latex] de modulo p. Effectivement grand quand on le relève.

Franky1103 · #15

Bonjour,
A l'aide d'une calculette, je construis mon nombre "avec fur et avec mesure" (: et mon prof de français m'engueula):
- le plus petit nombre 1 est 1,
- le plus petit nombre 1,2 est 5,
- le plus petit nombre 1,2,3 est 23,
- le plus petit nombre 1,2,3,4 est 53,
- le plus petit nombre 1,2,3,4,5 est 1 523,
- le plus petit nombre 1,2,3,4,5,6 est 29 243,
- le plus petit nombre 1,2,3,4,5,6,7 est 299 513,
- le plus petit nombre 1,2,3,4,5,6,7,8 est 4 383 593,
- le plus petit nombre 1,2,3,4,5,6,7,8,9 est 188 677 703.
Bonne journée.
Frank

L00ping007 · #16

On va faire ça à la main, alors

p=2 : reste 1
On cherche donc un nombre impair N de la forme 2k+1

p=3 : reste 2
2k+1 doit donner 2 modulo 3, donc 2k=1[3]. On a alors 2k=1+3(2n+1) (coefficient de 3 doit être impair car 2k est pair). Et finalement k=3n+2.
Le nombre N s'écrit alors 6n+5

p=5 : reste 3
6n+5 doit donner 3 modulo 5, donc n=3[5]. Finalement n=3+5k.
Le nombre N s'écrit alors 23+30k

p=7 : reste 4
23+30k doit donner 4 modulo 7, donc 2k+2=4[7], et k=1[7] : k=1+7n
Le nombre N s'écrit alors 53+210n

p=11 : reste 5
53+210n doit donner 5 modulo 11, donc 9+n=5[11], et n=7[11] : n=7+11k
Le nombre N s'écrit alors 1523+2310k

p=13 : reste 6
1523+2310k doit donner 6 modulo 13, donc 2+9k=6[13], 9k=4[13].
9k=4+13m est possible uniquement lorsque m=8+9n. On a alors k=12+13n.
Le nombre N s'écrit alors 29243+30030n

p=17 : reste 7
29243+30030n doit donner 7 modulo 17, donc 3+8n=7[17], soit 8n=4[17].
8n=4+17m n'est possible que lorsque m=4+8k. On a alors n=9+17k
Le nombre N s'écrit alors 299513+510510k

p=19 : reste 8
299513+510510k doit donner 8 modulo 19, donc 16+18k=8[19], soit 18k=11[19].
18k=11+19m n'est possible que lorsque m=7+18n. On a alors k=8+19n
Le nombre N s'écrit alors 4383593+9699690n

p=23 : reste 9
4383593+9699690n doit donner 9 modulo 23, donc 15n=9[23].
15n=9+23m n'est possible que lorsque m=12+15k. On a alors n=19+23k.
Le nombre N s'écrit alors 188677703+223092870k.

Le plus petit nombre cherché est alors N=188677703

nodgim · #17

OK pour Looping et Franky.

nodgim · #18

Merci aux participants.
Pas grand chose à ajouter, les réponses données suffisent.
Pas non plus donc de truc très efficace pour arriver plus vite au résultat.

Franky1103 · #19

Bonjour,
J'ai aussi cherché, en vain, un "truc" pour trouver le résultat plus rapidement, comme par exemple, construire la suite des nombres successifs. Mais j'ai dû me résigner, apparemment comme tout le monde, à procéder étape par étape.
La méthode de Yanyan semblait plus rapide, mais a t-elle abouti au résultat ?
Frank

nodgim · #20

Pour l'instant non, il faudrait que Yanyan nous en dise un peu plus. Je n'arrive d'ailleurs pas à appliquer sa solution concrètement.

Yanyan · #21

Ma formule est plutôt théorique mais implique l'existence d'entiers [latex]k_j[/latex] tels que [latex]\sum_j(1+k_jp_j)j[/latex] soit la solution. Le problème est de déterminer ces entiers.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 14-08-2011 10:42:25

Arithmétique mdulaire

#0 Pub

#2 - 14-08-2011 12:14:04

arithmétique modulairz

#3 - 14-08-2011 18:40:09

ariyhmétique modulaire

#4 - 14-08-2011 19:23:35

arithmétique modukaire

#5 - 14-08-2011 22:20:33

Arithmétiquee modulaire

#6 - 15-08-2011 09:37:43

Arithmétiuqe modulaire

#7 - 15-08-2011 10:16:59

Arithmétique omdulaire

#8 - 15-08-2011 15:09:38

rithmétique modulaire

#9 - 15-08-2011 15:15:55

arithlétique modulaire

#10 - 16-08-2011 08:31:15

arithmétique modulaite

#11 - 16-08-2011 11:57:23

Arithmétique odulaire

#12 - 16-08-2011 13:41:34

Arithmétique modulaiire

#13 - 16-08-2011 14:44:35

Arithmétiuqe modulaire

#14 - 16-08-2011 15:24:34

arithmétiqye modulaire

#15 - 16-08-2011 17:07:33

Arithmétique omdulaire

#16 - 16-08-2011 17:27:21

Arithmétique modularie

#17 - 17-08-2011 08:18:24

arithmérique modulaire

#18 - 17-08-2011 19:13:18

arithmétoque modulaire

#19 - 18-08-2011 10:28:21

arithmétique modulaiee

#20 - 18-08-2011 10:33:11

arithmérique modulaire

#21 - 18-08-2011 11:22:47

Arithmétiqeu modulaire

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums