Encontrar la solución de la congruencia.

Question

Resolver la congruencia

$$4x\equiv16\mod{26}.$$

¿Cómo puedo encontrar la solución a esto? He intentado por el algoritmo de euclides, pero el mcd no es $1$, por lo que no funciona.

$$\begin{align} 26&=&6&\times4&+2\\ 4&=&2&\times2&+0 \end{align}$$

Nota: entiendo que podemos ver que $4$ $17$ son soluciones, pero ¿cómo puedo resolver esto a través de algoritmos?

Answer 1

Usted tiene que reducir los factores, en primer lugar. $26$ $4$ no son relativamente primos, pero su factor común se divide $16$, por lo que usted puede solucionar $2x\equiv 8\pmod {13}$.

Más generalmente, si usted desea solucionar $ax\equiv b\pmod{d}$, usted necesita $\gcd(a,d)$ a ser un factor de $b$ (o por el contrario que no hay soluciones) y, a continuación, divida $\gcd(a,d)$ de todos ellos para obtener una ecuación:

$$\frac{a}{\gcd(a,d)}x\equiv \frac{b}{\gcd(a,d)}\pmod{\frac{d}{\gcd(a,d)}}$$

Answer 2

Mientras que la solución de congruencias, es mejor convertir la congruencia en el algoritmo de la división de formulario y, a continuación, ir a por resolver.

$4x \equiv 16 \pmod{26} \Rightarrow 26 \: | \: 4x-16$

Finalmente se reduzca a $13 \: | \: 2(x-4) \Rightarrow 13 \: | \: (x-4)$.

Por el algoritmo de Euclides, hemos único entero $k$ tal que $x-4=13k$.

Así lo exige la solución es $\color{red}{x=13k+4} \:, \:\color{blue}{k \in \mathbb{Z}}$

Answer 3

La relación puede ser "traducido" : $$26\mid 4x-16$$ or equivalently $$4x=16+26k\text{ for }k\in\mathbb Z$$ Dividing both sides by factor $2$ results in $$2x=8+13k\text{ for }k\in\mathbb Z$$ Evidentemente habrá soluciones para $x\in\mathbb Z$ si y sólo si $k$ es incluso.

Declarando $k=2m$ lo primero que nos encontramos: $$2x=8+26m\text{ for }m\in\mathbb Z$$Dividing both sides by factor $2$ again we end up with:$$x=4+13m\text{ for }m\in\mathbb Z$$