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

Example 11.1.

ℤ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]

Remark 11.2.

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

Por ejemplo con ℤ10\mathbb{Z}_{10}, [2]⁢[x]=[3]⇒2⁢x−3=10⁢k⇒∄[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.

Definition 11.3.

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}.

Example 11.4.
  • •
    ​

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

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

  • •
    ​

    6⁢x≡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]=

Proposition 11.5.

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.c.d.}(a,n).

a⁢x≡b⁢(mod ⁢n)⁢ tiene solucion⇔d|bax\equiv b(\text{mod }n)\text{ tiene solucion}\iff d|b
Proof 11.6.

a⁢x≡b⁢ mod ⁢n⁢ tiene solucion⇔∃x∈ℤ∣a⁢x≡b⁢ mod ⁢n⇔∃x∈ℤ∣∃k∈ℤ∣a⁢x−b=k⋅n⇔∃x∈ℤ⁢∃k∈ℤ∣a⁢x+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 8⁢m.c.d.(a,n)|b\underset{\text{Teorema 8}}{\iff}\mathrm{m.c.d.}(a,n)|b

Proposition 11.7.

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.c.d.}(a,n) tales que d|bd|b. Entonces las ecuaciones

  • •
    ​

    a⁢x≡b⁢ mod ⁢nax\equiv b\text{ mod }n

  • •
    ​

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

tienen el mismo conjunto de soluciones.

Proof 11.8.

Si cc es solucion de a⁢x≡b⁢ mod ⁢nax\equiv b\text{ mod }n ⇒ac≡b mod n⇒∃k∈ℤ∣ac−b=k⋅n⇒∃k∈ℤ∣a⁢c−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.c.d.(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}

Lemma 11.9.

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.c.d.}(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)}
Proof 11.10.

⇒)\Rightarrow) Si b≡c⁢ mod ⁢n⇒∃k∣b−c=k⋅n⇒∃k∣a⁢b−a⁢c=a⋅k⋅n⇒a⁢b≡a⁢c⁢ 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 a⁢b≡a⁢c⁢ mod ⁢n⇒∃k∈ℤ∣a⁢b−a⁢c=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.c.d.}(a,n)=1, n|b−c⇒b≡c⁢ mod ⁢nn|b-c\Rightarrow b\equiv c\text{ mod }n.

Proposition 11.11.

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.c.d.(a,n)=1.

Entonces la ecuacion

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

tiene como solucion x=u⁢bx=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]

Proof 11.12.

a⁢x≡b⁢ mod ⁢nax\equiv b\text{ mod }n con m.c.d.(a,n)=1\mathrm{m.c.d.}(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.c.d.(a,n)=1

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

Example 11.13.

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

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

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

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

Reducimos los coeficientes modulo 34

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

m.c.d.(14,34)=2|16⁢⇒P⁢r⁢o⁢p⁢15⁢∃ solucion\mathrm{m.c.d.}(14,34)=2|16\overset{Prop15}{\Rightarrow}\exists\text{ solucion}

Tiene las mismas soluciones que 142⁢x≡162⁢ mod ⁢342⇒7⁢x≡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.c.d.}(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]17−1=[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}