Comment résoudre le système d'équivalence modulaire avec paramètre
Compte tenu du système d'équivalences modulaires. Trouvez le plus petit paramètre naturel$a$ ce système a des solutions
$$\begin{cases} x \equiv a \mod 140\\ x \equiv 3 \mod 91\\ x \equiv 2a \mod 39 \end{cases}$$
Bien sûr, la solution sera appréciée mais si vous ne voulez pas résoudre cela, donnez-moi un indice, je ne sais même pas comment aborder ce problème
Réponses
Aucune factorisation principale des modules n'est nécessaire - seulement des gcds rapides. Par le critère de solvabilité CRT, un système est résoluble ssi il est résolu par paires ssi chaque paire est cohérente mod leurs modules pgcd. Vérifions toutes les consistances des paires. Pour la première paire$\,1,2\,$ le module pgcd est $\,(140,91) = 7\,$ alors
$\qquad\qquad\begin{align} x&\equiv a\!\!\!\pmod{\!140}\\ x&\equiv 3\!\!\!\pmod{\!91}\end{align}\,$ $\Rightarrow\, \begin{align} x&\equiv a\!\!\!\pmod{\!7}\\ x&\equiv 3\!\!\!\pmod{\!7}\end{align}\,$ $\Rightarrow\, \color{#c00}{a\equiv 3}\pmod{\!\color{#c00}{7}}$
Pour paire $\,1,3\,$ les modules pgcd $= (140,39)\!=\!1\,$il est donc toujours résoluble. Pour paire$\,2,3,\,$ exactement comme ci-dessus, nous obtenons $\bmod \color{#0a0}{13}\!=\!(91,39)\!:\,\ 2a\equiv 3\!\!\underset{\times 7\!\!}\iff \color{#0a0}a\equiv 21\equiv \color{#0a0}8.\,$ Ainsi, le système est résoluble ssi
$$\begin{align} \color{#c00}{a\equiv 3}&\!\!\pmod{\!\color{#c00}7}\\ \color{#0a0}{a\equiv 8}&\!\!\pmod{\color{#0a0}{\!13}}\end{align}\qquad\qquad$$
Avec Easy CRT, la solution est$\ a\equiv \color{#0a0}8+13\underbrace{\left[\dfrac{\color{#c00}3-\color{#0a0}8}{13}\bmod 7\right]}_{\!\!\!\large \color{#90f}{-5/(-1)}\ \bmod 7}\equiv 8+13[\color{#90f}5]\equiv 73\pmod{\!7\cdot 13}$
Remarque $ $Parce que cette méthode n'utilise que gcds (par rapport aux factorisations premières), elle peut être effectuée efficacement (à la machine ou à la main) pour des modules énormes - ce qui ne serait pas possible en utilisant des factorisations premières, car actuellement, il n'y a pas d'algorithme efficace connu pour calculer les factorisations premières, mais il y en a un pour gcds - l'algorithme euclidien.
$$x\equiv a\pmod{4,7,5}$$
$$x\equiv3\pmod{7,13}$$
$$x\equiv2a\pmod{3,13}$$
Alors, $a\equiv3\pmod7\ \ (1)$
$$2a\equiv3\pmod{13}\equiv13+3$$
$\iff a\equiv8\pmod{13} \ \ (2)$
Appliquer le théorème du reste chinois sur $(1),(2)$
Jetez un œil au théorème du reste chinois
Pour votre cas, x = 3 mod 91 = 3afin que vous puissiez voir:
3 = a mod 140
3 = 2a mod 39
D'où vous obtenez:
a = 3 + 140 * k1
a = (3 + 39 * k2 ) / 2
Maintenant, le problème semble plus simple, car il vous suffit de trouver la plus petite paire (k1, k2) pour laquelle:
3 + 140 * k1 = (3 + 39 * k2 ) / 2
En résolvant, vous pouvez obtenir:
k1 = 33
k2 = 237
a = 4623
PD: désolé pour la mise en forme, j'apprends toujours comment mon chemin
Si le système est cohérent, il a des solutions.
Depuis $140=4\cdot 5\cdot 7$ alors le premier système équivaut à $$x \equiv a \pmod {4, 5, 7}$$
et de même pour les autres congruences que nous avons $x \equiv 3 \pmod{7, 13}$ et $x\equiv 2a \pmod{3,13}$.
Dès le premier nous avons $x\equiv a \pmod{7}$ et à partir de la seconde $x\equiv 3 \pmod{7}$. Donc, pour que le système soit cohérent, nous devons avoir$a\equiv 3 \pmod{7}$.
De même à partir des deuxième et troisième congruences, nous voyons que $a$ doit aussi satisfaire $2a\equiv 3\pmod {13}.$ Puis depuis $2^{-1} \equiv 7 \pmod{7}$, on multiplie la congruence par $7$ et l'obtenir $$14a\equiv a \equiv21\equiv8 \pmod{13}$$
Ainsi, pour que le système soit cohérent, il doit satisfaire $$a\equiv 3 \pmod{7}\space(1)$$ $$a \equiv8 \pmod{13}\space(2)$$
Depuis $7$ et $13$ sont co-prime, il existe des solutions modulo $7\times13=91$par le CRT .
De $(2)$ nous savons que $a=8+13k_1$ pour $k_1\in\mathbb Z$ et la substitution dans le premier donne $$8+13k_1\equiv 3 \pmod{7}$$ $$13k_1\equiv 2 \pmod{7}$$
Alors $$13\times 6 k_1\equiv k_1\equiv 12\equiv 5 \pmod{7}$$
Donc $k_1=5+7k_2$ pour $k_2\in\mathbb Z$ et par conséquent nous avons $a=8+13k_1=8+13(5+7k_2)=73+91k_{2}.$
Par conséquent $a\equiv 73 \pmod {91}$ et le plus petit paramètre naturel de $a$ est $73$.