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

Ejemplo.

ℤ7\displaystyle\mathbb{Z}_{7}. [3]⁢[x]=[4]\displaystyle[3][x]=[4] El inverso de [3]\displaystyle[3] es [5]\displaystyle[5] porque [3]⁢[5]=[15]=[1]\displaystyle[3][5]=[15]=[1]. [5]⁢[3]⁢[x]=[5]⁢[4]⇒[1]⁢[x]=[20]⇒x=[6]\displaystyle[5][3][x]=[5][4]\Rightarrow[1][x]=[20]\Rightarrow x=[6]

Observación.

Que pasa si ℤn\displaystyle\mathbb{Z}_{n} no es un cuerpo? Por ejemplo con ℤ10\displaystyle\mathbb{Z}_{10}, [2]⁢[x]=[3]⇒2⁢x−3=10⁢k⇒∄\displaystyle[2][x]=[3]\Rightarrow 2x-3=10k\Rightarrow\not\exists solucion. [4]⋅[x]=[2]\displaystyle[4]\cdot[x]=[2], [x]=[3]\displaystyle[x]=[3] es solucion, [x]=[8]\displaystyle[x]=[8] es solucion.

Definición 11.1.

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

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

donde x\displaystyle x es la incognita que toma valores en ℤ\displaystyle\mathbb{Z}. Tambien puede expresarse como una ecuacion en ℤn\displaystyle\mathbb{Z}_{n}:

[a]n⁢[x]n=[b]n\displaystyle[a]_{n}[x]_{n}=[b]_{n}

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

Ejemplo.
  •  
    ​

    6⁢x≡3⁢(mod8)\displaystyle 6x\equiv 3(\mathrm{mod}8) No tiene solucion porque no existen x y k tal que 6⁢x−3⏟par=8⁢k⏟par\displaystyle\underbrace{6x-3}_{\text{par}}=\underbrace{8k}_{\text{par}}

  •  
    ​

    6⁢x≡2⁢(mod ⁢8)\displaystyle 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 ⁢8\displaystyle 6\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,8\displaystyle x=3,8 son soluciones. Si me interesan las soluciones en ℤ\displaystyle\mathbb{Z}, hay infinitas. [3]=\displaystyle[3]=

Proposición 11.1.

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

a⁢x≡b⁢(mod ⁢n)⁢ tiene solucion⇔d|b\displaystyle ax\equiv b(\text{mod }n)\text{ tiene solucion}\Leftrightarrow d|b
Demostración.

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⇔\displaystyle ax\equiv b\text{ mod }n\text{ tiene solucion}\Leftrightarrow% \exists x\in\mathbb{Z}\mid ax\equiv b\text{ mod }n\Leftrightarrow\exists x\in% \mathbb{Z}\mid\exists k\in\mathbb{Z}\mid ax-b=k\cdot n\Leftrightarrow\exists x% \in\mathbb{Z}\;\exists k\in\mathbb{Z}\mid ax+n(-k)=b\Leftrightarrow La ecuacion a⋅x+n⋅y=b\displaystyle a\cdot x+n\cdot y=b tiene solucion en ℤ\displaystyle\mathbb{Z} ⇔Teorema 8⁢m.c.d.(a,n)|b\displaystyle\underset{\text{Teorema 8}}{\Leftrightarrow}\mathrm{m.c.d.}(a,n)|b ∎

Proposición 11.2.

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

  •  
    ​

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

  •  
    ​

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

tienen el mismo conjunto de soluciones.

Demostración.

Si c\displaystyle c es solucion de a⁢x≡b⁢ mod ⁢n\displaystyle ax\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\displaystyle\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)\Leftrightarrow\frac{a}{d}\cdot c\equiv\frac{b}{d}\text{ mod }\frac{n}{d}% \Leftrightarrow\text{ k es solucion de }\frac{a}{d}x\equiv\frac{b}{d}\text{ % mod }\frac{n}{d} ∎

Lema 11.1.

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

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

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

Proposición 11.3.

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

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

tiene como solucion x=u⁢b\displaystyle x=ub, donde u\displaystyle u es el inverso de a\displaystyle a modulo n\displaystyle n. Ademas la solucion es unica modulo n\displaystyle n. Expresado en ℤn\displaystyle\mathbb{Z}_{n}, la ecuacion

[a]⁢[x]=[b]\displaystyle[a][x]=[b]

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

Demostración.

a⁢x≡b⁢ mod ⁢n\displaystyle ax\equiv b\text{ mod }n con m.c.d.(a,n)=1\displaystyle\mathrm{m.c.d.}(a,n)=1 Es lo mismo que resolver [a]n⋅[x]n=[b]\displaystyle[a]_{n}\cdot[x]_{n}=[b] Sabemos que [a]n\displaystyle[a]_{n} tiene inverso mod n porque m.c.d.(a,n)=1\displaystyle m.c.d.(a,n)=1 [a]n⁢[x]n=[b]n⇒[x]n=[b]n⋅[a]n−1\displaystyle[a]_{n}[x]_{n}=[b]_{n}\Rightarrow[x]_{n}=[b]_{n}\cdot[a]^{-1}_{n} ∎

Ejemplo.

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

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

59⁢x−11⁢x+9−9≡−9+11⁢x−11⁢x−9⁢ mod ⁢34\displaystyle 59x-11x+9-9\equiv-9+11x-11x-9\text{ mod }34 48⁢x≡−18⁢ mod 34 \displaystyle 48x\equiv-18\text{ mod 34 } Reducimos los coeficientes modulo 34 14⁢x≡16⁢ mod 34 \displaystyle 14x\equiv 16\text{ mod 34 } m.c.d.(14,34)=2|16⁢⇒P⁢r⁢o⁢p⁢15⁢∃ solucion\displaystyle\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\displaystyle\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\displaystyle\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+1\displaystyle 17=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)⋅17\displaystyle 1=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⇒5\displaystyle 1\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\displaystyle[5]_{17}[7]_{17}=[1]_{17}. [7]17−1=[5]17\displaystyle[7]^{-1}_{17}=[5]_{17}. Luego si tomo la ecuacion 7⋅x≡8⁢ mod ⁢17\displaystyle 7\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 ⁢17\displaystyle 5\cdot 7\cdot x\equiv 5\cdot 8\text{ mod }17\Rightarrow x\equiv 4% 0\text{ mod }17 (lema 3 o prop 17). Produzco x≡6⁢ mod ⁢17\displaystyle x\equiv 6\text{ mod }17. Todas las soluciones en ℤ\displaystyle\mathbb{Z} son x=6+17⋅k\displaystyle x=6+17\cdot k con k∈ℤ\displaystyle k\in\mathbb{Z}. Si pienso en las soluciones de [7]17⋅[x]17=[8]17\displaystyle[7]_{17}\cdot[x]_{17}=[8]_{17} en ℤ17\displaystyle\mathbb{Z}_{17} hay una unica solucion que es [x]17=[6]17\displaystyle[x]_{17}=[6]_{17}