Bonjour
Sur ce site j'ai trouvé le systeme suivant:
5x=4[27]
4x=3[17]
En passant par le ppcm et Bezout: x=260
J'aurai bien aimé le faire avec la méthode directe avec un tableau de congruences sans passez par le ppcm et bezout ou les restes chinois:
x
5x
modulo27
Le tableau donne: x=27
Puis le tableau suivant:
x
4x
modulo17
Le tableau donne: x=5
Et après je n'en sais rien !
Merci pour une aide.
systeme congruence
Re: systeme congruence
Déjà c'est 12 pour le premier tableau.
Et tout ce qu'on peut faire avec les tableaux c'est simplifier un peu le système, il est un peu plus simple maintenant mais pas assez pour se passer de l'idée des restes chinois (en gros t'as juste multiplié les équations par ce qu'on appelle l'inverse de 5 modulo 27, et l'inverse de 4 modulo 17; pour a et n premiers entre eux, il existe toujours un entier b (unique modulo n) tel que a*b = 1 mod n).
Si tu tiens à ne pas prononcer les mots restes chinois et Bézout, tu peux trouver a et b tels que 27a+17b=1 sans mentionner nulle part le théorème de Bézout (en remontant l'algorithme d'Euclide ou à tâtons), puis obtenir une solution du système comme dans la démonstration des restes chinois (12*17b + 5*27a).
Ensuite grâce au lemme de Gauss (ou son corollaire tu l'appelles comme tu veux) t'obtiens l'unicité de la solution modulo 27*17.
En fait c'est exactement la démonstration du théorème des restes chinois mais dans un cas particulier (qui n'a rien à envier au cas général).
Et tout ce qu'on peut faire avec les tableaux c'est simplifier un peu le système, il est un peu plus simple maintenant mais pas assez pour se passer de l'idée des restes chinois (en gros t'as juste multiplié les équations par ce qu'on appelle l'inverse de 5 modulo 27, et l'inverse de 4 modulo 17; pour a et n premiers entre eux, il existe toujours un entier b (unique modulo n) tel que a*b = 1 mod n).
Si tu tiens à ne pas prononcer les mots restes chinois et Bézout, tu peux trouver a et b tels que 27a+17b=1 sans mentionner nulle part le théorème de Bézout (en remontant l'algorithme d'Euclide ou à tâtons), puis obtenir une solution du système comme dans la démonstration des restes chinois (12*17b + 5*27a).
Ensuite grâce au lemme de Gauss (ou son corollaire tu l'appelles comme tu veux) t'obtiens l'unicité de la solution modulo 27*17.
En fait c'est exactement la démonstration du théorème des restes chinois mais dans un cas particulier (qui n'a rien à envier au cas général).
X2018
Re: systeme congruence
Merci pour ta réponse!
Au fait j'ai programmé la méthode directe sur ma calculatrice et ça marche!
Bien sûr c'est un programme " naïf " à ne pas montrer à un professionnel !
Au fait j'ai programmé la méthode directe sur ma calculatrice et ça marche!
Bien sûr c'est un programme " naïf " à ne pas montrer à un professionnel !
Re: systeme congruence
J'imagine que ton programme calcule (27k+1) mod 17 en augmentant k jusqu'à trouver 5, vu que la solution existe ça marche forcément. Cet algorithme fait un nombre d'opérations proportionnel à 17 dans le pire des cas.
Pour faire plus rapide tu peux faire un algorithme qui trouve mon a et mon b (ça s'appelle l'algorithme d'Euclide étendu) pour finalement renvoyer 12*17b + 5*27a. En s'y prenant bien on peut trouver un algorithme qui fait un nombre d'opérations proportionnel à ln(17).
Pour faire plus rapide tu peux faire un algorithme qui trouve mon a et mon b (ça s'appelle l'algorithme d'Euclide étendu) pour finalement renvoyer 12*17b + 5*27a. En s'y prenant bien on peut trouver un algorithme qui fait un nombre d'opérations proportionnel à ln(17).
X2018
Re: systeme congruence
Bonjour
5x=4[27]
4x=3[17]
Il calcule 5x modulo 27 pour x variant de 1 ppcm(27,17)
Il calcule 4x modulo 17 pour x variant de 1 ppcm(27,17)
et il s'arrête lorsque 5x=4[27] ET 4x=3[17], ce qui me donne x
Tu vois il est très lent !
Je vais essayer ce que tu m'a proposé.
5x=4[27]
4x=3[17]
Non !J'imagine que ton programme calcule (27k+1) mod 17 en augmentant k jusqu'à trouver 5, vu que la solution existe ça marche forcément. Cet algorithme fait un nombre d'opérations proportionnel à 17 dans le pire des cas.
Il calcule 5x modulo 27 pour x variant de 1 ppcm(27,17)
Il calcule 4x modulo 17 pour x variant de 1 ppcm(27,17)
et il s'arrête lorsque 5x=4[27] ET 4x=3[17], ce qui me donne x
Tu vois il est très lent !
Je vais essayer ce que tu m'a proposé.
Re: systeme congruence
Je suis désolé en fait quand je t'ai dit 12 j'ai raconté n'importe quoi c'est 17 à la place.
Puis c'est 27k+ 17 au lieu de 27k + 1 (faute de frappe).
Puis c'est 27k+ 17 au lieu de 27k + 1 (faute de frappe).
X2018
Re: systeme congruence
Bon, mon programme est lent mais il résout des systèmes de n équations, c'est l'avantage je pense.
Les équations sont de la forme: Ai = Bi [Ni]
Quelle sont les conditions à poser ?
Si pgcd(Ai,Ni) divise Bi
Y'a t-il d'autres ?
Les équations sont de la forme: Ai = Bi [Ni]
Quelle sont les conditions à poser ?
Si pgcd(Ai,Ni) divise Bi
Y'a t-il d'autres ?