10 La relacion de congruencia en ℤ\displaystyle\mathbb{Z}

Definición 10.1.

Sea n∈ℕ,n≥2\displaystyle n\in\mathbb{N},n\geq 2. Dados a,b∈ℤ\displaystyle a,b\in\mathbb{Z} decimos que son congruentes modulo n\displaystyle n si n|a−b\displaystyle n|a-b, es decir, si existe k∈ℤ\displaystyle k\in\mathbb{Z} tal que a−b=k⁢n\displaystyle a-b=kn. Notacion: a≡b\displaystyle a\equiv b (mod n\displaystyle n).

Proposición 10.1.

La relacion congruencia modulo n\displaystyle n es una relacion de equivalencia en ℤ\displaystyle\mathbb{Z}.

Demostración.
  1. 1.
    ​

    Reflexiva: ∀a∈ℤ⁢a≡a\displaystyle\forall a\in\mathbb{Z}\;a\equiv a mod n\displaystyle n? a−a=0=0⋅n⇒a≡a\displaystyle a-a=0=0\cdot n\Rightarrow a\equiv a mod n\displaystyle n.

  2. 2.
    ​

    Simetrica: ∀a,b∈ℤ\displaystyle\forall a,b\in\mathbb{Z} si a≡b\displaystyle a\equiv b mod n\displaystyle n ∃k∈ℤ\displaystyle\exists k\in\mathbb{Z} tal que a−b=k⋅n⇒b−a=(−k)⋅n⇒b≡a⁢ mod ⁢n\displaystyle a-b=k\cdot n\Rightarrow b-a=(-k)\cdot n\Rightarrow b\equiv a% \text{ mod }n.

  3. 3.
    ​

    Transitiva: ∀a,b,c∈ℤ\displaystyle\forall a,b,c\in\mathbb{Z}

    a≡b⁢ mod ⁢nb≡c⁢ mod ⁢n}⇒∃k,m∈ℤ∣a−b=k⋅n,b−c=m⋅n\displaystyle\begin{rcases}a\equiv b\text{ mod }n\\ b\equiv c\text{ mod }n\end{rcases}\Rightarrow\exists k,m\in\mathbb{Z}\mid a-b=% k\cdot n,b-c=m\cdot n

    Luego a−c=n⋅(k+m)\displaystyle a-c=n\cdot(k+m) ⇒a≡c⁢ mod ⁢n\displaystyle\Rightarrow a\equiv c\text{ mod }n.

∎

Ejemplo.

Congruencia modulo 6 (dibujada en la pizarra). Los numeros que estan relacionados entre si son los que estan en la misma columna. Cada columna es una clase de equivalencia de la relacion. Hay 6 clases de equivalencia. El conjunto cociente es:

ℤ/≡ mod n={[0],[1],[2],[3],[4],[5]}=ℤ6\displaystyle\mathbb{Z}/\equiv\text{ mod }n=\{[0],[1],[2],[3],[4],[5]\}=% \mathbb{Z}_{6}

[0]={…,−6,0,6,12,…}\displaystyle[0]=\{\ldots,-6,0,6,12,\ldots\} [1]={…,−5,1,7,13,…}\displaystyle[1]=\{\ldots,-5,1,7,13,\ldots\} [2]={…,−4,2,8,14,…}\displaystyle[2]=\{\ldots,-4,2,8,14,\ldots\}, …

Ejemplo.

¿Cual es la clase de 353? 353=6⋅58+5\displaystyle 353=6\cdot 58+5 ⇒[353]6=[5]6\displaystyle\Rightarrow[353]_{6}=[5]_{6} ya que 353−5=6⋅58⇒353≡5\displaystyle 353-5=6\cdot 58\Rightarrow 353\equiv 5 mod 6\displaystyle 6.

Proposición 10.2.

Sean a∈ℤ\displaystyle a\in\mathbb{Z}, n≥2\displaystyle n\geq 2 y r\displaystyle r el resto de dividir a\displaystyle a entre n\displaystyle n. Entonces se cumple

[a]n=[r]n\displaystyle[a]_{n}=[r]_{n}
Demostración.

Como a=n⋅q+r\displaystyle a=n\cdot q+r (teorema de la division), a−r=n⋅q⇒a≡r⁢ mod ⁢n⇒[a]n=[r]n\displaystyle a-r=n\cdot q\Rightarrow a\equiv r\text{ mod }n\Rightarrow[a]_{n}% =[r]_{n}. ∎

Teorema 10.1.

|ℤn|=n\displaystyle|\mathbb{Z}_{n}|=n. Es mas, ℤn={[0]n,[1]n,[2]n,…,[n−1]n}\displaystyle\mathbb{Z}_{n}=\{[0]_{n},[1]_{n},[2]_{n},\ldots,[n-1]_{n}\}

Demostración.

Dado a∈ℤ\displaystyle a\in\mathbb{Z} cualquiera por la proposicion 10 ∃r∈ℤ⁢,0≤r≤n−1\displaystyle\exists r\in\mathbb{Z},0\leq r\leq n-1 tal que

[a]n=[r]n\displaystyle[a]_{n}=[r]_{n}

Para demostrar que hay exactamente r\displaystyle r clases, tengo que demostrar que las clases [0],[1],[2],…,[n−1]\displaystyle[0],[1],[2],\ldots,[n-1] son todas distintas entre si. Supongamos que r1\displaystyle r_{1} y r2\displaystyle r_{2} son restos modulo n\displaystyle n, es decir, 0≤r1,r2≤n−1\displaystyle 0\leq r_{1},r_{2}\leq n-1 y que [r1]=[r2]\displaystyle[r_{1}]=[r_{2}]. Luego ∃k∈ℤ\displaystyle\exists k\in\mathbb{Z} tal que r1−r2=k⋅n⇒|r1−r2|⏟≤n−1=|k|⋅n\displaystyle r_{1}-r_{2}=k\cdot n\Rightarrow\underbrace{|r_{1}-r_{2}|}_{\leq n% -1}=|k|\cdot n Por ser la distancia entre 2 restos, |k|⋅n≤n−1⇒k=0⇒r1=r2\displaystyle|k|\cdot n\leq n-1\Rightarrow k=0\Rightarrow r_{1}=r_{2} ∎

Vamos a definir una suma y un producto en ℤn\displaystyle\mathbb{Z}_{n}, sumando y multiplicando representantes. Es necesario demostrar que la operacion esta bien definida:

Proposición 10.3.

Sean n∈ℕ\displaystyle n\in\mathbb{N}, n≥2\displaystyle n\geq 2 y a,b,c,d∈ℤ\displaystyle a,b,c,d\in\mathbb{Z} tales que

  •  
    ​

    [a]n=[c]n\displaystyle[a]_{n}=[c]_{n}

  •  
    ​

    [b]n=[d]n\displaystyle[b]_{n}=[d]_{n}

Entonces se cumple:

  •  
    ​

    [a+b]n=[c+d]n\displaystyle[a+b]_{n}=[c+d]_{n}

  •  
    ​

    [a⁢b]n=[c⁢d]n\displaystyle[ab]_{n}=[cd]_{n}

Demostración.

[a]=[c]⇒∃k∈ℤ\displaystyle[a]=[c]\Rightarrow\exists k\in\mathbb{Z} tal que a−c=k⋅n\displaystyle a-c=k\cdot n [b]=[d]⇒∃m∈ℤ\displaystyle[b]=[d]\Rightarrow\exists m\in\mathbb{Z} tal que b−d=m⋅n\displaystyle b-d=m\cdot n Quiero ver que [a+b]=[c+d]\displaystyle[a+b]=[c+d], es decir, que (a+b)−(c+d)\displaystyle(a+b)-(c+d) es multiplo de n\displaystyle n. (a+b)−(c+d)=(a−c)+(b−d)=k⋅n+m⋅n=(k+m)⋅n⇒[a+b]=[c+d]\displaystyle(a+b)-(c+d)=(a-c)+(b-d)=k\cdot n+m\cdot n=(k+m)\cdot n\Rightarrow% [a+b]=[c+d]. Ahora vamos a ver que [a⋅b]=[c⋅d]\displaystyle[a\cdot b]=[c\cdot d], es decir, que a⁢b−c⁢d⁢(∗)\displaystyle ab-cd(*) es multiplo de n\displaystyle n. (*) = a⁢b−a⁢d+a⁢d−c⁢d=a⁢(b−d)+(a−c)⋅d=a⋅m⋅n+k⋅n⋅d=n⁢(a⁢m+k⁢d)⇒[a⁢b]=[c⁢d]\displaystyle ab-ad+ad-cd=a(b-d)+(a-c)\cdot d=a\cdot m\cdot n+k\cdot n\cdot d=% n(am+kd)\Rightarrow[ab]=[cd] ∎

Ejemplo.

Suma y multiplicacion en ℤ6\displaystyle\mathbb{Z}_{6}:

  •  
    ​

    [2]+[5]=[2+5]=[7]=[1]\displaystyle[2]+[5]=[2+5]=[7]=[1]

  •  
    ​

    [4]⋅[5]=[4⋅5]=[20]=[2]\displaystyle[4]\cdot[5]=[4\cdot 5]=[20]=[2]

  •  
    ​

    [16]⋅[−1]=⋯=[2]\displaystyle[16]\cdot[-1]=\cdots=[2]

Definición 10.2 (Anillo).

Un anillo es una terna (A,⊕,⊗)\displaystyle(A,\oplus,\otimes) donde:

  •  
    ​

    A\displaystyle A es un conjunto no vacio.

  •  
    ​

    ⊕:A×A→A\displaystyle\oplus:A\times A\to A es una operacion interna, denominada suma.

  •  
    ​

    ⊗:A×A→A\displaystyle\otimes:A\times A\to A es una operacion interna, denominada producto.

que cumplen:

  1. 1.
    ​

    Suma asociativa: ∀a,b,c∈A⁢(a⊕b)⊕c=a⊕(b⊕c)\displaystyle\forall a,b,c\in A(a\oplus b)\oplus c=a\oplus(b\oplus c)

  2. 2.
    ​

    Existencia de neutro: ∃0A∈A\displaystyle\exists 0_{A}\in A tal que ∀a∈Aa⊕a⊕0A=0A⊕a=a\displaystyle\forall a\in A\quad a\oplus a\oplus 0_{A}=0_{A}\oplus a=a

  3. 3.
    ​

    Existencia de opuestos: ∀a∈A⁢∃b∈A\displaystyle\forall a\in A\;\exists b\in A tal que a⊕b=b⊕a=0A\displaystyle a\oplus b=b\oplus a=0_{A}

  4. 4.
    ​

    Suma conmutativa: ∀a,b∈A\displaystyle\forall a,b\in A a⊕b=b⊕a\displaystyle a\oplus b=b\oplus a

  5. 5.
    ​

    Producto asociativo: ∀a,b∈A\displaystyle\forall a,b\in A (a⊗b)⊗c=a⊗(b⊗c)\displaystyle(a\otimes b)\otimes c=a\otimes(b\otimes c)

  6. 6.
    ​

    Distributivas: ∀a,b,c∈A\displaystyle\forall a,b,c\in A a⊗(b⊕c)=(a⊗b)⊕(a⊗c)\displaystyle a\otimes(b\oplus c)=(a\otimes b)\oplus(a\otimes c) y (b⊕c)⊗a=(b⊗a)⊕(c⊗a)\displaystyle(b\oplus c)\otimes a=(b\otimes a)\oplus(c\otimes a)

Definición 10.3.

Un anillo A\displaystyle A es conmutativo si el producto ⊗\displaystyle\otimes es conmutativo.

Definición 10.4.

Un anillo A\displaystyle A es unitario o anillo con unidad si existe un netro para el producto ⊗\displaystyle\otimes distinto del neutro para la suma ⊕\displaystyle\oplus, es decir

∃1A∈A∖{0A}⁢ tal que ⁢∀a∈Aa⊗1A=1A⊗a=a\displaystyle\exists 1_{A}\in A\setminus\{0_{A}\}\text{ tal que }\forall a\in A% \quad a\otimes 1_{A}=1_{A}\otimes a=a
Definición 10.5.

Definimos en ℤn\displaystyle\mathbb{Z}_{n} una suma y un producto como:

  •  
    ​

    [a]n+[b]n=[a+b]n\displaystyle[a]_{n}+[b]_{n}=[a+b]_{n}

  •  
    ​

    [a]n⋅[b]n=[a⋅b]n\displaystyle[a]_{n}\cdot[b]_{n}=[a\cdot b]_{n}

La proposicion 11 garantiza que estas operaciones estan bien definidas

Proposición 10.4.

(ℤn,+,⋅)\displaystyle(\mathbb{Z}_{n},+,\cdot) es un anillo conmutativo con unidad.

Demostración.

Veamos que la suma es asociativa Sea [a],[b],[c]∈ℤn⇒[a]+([b]+[c])⁢=?⁢([a]+[b])+[c]\displaystyle[a],[b],[c]\in\mathbb{Z}_{n}\Rightarrow[a]+([b]+[c])\overset{?}{=% }([a]+[b])+[c]. Por definicion, [a]+([b]+[c])=[a]+[b+c]=[a+(b+c)]=[(a+b)+c]\displaystyle[a]+([b]+[c])=[a]+[b+c]=[a+(b+c)]=[(a+b)+c] porque la suma en ℤ\displaystyle\mathbb{Z} es asociativa. Es decir, la asociatividad se “hereda” de la asociatividad de la suma en ℤ\displaystyle\mathbb{Z}. Son analogas las demostraciones de que la suma y el producto son conmutativos, el producto es asociativo, y la distributiva. Se heredan de ℤ\displaystyle\mathbb{Z} y no las escribimos. Tenemos que demostrar que existe un neutro de la suma: ∀[a]∈ℤn\displaystyle\forall[a]\in\mathbb{Z}_{n} se cumple que [a]+[0]=[a]\displaystyle[a]+[0]=[a]. Luego [0]\displaystyle[0] es el neutro de la suma. Tambien, ∀[a]∈ℤn\displaystyle\forall[a]\in\mathbb{Z}_{n} tenemos [−a]∈ℤn\displaystyle[-a]\in\mathbb{Z}_{n} tal que [a]+[−a]=[0]\displaystyle[a]+[-a]=[0]. Luego [−a]\displaystyle[-a] es el opuesto de [a]\displaystyle[a]. Por otro lado ∀a∈ℤ\displaystyle\forall a\in\mathbb{Z}, [a]⁢[1]=[a]\displaystyle[a][1]=[a]. Asi, [1]\displaystyle[1] es el neutro del producto en ℤn\displaystyle\mathbb{Z}_{n}. Como cumple todas las propiedades, ℤn\displaystyle\mathbb{Z}_{n} es un anillo conmutativo unitario. ∎

Ejemplo.

ℤn\displaystyle\mathbb{Z}_{n} no es siempre un cuerpo. Por ejemplo, veamos si ℤ6\displaystyle\mathbb{Z}_{6} lo es. Tenemos que ver si existe un x∈ℤ\displaystyle x\in\mathbb{Z} tal que [2]⋅[x]=[1]\displaystyle[2]\cdot[x]=[1]. Esto es lo mismo que 2⁢x−1=6⁢x\displaystyle 2x-1=6x, pero no tiene solucion en ℤ\displaystyle\mathbb{Z}. Luego no es cierto que todos los elementos tengan inverso y por tanto no es un cuerpo. ¿Es ℤ5\displaystyle\mathbb{Z}_{5} cuerpo? [2]⋅[3]=[1]\displaystyle[2]\cdot[3]=[1], [1]⋅[1]=[1]\displaystyle[1]\cdot[1]=[1], [4]⋅[4]=[1]\displaystyle[4]\cdot[4]=[1]. Luego [1],[2],[3],[4]\displaystyle[1],[2],[3],[4] son invertibles en ℤ5⇒\displaystyle\mathbb{Z}_{5}\Rightarrow ℤ5\displaystyle\mathbb{Z}_{5} es un cuerpo

Definición 10.6.

Decimos que a∈A\displaystyle a\in A es invertible si ∃b∈A\displaystyle\exists b\in A tal que a⁢b=b⁢a=1\displaystyle ab=ba=1.

Definición 10.7.

Un cuerpo es un anillo conmutativo con unidad A\displaystyle A tal que todo elemento distinto de 0\displaystyle 0 es invertible.

Proposición 10.5.

Sea [a]n∈ℤn\displaystyle[a]_{n}\in\mathbb{Z}_{n}. Se tiene que

[a]n es invertible⇔m.c.d.(a,n)=1\displaystyle[a]_{n}\text{ es invertible}\Leftrightarrow\mathrm{m.c.d.}(a,n)=1
Demostración.

[a]n\displaystyle[a]_{n} es invertible ⇔\displaystyle\Leftrightarrow ⇒D⁢E⁢F⁢∃b∈ℤ\displaystyle\overset{DEF}{\Rightarrow}\exists b\in\mathbb{Z} tal que [a]n⋅[b]n=[1]n\displaystyle[a]_{n}\cdot[b]_{n}=[1]_{n} ⇔\displaystyle\Leftrightarrow ⇔\displaystyle\Leftrightarrow ∃b,k∈ℤ\displaystyle\exists b,k\in\mathbb{Z} tal que 1−a⁢b=k⋅n\displaystyle 1-ab=k\cdot n ⇔\displaystyle\Leftrightarrow ⇔\displaystyle\Leftrightarrow La ecuacion diofantica n⋅x+a⋅y=1\displaystyle n\cdot x+a\cdot y=1 tiene solucion en x\displaystyle x e y\displaystyle y. Por el teorema 8, tiene solucion si y solo si m.c.d.(n,a)|1⇔m.c.d.(n,a)=1\displaystyle\mathrm{m.c.d.}(n,a)|1\Leftrightarrow\mathrm{m.c.d.}(n,a)=1. Obs: Ademas, hemos dado una forma de encontrar el inverso, si existe, resolviendo una ecuacion diofantica. ∎

Ejemplo.

¿Es invertible [17]\displaystyle[17] en ℤ12\displaystyle\mathbb{Z}_{12}? En caso de que exista hallalo. m.c.d.(17,12)=1⁢⇒Prop 13⁢[17]\displaystyle\mathrm{m.c.d.}(17,12)=1\overset{\text{Prop 13}}{\Rightarrow}[17] es invertible en ℤ12\displaystyle\mathbb{Z}_{12}. [17]⁢[x]=[1]\displaystyle[17][x]=[1] 32⁢x+17⁢y=1\displaystyle 32x+17y=1. Lo resolvemos por el algoritmo extendido de Euclides: 32=17⋅1+15\displaystyle 32=17\cdot 1+15, 17=16⋅1+2\displaystyle 17=16\cdot 1+2, 15=2⋅7+1\displaystyle 15=2\cdot 7+1, 2=1⋅2\displaystyle 2=1\cdot 2. Luego 15−(17⋅15)⋅7=8⋅15−7⋅17=8⋅(32−17)−7⋅17=8⋅32−8⋅17−7⋅17=8⋅32+(−15)⋅17\displaystyle 15-(17\cdot 15)\cdot 7=8\cdot 15-7\cdot 17=8\cdot(32-17)-7\cdot 1% 7=8\cdot 32-8\cdot 17-7\cdot 17=8\cdot 32+(-15)\cdot 17 Luego [−15]\displaystyle[-15] es el inverso de [37]\displaystyle[37] en ℤ12\displaystyle\mathbb{Z}_{12}. 1=8⋅32+(−15)⋅17\displaystyle 1=8\cdot 32+(-15)\cdot 17 Id Bezout 1−(−15)⋅17=8⋅32\displaystyle 1-(-15)\cdot 17=8\cdot 32. [1]=[−15]⋅[17]=[−15⋅17]\displaystyle[1]=[-15]\cdot[17]=[-15\cdot 17] [−15]=[17]\displaystyle[-15]=[17] (−15+32=17\displaystyle-15+32=17 ), [1]=[17]⁢[17]\displaystyle[1]=[17][17].

Proposición 10.6.

ℤn\displaystyle\mathbb{Z}_{n} es cuerpo ⇔\displaystyle\Leftrightarrow n\displaystyle n es primo

Demostración.

⇐)\displaystyle\Leftarrow) n\displaystyle n es primo. Tengo que ver que [1],[2],[3],…,[n−1]\displaystyle[1],[2],[3],\ldots,[n-1] son invertibles. ∀a\displaystyle\forall a tal que 1≤a≤n−1\displaystyle 1\leq a\leq n-1 se cumple que m.c.d.(a,n)=1\displaystyle\mathrm{m.c.d.}(a,n)=1 (porque n es primo) Luego por la proposicion 13, [a]\displaystyle[a] es invertible. ⇒)\displaystyle\Rightarrow) Veamos que si ℤn\displaystyle\mathbb{Z}_{n} es un cuerpo entonces n\displaystyle n es primo. Lo demostramos por contraposicion. (n\displaystyle n compuesto ⇒ℤn\displaystyle\Rightarrow\mathbb{Z}_{n} no es un cuerpo) n\displaystyle n compuesto ⇒n=d1⋅d2\displaystyle\Rightarrow n=d_{1}\cdot d_{2} con 2≤d1,d2≤n−1\displaystyle 2\leq d_{1},d_{2}\leq n-1. Por tanto m.c.d.(n,d1)≥d1≥2⇒ℤn\displaystyle\mathrm{m.c.d.}(n,d_{1})\geq d_{1}\geq 2\Rightarrow\mathbb{Z}_{n} no es un curpo por la proposicion 13. ∎