décompostion d'une congruence

[kaderben]

Bonjour

Comment décomposer une congruence de la forme x=a[n]
Exemple:
x=4[15] (congruence) équivaut à x=1[3] et x=4[5]

Je pense bien qu'il y a des conditions sur a et n.

Je ne trouve rien sur le web !

Merci d'avance.
-----

[ansset]

pour x=c[N] la décomposition peut se faire avec tous les diviseurs de N ( sauf 1 inutile )
soit P un diviseur de N et
x=c[N]
c=c(P)[P] alors x=c(P)[P]
dans ton exemple ( je prend tes chiffres, mais on pourrait l'écrire avec des variables )
x=15k+4
diviseurs 3 et 5
x=4[15]
4=1[3] d'où x=1[3]
4=4[5] d'où x=4[5]

[gg0]

Dans l'autre sens, voir le théorème chinois.

[kaderben]

Bonjour

Oui, j'ai compris !

4=1[3] d'où x=1[3]
4=4[5] d'où x=4[5]

Dans l'autre sens, voir le théorème chinois.

Comme les modulos 3 et 5 sont premiers entre eux alors on peut appliquer le théorème des restes chinois.
C'est ce que tu voulais dire gg0 ?

[A voir en vidéo sur Futura]

[ansset]

dans l'implication que je donnais, c'est vrai pour tous les diviseurs ( premiers entre eux ou pas )
ex 15=3[12]
12=2*2*3
diviseurs : 2;3;4;6
2 et 4 ne sont pas premiers entre eux , 3 et 6 non plus.
pourtant
3=1[2] et 15=3[2]
3=0[3] et 15=0[3]
3=3[4] et 15=3[4]
3=3[6] et 15=3[6]

la proposition de gg0 est la démo de l'implication inverse , en utilisant le théorème des restes chinois.

[kaderben]

OK et merci!

Maintenant quelle est l'intérêt de casser une congruence ?
Peut être pour, résoudre un système d'équations à une inconnue, avoir des modulos premiers entre eux et appliquer le théorème des restes chinois qui est peut être pratique pour programmer ?

[gg0]

En général, on fait plutôt le contraire. Le théorème des restes chinois est très utilisé pour les maths discrètes (calcul formel, codage, cryptage, ...) car il permet de travailler sur des petits nombres tout en ayant des résultats sur des nombres très grands. Voir calcul formel par Davenport et al.

Comme c'est toi qui a décidé de parler de "casser une congruence", tu as sans doute des raisons, pourquoi poser la question ?

Cordialement.

[kaderben]

Comme c'est toi qui a décidé de parler de "casser une congruence", tu as sans doute des raisons, pourquoi poser la question ?

Oui, le but c'est d'écrire un programme pour résoudre des systèmes d'équations à une inconnue genre:ax=b[n] et cx=d[m] et etc...mais je n'est pas une méthode générale.
Comme j'ai que le niveau terminale, autodidacte,curieux, je regarde sur internet, les forums etc... pour avoir des idées et des choses que je ne comprends pas!

Toutes ses méthodes sont pour moi un peu floues et je n'arrive pas à faire un peu d'ordre dans ma tête car l'arithmétique modulaire n'est pas si simple !.

[gg0]

Oui,

mais tu as posé le problème à l'envers !!!
Si tu veux vraiment traiter ça (faire le programme, car les logiciels de calcul formel le font très facilement), étudie les bases de l'arithmétique (dans un bouquin, Internet c'est pour survoler, ou pour revoir un point particulier) et vois le théorème chinois.

NB : Ton niveau actuel n'interdit pas d'en changer. En apprenant.

[sylvainc2]

Pour résoudre un système où les moduli sont premiers entre eux (théorème des restes chinois), par exemple:
x = 2 (mod 3)
x = 3 (mod 5)
x = 2 (mod 7)

on peut résoudre chaque congruence comme ceci séparément puis on additionne les solutions partielles:

Première congruence:
on cherche un multiple de 5*7=35 qui est congru à 2 mod 3 c.a.d. on cherche x₁ = 35k₁ tel que 35k₁ = 2 mod 3
35 et 3 sont premiers entre eux donc il y a une solution. Ce sera toujours le cas puisque les moduli sont premiers entre eux:
--> k₁ = 2* 35^-1 mod 3 --> 2*2^-1 = 2*2 = 1 mod 3 donc x₁=35*1 = 35, et on ne réduit pas x₁. Tu peux vérifier que 35 est bien multiple de 5 et 7 et congru à 2 mod 3.

On fait la même chose pour les deux autres congruences:

2 - On cherche un multiple de 3*7=21 qui est congru à 3 mod 5 --> x₂ = 21 k₂ tel que 21 k₂ = 3 mod 5
--> k₂ = 3* 21^-1 mod 5 --> 3*1^-1 = 3 mod 5 donc x₂=21*3 = 63

3- 3*5 = 15: x₃ = 15 k₃ tel que 15 k₃ = 2 mod 7 --> k₃ = 2*15^-1 = 2*1 = 2 mod 7 --> x₃ = 15*2 = 30

La solution est la somme x₁+x₂+x₃ = 23 mod (3*5*7)

Donc tu vois qu'il est facile d'écrire un programme qui résoud un système de ce genre, tu a besoin d'une routine qui trouve l'inverse modulaire basé sur l'algo d'Euclide étendu par exemple et puis c'est à peu près tout.