Cómo solucionar $100x +19 =0 \pmod{23}$

Question

Cómo solucionar $100x +19 =0 \pmod{23}$,$100x=-19 \pmod{23}$ ? En general quiero saber cómo resolver los $ax=b \pmod{c}$.

Answer 1

Sugerencia de $\displaystyle\rm\,\ mod\ 23\!:\,\ x\,\equiv\, \frac{\color{color marrón}{-19}}{4\cdot \color{#0A0}{25}} \,\equiv\,\frac{\color{color marrón}4}{4\cdot\color{#0A0} 2} \,\equiv\, \frac{\color{blue}1}2 \,\equiv\, \frac{\color{blue}{24}}2 \,\equiv\, 12,\ \:$ por $\:\ \begin{array}{r}\color{brown}{{-}19\equiv 4}, & \color{blue}{1\equiv 24}\\ \color{#0A0}{25\equiv 2}\,\end{array} $

Answer 2

En primer lugar, $100=4\cdot 23+8$, lo $100\equiv 8\pmod{23}$. Entonces $$ 100x\equiv 8x\equiv -19\equiv 4\pmod{23}. $$ Desde $4$ $23$ son coprime, $4$ es invertible en $\mathbb{Z}/23\mathbb{Z}$, ($\mathbb{Z}/23\mathbb{Z}$ es en realidad un campo), por lo que multiplicando por $4^{-1}$ rendimientos $2x\equiv 1\pmod{23}$. Multiplicar ambos lados por $12$ conseguir $24x\equiv 12\pmod{23}$. Pero $24\equiv 1\pmod{23}$, lo $x\equiv 12\pmod{23}$.

Para la solución general a $ax\equiv b\pmod{c}$, es un teorema que $ax\equiv b\pmod{c}$ tiene una solución iff $d\mid b$ donde $d=\gcd(a,c)$. Cuando este es el caso, las soluciones forman una progresión aritmética con diferencia común $c/d$, para un total de $d$ soluciones modulo $c$. Usted puede leer acerca de esto por ejemplo como Teorema 2.17, página 62, de Ivan Niven de la Introducción a la Teoría de los Números en la Sección "las Soluciones a los Congruencias."

Answer 3

$$ x \equiv \frac{-19}{100} \equiv \frac{4}{100} \equiv \frac{1}{25} \equiv \frac{1}{2} \equiv \frac{ 12}{24} \equiv 12.$$

Answer 4

Un problema relacionado. El primer paso que simplificar la congruencia como $$ 100 x \equiv -19({\rm mod}\, 23) \Rightarrow 8 x \equiv 4 ({\rm mod}\, 23) \,. $$ El último de la congruencia de la siguiente manera de restar múltiplos de $23$ a partir de 100 y añadiendo $23$ $-19$que está permitido por las reglas de congruencias. Podemos simplificar el último congruencia más a

$$ 2 x \equiv 1 ({\rm mod}\, 23 ) \,.$$

desde $ {\rm gcd}(4,23) = 1 \,.$

Ahora, desde la ${\rm gcd}( 2,23 )=1 \,, $, entonces la congruencia tiene exactamente una solución (esto es un teorema) y por la inspección puede ver que $x=12$ es una solución.

Otro Enfoque

Esta es una técnica que se puede utilizar para resolver lineal de congruencias.,

si $ a x \equiv b({\rm mod}\, m) $, entonces se puede reducir a $ m y \equiv -b({\rm mod}\, a)\,.$ Si $y_0$ es una solución para la reducción de la congruencia, a continuación, $x_0$ definido por $$ x_0 = \frac{my_0+b}{a} \,.$$ es una solución de la original de la congruencia.

La aplicación de este algoritmo al problema, podemos reducir nuestra congruencia a

$$ 23 y \equiv 19({\rm mod}\, 8) \Rightarrow 7 y \equiv 3({\rm mod}\, 8)\,. $$ Ahora se puede ver por la inspección que el $y_0 = 5 $ es una solución de la última congruencia. Sustituyendo en la $$ x_0 = \frac{m y_0 + b}{a} = \frac{23.5-19 - 19}{8}= 12\,. $$

Tenga en cuenta que, puede repetir el mismo algoritmo para el último de la congruencia que se traduce en una simplificación de la congruencia. Si lo hacemos, tendremos la siguiente congruencia $$ z \equiv -3({\rm mod}\, 7) \,$$ tal que $$ y_0 = \frac{m z_0 + b}{a} \,. $$ Podemos ver por la inspección que el $z_0=4$ es una solución que implica

$$ y_0= \frac{8.4+3}{7} = 5 \,$$

que lo que tenemos delante.

Answer 5

$100x +19 =0 \pmod{23}$

$100x ≡ -19 \pmod{23}$

$92x+8x=4-23\pmod{23}$

$=>8x≡4 \pmod{23}$ dividir ambos lados por $23$ y tomando resdiues,

Por eso, $2x≡1 \pmod{23}$ dividir ambos lados por $4$, lo que es posible como $(4,23)=1,$

Ahora$\frac{23}{2}=11+\frac{1}{2}$, $23-2\cdot 11=1$

(Por favor refiérase a este y este, por el teorema de usa.)

Por eso, $2x≡23-2\cdot 11 \pmod{23}=>2x≡-22\pmod{23}$

$x≡-11\pmod{23}$ dividir ambos lados por $2$ $(2,23)=1$

$x≡-11\pmod{23}≡12\pmod{23}$

Para resolver el problema general, $ax≡b\pmod{c}$,

$d=(a,b)$ debe dividir $c$ a admitir cualquier solución(de acuerdo a este o este).

Si dividimos ambos lados por $d$, por lo que el $Ax≡B\pmod{C}$ donde $\frac{a}{A}=\frac{b}{B}=\frac{c}{C}=d$ e (a,B)=1.

El uso convergente de la propiedad de la continuación de la fracción, se pueden obtener números enteros $r,s$ tal que $rA-sB=±1$

Por ejemplo, $\frac{17}{13}=1+\frac{4}{13}=1+\frac{1}{\frac{13}{4}}=1+\frac{1}{3+\frac{1}{4}}$

Así, el convergente aquí es $1+\frac{1}{3}=\frac{4}{3}$

Así. $17\cdot 3 - 13\cdot 4$ debe $±1$ , y es $-1$.

Poner $rA-sB$ con el signo adecuado en lugar de $(1)$, $Ax≡B(1)\pmod{C}$

Un ejemplo puede ser encontrado aquí.

Por favor refiérase a esta para más detalles.