Programme python avec congruence

[maze]

Bonsoir, je bloque sur un exercice sur les congruences.
Le sujet est le suivant: astérix compte les légionnaire par paquet de 7, il n'en reste pas. Obélix les compte par paquet de 8 il en reste 2. Panoramix les compte par paquet de 9 il en reste 5 et un autre personnage les comptes par paquet de 10 il en reste 8.

Pour la première question il faut donner un système avec x donc j'ai fait ça:
x congru à 0 (mod7)
x congru à 2 (mod8)
x congru à 5 (mod9)
x congru à 8 (mod10)

Mais dans la deuxième question il faut écrire un programme python qui trouve le nombre x sachant qu'il est compris entre 2000 et 6000.
Pouvez-vous me donner des pistes sur la démarche à suivre ?

[lyceen95]

Si tu devais résoudre ce problème à la main, en admettant que tu sois assez doué en calcul mental, tu ferais comment ?
Il y a différentes méthodes, tu vas bien en trouver une.
Ensuite, quand tu auras une méthode (un plan) pour résoudre ce problème, il faudra (futur lointain) le retranscrire en Python.
Mais la première étape, c'est de trouver une idée pour résoudre ce problème, à la main.
Et c'est systématique dans tout travail de programmation.

[maze]

Merci pour votre aide, j'ai fait un programme avec les conditions x%7==0, x%8==2, x%9==5 et x%10==8 et cela me donne un nombre x=4298

[lyceen95]

Ca paraît correct , mais alors, pourquoi posais-tu la question ?

Selon les compétences qu'on a en Python, il y a différentes façons de faire ce programme.

La méthode simple, qui ressemble à ce qu'on ferait dans beaucoup de langages : tester chaque nombre 1 à 1, de 2000 à 6000 , et vérifier si le nombre en question vérifient les 4 contraintes.
C'est la seule que je maîtrise bien.

Méthode 2 :
1. Créer un 'DataSet' avec tous les nombres entre 2000 et 6000 qui vérifient la 1ère contrainte.
2. Créer un 'DataSet' avec tous les nombres entre 2000 et 6000 qui vérifient la 2ème contrainte.
3. Créer un 3ème DataSet, égal à l'intersection entre les 2 premiers.
Et continuer de la même façon avec les 2 autres contraintes.

[maze]

J'avais déjà des pistes sur comment faire pour trouver le nombre mais il y avait des erreurs dans le programme python (mon niveau est vraiment pas ouf) donc je pensais que c'était une mauvaise manière de raisonner. Le fait d'essayer de le faire sans python m'a aider à comprendre où étaient les erreurs.
Pour trouver x j'ai pris les nombres de 2000 à 6000 qui remplissaient la première condition, puis la deuxième condition et ainsi de suite.

[danyL]

une optimisation est de tester non pas tous les nombres de 2000 à 6000
mais seulement de 7 en 7 puisque le nombre à trouver est un multiple de 7

le premier est 2002 = 7 * 286
et dans la boucle on incrémente de 7 le nombre à tester
cela divise par 7 le nombre de tests

[lyceen95]

Calculons ppcm(7,8,9,10), ça donne 2520.
Toutes les autres solutions de ce système à 4 équations sont les nombres 4298+2520k.
C'est à dire 1778, 4298, 6818 ... ...
Et donc, on a bien une seule solution dans l'intervalle [2000,6000]

[catamat]

Ok, je me suis amusé à retrouver ce résultats en résolvant les diverses équations diophantiennes...

Cela donne ceci :
Dans tout ce qui suit les lettres désignent des entiers relatifs.

n multiple de 7 et n congru à 2 modulo 8
est équivalent à
n=7a=8b+2
Or 7*2=8*2-2
donc par addition
7(a+2)=8(b+2)
donc d'après Gauss (a+2)
ou a+2=8c
donc n=7(8c-2)=56c-14

n congru à 5 modulo 9 et congru à 8 modulo 10
est équivalent à
n=5+9d=8+10e
ou 9d-10e=3
or 9*3-10*3=-3
donc par addition
9(d+3)-10(e+3)=0
donc 9|(e+3)
ou e+3=9f
donc n=8+10(9f-3)=90f-22

Donc si on a les quatre hypothèses
n=56c-14=90f-22
ou 56c-90f=-8
ou 28c-45f=-4
or 28*(-32)+45*20=4 (trouvé par algorithme d'Euclide)
donc par addition
28(c-32)-45(f-20)=0
donc 28|f-20
ou f-20=28g
donc n=90(28g+20)-22
soit n=2520g+1778.

Comme on raisonné par implication il faut vérifier que le résultats satisfait aux congruences demandées ce qui se fait aisément.

Donc la plus petite valeur positive possible est 1778, celle qui est dans l'intervalle choisi s'obtient pour g=1, c'est n
2520+1778 = 4298.

[catamat]

Dans mon message précédent j'ai voulu écrire 8 divise (a+2) mais on a pris cela pour un smiley, désolé...