10 La relacion de congruencia en $\mathbb{Z}$

Definición III.9.

Sea $n\in\mathbb{N},n\geq 2$ . Dados $a,b\in\mathbb{Z}$ decimos que son congruentes modulo $n$ si $n|a-b$ , es decir, si existe $k\in\mathbb{Z}$ tal que $a-b=kn$ .

Notacion: $a\equiv b$ (mod $n$ ).

Proposición III.9.

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

Demostración.

1.

Reflexiva: $\forall a\in\mathbb{Z}\;a\equiv a$ mod $n$ ?

$a-a=0=0\cdot n\Rightarrow a\equiv a$ mod $n$ .
2.

Simetrica: $\forall a,b\in\mathbb{Z}$ si $a\equiv b$ mod $n$ $\exists k\in\mathbb{Z}$ tal que $a-b=k\cdot n\Rightarrow b-a=(-k)\cdot n\Rightarrow b\equiv a\text{ mod }n$ .
3.

Transitiva: $\forall a,b,c\in\mathbb{Z}$

$\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\cdot(k+m)$ $\Rightarrow a\equiv c\text{ mod }n$ .

∎

Ejemplo III.8.

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:

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

$[0]=\left\{\ldots,-6,0,6,12,\ldots\right\}$

$[1]=\left\{\ldots,-5,1,7,13,\ldots\right\}$

$[2]=\left\{\ldots,-4,2,8,14,\ldots\right\}$ , …

Ejemplo III.9.

¿Cual es la clase de 353?

$353=6\cdot 58+5$ $\Rightarrow[353]_{6}=[5]_{6}$

ya que $353-5=6\cdot 58\Rightarrow 353\equiv 5$ mod $6$ .

Proposición III.10.

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

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

Demostración.

Como $a=n\cdot q+r$ (teorema de la division), $a-r=n\cdot q\Rightarrow a\equiv r\text{ mod }n\Rightarrow[a]_{n}=[r]_{n}$ . ∎

Teorema III.9.

$|\mathbb{Z}_{n}|=n$ .

Es mas, $\mathbb{Z}_{n}=\left\{[0]_{n},[1]_{n},[2]_{n},\ldots,[n-1]_{n}\right\}$

Demostración.

Dado $a\in\mathbb{Z}$ cualquiera por la proposicion 10 $\exists r\in\mathbb{Z},0\leq r\leq n-1$ tal que

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

Para demostrar que hay exactamente $r$ clases, tengo que demostrar que las clases $[0],[1],[2],\ldots,[n-1]$ son todas distintas entre si.

Supongamos que $r_{1}$ y $r_{2}$ son restos modulo $n$ , es decir, $0\leq r_{1},r_{2}\leq n-1$ y que $[r_{1}]=[r_{2}]$ .

Luego $\exists k\in\mathbb{Z}$ tal que $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|\cdot n\leq n-1\Rightarrow k=0\Rightarrow r_{1}=r_{2}$ ∎

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

Proposición III.11.

Sean $n\in\mathbb{N}$ , $n\geq 2$ y $a,b,c,d\in\mathbb{Z}$ tales que

$[a]_{n}=[c]_{n}$
$[b]_{n}=[d]_{n}$

Entonces se cumple:

$[a+b]_{n}=[c+d]_{n}$
$[ab]_{n}=[cd]_{n}$

Demostración.

$[a]=[c]\Rightarrow\exists k\in\mathbb{Z}$ tal que $a-c=k\cdot n$

$[b]=[d]\Rightarrow\exists m\in\mathbb{Z}$ tal que $b-d=m\cdot n$

Quiero ver que $[a+b]=[c+d]$ , es decir, que $(a+b)-(c+d)$ es multiplo de $n$ .

$(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\cdot b]=[c\cdot d]$ , es decir, que $ab-cd(*)$ es multiplo de $n$ .

(*) = $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 III.10.

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

$[2]+[5]=[2+5]=[7]=[1]$
$[4]\cdot[5]=[4\cdot 5]=[20]=[2]$
$[16]\cdot[-1]=\cdots=[2]$

Definición III.10 (Anillo).

Un anillo es una terna $(A,\oplus,\otimes)$ donde:

$A$ es un conjunto no vacio.
$\oplus:A\times A\to A$ es una operacion interna, denominada suma.
$\otimes:A\times A\to A$ es una operacion interna, denominada producto.

que cumplen:

1.

Suma asociativa: $\forall a,b,c\in A(a\oplus b)\oplus c=a\oplus(b\oplus c)$
2.

Existencia de neutro: $\exists 0_{A}\in A$ tal que $\forall a\in A\quad a\oplus a\oplus 0_{A}=0_{A}\oplus a=a$
3.

Existencia de opuestos: $\forall a\in A\;\exists b\in A$ tal que $a\oplus b=b\oplus a=0_{A}$
4.

Suma conmutativa: $\forall a,b\in A$ $a\oplus b=b\oplus a$
5.

Producto asociativo: $\forall a,b\in A$ $(a\otimes b)\otimes c=a\otimes(b\otimes c)$
6.

Distributivas: $\forall a,b,c\in A$ $a\otimes(b\oplus c)=(a\otimes b)\oplus(a\otimes c)$ y $(b\oplus c)\otimes a=(b\otimes a)\oplus(c\otimes a)$

Definición III.11.

Un anillo $A$ es conmutativo si el producto $\otimes$ es conmutativo.

Definición III.12.

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

\exists 1_{A}\in A\setminus\left\{0_{A}\right\}\text{ tal que }\forall a\in A% \quad a\otimes 1_{A}=1_{A}\otimes a=a

Definición III.13.

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

$[a]_{n}+[b]_{n}=[a+b]_{n}$
$[a]_{n}\cdot[b]_{n}=[a\cdot b]_{n}$

La proposicion 11 garantiza que estas operaciones estan bien definidas

Proposición III.12.

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

Demostración.

Veamos que la suma es asociativa

Sea $[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]$ porque la suma en $\mathbb{Z}$ es asociativa.

Es decir, la asociatividad se “hereda” de la asociatividad de la suma en $\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 $\mathbb{Z}$ y no las escribimos.

Tenemos que demostrar que existe un neutro de la suma: $\forall[a]\in\mathbb{Z}_{n}$ se cumple que $[a]+[0]=[a]$ . Luego $[0]$ es el neutro de la suma.

Tambien, $\forall[a]\in\mathbb{Z}_{n}$ tenemos $[-a]\in\mathbb{Z}_{n}$ tal que $[a]+[-a]=[0]$ . Luego $[-a]$ es el opuesto de $[a]$ .

Por otro lado $\forall a\in\mathbb{Z}$ , $[a][1]=[a]$ . Asi, $[1]$ es el neutro del producto en $\mathbb{Z}_{n}$ .

Como cumple todas las propiedades, $\mathbb{Z}_{n}$ es un anillo conmutativo unitario. ∎

Ejemplo III.11.

$\mathbb{Z}_{n}$ no es siempre un cuerpo. Por ejemplo, veamos si $\mathbb{Z}_{6}$ lo es.

Tenemos que ver si existe un $x\in\mathbb{Z}$ tal que $[2]\cdot[x]=[1]$ . Esto es lo mismo que $2x-1=6x$ , pero no tiene solucion en $\mathbb{Z}$ . Luego no es cierto que todos los elementos tengan inverso y por tanto no es un cuerpo.

¿Es $\mathbb{Z}_{5}$ cuerpo?

$[2]\cdot[3]=[1]$ , $[1]\cdot[1]=[1]$ , $[4]\cdot[4]=[1]$ .

Luego $[1],[2],[3],[4]$ son invertibles en $\mathbb{Z}_{5}\Rightarrow$ $\mathbb{Z}_{5}$ es un cuerpo

Definición III.14.

Decimos que $a\in A$ es invertible si $\exists b\in A$ tal que $ab=ba=1$ .

Definición III.15.

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

Proposición III.13.

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

[a]_{n}\text{ es invertible}\iff\mathrm{m\mathchar 46\relax c\mathchar 46% \relax d\mathchar 46\relax}(a,n)=1

Demostración.

$[a]_{n}$ es invertible $\iff$ $\overset{DEF}{\Rightarrow}\exists b\in\mathbb{Z}$ tal que $[a]_{n}\cdot[b]_{n}=[1]_{n}$ $\iff$

$\iff$ $\exists b,k\in\mathbb{Z}$ tal que $1-ab=k\cdot n$ $\iff$

$\iff$ La ecuacion diofantica $n\cdot x+a\cdot y=1$ tiene solucion en $x$ e $y$ .

Por el teorema 8, tiene solucion si y solo si $\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(n,a)|1% \iff\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(n,a)=1$ .

Obs: Ademas, hemos dado una forma de encontrar el inverso, si existe, resolviendo una ecuacion diofantica. ∎

Ejemplo III.12.

¿Es invertible $[17]$ en $\mathbb{Z}_{12}$ ? En caso de que exista hallalo.

$\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(17,12)=1% \overset{\text{Prop 13}}{\Rightarrow}[17]$ es invertible en $\mathbb{Z}_{12}$ .

$[17][x]=[1]$

$32x+17y=1$ . Lo resolvemos por el algoritmo extendido de Euclides: $32=17\cdot 1+15$ , $17=16\cdot 1+2$ , $15=2\cdot 7+1$ , $2=1\cdot 2$ .

Luego $15-(17\cdot 15)\cdot 7=8\cdot 15-7\cdot 17=8\cdot(32-17)-7\cdot 17=8\cdot 32-8% \cdot 17-7\cdot 17=8\cdot 32+(-15)\cdot 17$

Luego $[-15]$ es el inverso de $[37]$ en $\mathbb{Z}_{12}$ .

$1=8\cdot 32+(-15)\cdot 17$ Id Bezout

$1-(-15)\cdot 17=8\cdot 32$ .

$[1]=[-15]\cdot[17]=[-15\cdot 17]$ $[-15]=[17]$ ( $-15+32=17$ ), $[1]=[17][17]$ .

Proposición III.14.

$\mathbb{Z}_{n}$ es cuerpo $\iff$ $n$ es primo

Demostración.

$\Leftarrow)$ $n$ es primo. Tengo que ver que $[1],[2],[3],\ldots,[n-1]$ son invertibles.

$\forall a$ tal que $1\leq a\leq n-1$ se cumple que $\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(a,n)=1$ (porque n es primo)

Luego por la proposicion 13, $[a]$ es invertible.

$\Rightarrow)$ Veamos que si $\mathbb{Z}_{n}$ es un cuerpo entonces $n$ es primo. Lo demostramos por contraposicion. ( $n$ compuesto $\Rightarrow\mathbb{Z}_{n}$ no es un cuerpo)

$n$ compuesto $\Rightarrow n=d_{1}\cdot d_{2}$ con $2\leq d_{1},d_{2}\leq n-1$ .

Por tanto $\mathrm{m\mathchar 46\relax c\mathchar 46\relax d\mathchar 46\relax}(n,d_{1})% \geq d_{1}\geq 2\Rightarrow\mathbb{Z}_{n}$ no es un curpo por la proposicion 13. ∎

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

10 La relacion de congruencia en $\mathbb{Z}$