11 La ecuacion lineal en ℤn\mathbb{Z}_{n}

Ejemplo III.13.

ℤ7\mathbb{Z}_{7}.

[3][x]=[4][3][x]=[4]

El inverso de [3][3] es [5][5] porque [3][5]=[15]=[1][3][5]=[15]=[1].

[5][3][x]=[5][4]⇒[1][x]=[20]⇒x=[6][5][3][x]=[5][4]\Rightarrow[1][x]=[20]\Rightarrow x=[6]

Observación III.3.

Que pasa si ℤn\mathbb{Z}_{n} no es un cuerpo?

Por ejemplo con ℤ10\mathbb{Z}_{10}, [2][x]=[3]⇒2x−3=10k⇒∄[2][x]=[3]\Rightarrow 2x-3=10k\Rightarrow\not\exists solucion.

[4]⋅[x]=[2][4]\cdot[x]=[2], [x]=[3][x]=[3] es solucion, [x]=[8][x]=[8] es solucion.

Definición III.16.

Sean n∈ℕ,n≥2n\in\mathbb{N},n\geq 2 y a,b∈ℤa,b\in\mathbb{Z}. Una ecuacion lineal modulo nn con una incognita es una expresion

ax≡b (mod n)ax\equiv b\text{ (mod }n)

donde xx es la incognita que toma valores en ℤ\mathbb{Z}.

Tambien puede expresarse como una ecuacion en ℤn\mathbb{Z}_{n}:

[a]n[x]n=[b]n[a]_{n}[x]_{n}=[b]_{n}

donde [x]n[x]_{n} es la incognita que toma valores en ℤn\mathbb{Z}_{n}.

Ejemplo III.14.
  • ​

    6x≡3(mod8)6x\equiv 3(\mathrm{mod}8)

    No tiene solucion porque no existen x y k tal que 6x−3⏟par=8k⏟par\underbrace{6x-3}_{\text{par}}=\underbrace{8k}_{\text{par}}

  • ​

    6x≡2(mod 8)6x\equiv 2(\text{mod }8)

    6⋅0=0,6⋅1=6,6⋅2=12≡4 mod 8,6⋅3=18≡2 mod 8,6⋅4=24≡0 mod 8,6⋅5=30≡7 mod 8,6⋅6=36≡4 mod 8,6⋅7=42≡2 mod 86\cdot 0=0,6\cdot 1=6,6\cdot 2=12\equiv 4\text{ mod }8,\boxed{6\cdot 3=18% \equiv 2\text{ mod }8},6\cdot 4=24\equiv 0\text{ mod }8,6\cdot 5=30\equiv 7% \text{ mod }8,6\cdot 6=36\equiv 4\text{ mod }8,\boxed{6\cdot 7=42\equiv 2\text% { mod }8}

    x=3,8x=3,8 son soluciones.

    Si me interesan las soluciones en ℤ\mathbb{Z}, hay infinitas.

    [3]=[3]=

Proposición III.15.

Sean n∈ℕ,n≥2n\in\mathbb{N},n\geq 2, a,b∈ℤa,b\in\mathbb{Z} y d=m.c.d.(a,n)d=\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(a,n).

ax≡b(mod n) tiene solucion⇔d|bax\equiv b(\text{mod }n)\text{ tiene solucion}\iff d|b
Demostración.

ax≡b mod n tiene solucion⇔∃x∈ℤ∣ax≡b mod n⇔∃x∈ℤ∣∃k∈ℤ∣ax−b=k⋅n⇔∃x∈ℤ∃k∈ℤ∣ax+n(−k)=b⇔ax\equiv b\text{ mod }n\text{ tiene solucion}\iff\exists x\in\mathbb{Z}\mid ax% \equiv b\text{ mod }n\iff\exists x\in\mathbb{Z}\mid\exists k\in\mathbb{Z}\mid ax% -b=k\cdot n\iff\exists x\in\mathbb{Z}\;\exists k\in\mathbb{Z}\mid ax+n(-k)=b\iff La ecuacion a⋅x+n⋅y=ba\cdot x+n\cdot y=b tiene solucion en ℤ\mathbb{Z} ⇔Teorema 8m.c.d.(a,n)|b\underset{\text{Teorema 8}}{\iff}\mathrm{m\mathchar 46\relax c\mathchar 46% \relax d\mathchar 46\relax}(a,n)|b ∎

Proposición III.16.

Sean n∈ℕ,n≥2,a,b∈ℤn\in\mathbb{N},n\geq 2,a,b\in\mathbb{Z} y d≡m.c.d.(a,n)d\equiv\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(a,n) tales que d|bd|b. Entonces las ecuaciones

  • ​

    ax≡b mod nax\equiv b\text{ mod }n

  • ​

    adx≡bd(mod nd)\frac{a}{d}x\equiv\frac{b}{d}(\text{mod }\frac{n}{d})

tienen el mismo conjunto de soluciones.

Demostración.

Si cc es solucion de ax≡b mod nax\equiv b\text{ mod }n ⇒ac≡b mod n⇒∃k∈ℤ∣ac−b=k⋅n⇒∃k∈ℤ∣ac−bd=k⋅nd⇒∃k∈ℤ∣adc−bd=k⋅nd(∈ℤ porque d=m.c.d.(a,n) y d|b)⇔ad⋅c≡bd mod nd⇔ k es solucion de adx≡bd mod nd\Rightarrow ac\equiv b\text{ mod }n\Rightarrow\exists k\in\mathbb{Z}\mid ac-b=% k\cdot n\Rightarrow\exists k\in\mathbb{Z}\mid\frac{ac-b}{d}=\frac{k\cdot n}{d}% \Rightarrow\exists k\in\mathbb{Z}\mid\frac{a}{d}c-\frac{b}{d}=k\cdot\frac{n}{d% }(\in\mathbb{Z}\text{ porque }d=\mathrm{m\mathchar 46\relax c\mathchar 46% \relax d\mathchar 46\relax(a,n)}\text{ y }d|b)\iff\frac{a}{d}\cdot c\equiv% \frac{b}{d}\text{ mod }\frac{n}{d}\iff\text{ k es solucion de }\frac{a}{d}x% \equiv\frac{b}{d}\text{ mod }\frac{n}{d} ∎

Lema III.3.

Sean n∈ℕ,n≥2n\in\mathbb{N},n\geq 2 y a,b,c∈ℤa,b,c\in\mathbb{Z} tales que m.c.d.(a,n)=1\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(a,n)=1. Entonces

b≡c (mod n)⇔ab≡ac (mod n)b\equiv c\text{ (mod }n)\iff ab\equiv ac\text{ (mod n)}
Demostración.

⇒)\Rightarrow) Si b≡c mod n⇒∃k∣b−c=k⋅n⇒∃k∣ab−ac=a⋅k⋅n⇒ab≡ac mod nb\equiv c\text{ mod }n\Rightarrow\exists k\mid b-c=k\cdot n\Rightarrow\exists k% \mid ab-ac=a\cdot k\cdot n\Rightarrow ab\equiv ac\text{ mod }n

⇐)\Leftarrow) Si ab≡ac mod n⇒∃k∈ℤ∣ab−ac=k⋅n⇒a(b−c)=k⋅n⇒n|a(b−c)ab\equiv ac\text{ mod }n\Rightarrow\exists k\in\mathbb{Z}\mid ab-ac=k\cdot n% \Rightarrow a(b-c)=k\cdot n\Rightarrow n|a(b-c). Por el lema de Euclides, como m.c.d.(a,n)=1\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(a,n)=1, n|b−c⇒b≡c mod nn|b-c\Rightarrow b\equiv c\text{ mod }n. ∎

Proposición III.17.

Sean n∈ℕ,n≥2n\in\mathbb{N},n\geq 2 y a,b∈ℤa,b\in\mathbb{Z} tales que m.c.d.(a,n)=1m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax(a,n)=1.

Entonces la ecuacion

ax≡b (mod n)ax\equiv b\text{ (mod }n)

tiene como solucion x=ubx=ub, donde uu es el inverso de aa modulo nn. Ademas la solucion es unica modulo nn.

Expresado en ℤn\mathbb{Z}_{n}, la ecuacion

[a][x]=[b][a][x]=[b]

tiene solucion unica, que es [x]=[a]−1[b][x]=[a]^{-1}[b]

Demostración.

ax≡b mod nax\equiv b\text{ mod }n con m.c.d.(a,n)=1\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(a,n)=1

Es lo mismo que resolver [a]n⋅[x]n=[b][a]_{n}\cdot[x]_{n}=[b]

Sabemos que [a]n[a]_{n} tiene inverso mod n porque m.c.d.(a,n)=1m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax(a,n)=1

[a]n[x]n=[b]n⇒[x]n=[b]n⋅[a]−1n[a]_{n}[x]_{n}=[b]_{n}\Rightarrow[x]_{n}=[b]_{n}\cdot[a]^{-1}_{n} ∎

Ejemplo III.15.

Calcular todas la soluciones en ℤ\mathbb{Z} de la ecuacion

59x+9≡−9+11x (mod 34)59x+9\equiv-9+11x\text{ (mod 34)}

59x−11x+9−9≡−9+11x−11x−9 mod 3459x-11x+9-9\equiv-9+11x-11x-9\text{ mod }34

48x≡−18 mod 34 48x\equiv-18\text{ mod 34 }

Reducimos los coeficientes modulo 34

14x≡16 mod 34 14x\equiv 16\text{ mod 34 }

m.c.d.(14,34)=2|16⇒Prop15∃ solucion\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(14,34)=2|% 16\overset{Prop15}{\Rightarrow}\exists\text{ solucion}

Tiene las mismas soluciones que 142x≡162 mod 342⇒7x≡8 mod 17\frac{14}{2}x\equiv\frac{16}{2}\text{ mod }\frac{34}{2}\Rightarrow 7x\equiv 8% \text{ mod }17.

m.c.d.(7,17)=1⇒7\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(7,17)=1\Rightarrow 7 es invertible modulo 17.

Para hallar el inverso de 7, buscamos una identidad de Bezout entre 7 y 17. 17=7⋅2+3,7=3⋅2+117=7\cdot 2+3,7=3\cdot 2+1.

1=7−3⋅2=7−(17−7⋅2)⋅2=7−2⋅17+4⋅7=5⋅7+(−2)⋅171=7-3\cdot 2=7-(17-7\cdot 2)\cdot 2=7-2\cdot 17+4\cdot 7=5\cdot 7+(-2)\cdot 17.

1≡5⋅7+(−2)⋅17⏟0 mod 17⇒1≡5⋅7 mod 17⇒51\equiv 5\cdot 7+(-2)\cdot\underbrace{17}_{0}\text{ mod }17\Rightarrow 1\equiv 5% \cdot 7\text{ mod }17\Rightarrow 5 es el inverso de 7 modulo 17.

En el lenguaje de bloques [5]17[7]17=[1]17[5]_{17}[7]_{17}=[1]_{17}.

[7]−117=[5]17[7]^{-1}_{17}=[5]_{17}.

Luego si tomo la ecuacion 7⋅x≡8 mod 177\cdot x\equiv 8\text{ mod }17 y multiplico por 5 a los dos lados, 5⋅7⋅x≡5⋅8 mod 17⇒x≡40 mod 175\cdot 7\cdot x\equiv 5\cdot 8\text{ mod }17\Rightarrow x\equiv 40\text{ mod }17 (lema 3 o prop 17). Produzco x≡6 mod 17x\equiv 6\text{ mod }17.

Todas las soluciones en ℤ\mathbb{Z} son x=6+17⋅kx=6+17\cdot k con k∈ℤk\in\mathbb{Z}.

Si pienso en las soluciones de [7]17⋅[x]17=[8]17[7]_{17}\cdot[x]_{17}=[8]_{17} en ℤ17\mathbb{Z}_{17} hay una unica solucion que es [x]17=[6]17[x]_{17}=[6]_{17}