Siguiente: Algoritmo de Euclides Un nivel arriba: Función de Gödel Anterior: Función de Gödel

Nociones de divisibilidad

Recordamos la relación de divisibilidad. Dados $x,y\in Z\!\!\!Z$ se dice que y divide a x, y se escribe x|y, si y sólo si $\exists z\in Z\!\!\!Z:y=zx$. Es claro que esta relación es

Reflexiva

$\forall x: x\vert x$.

Transitiva

$\forall x,y,z: (x\vert y)\land(y\vert z)\Rightarrow(x\vert z)$.

Antisimétrica

(Salvo unidades) $\forall x,y: (x\vert y)\land(y\vert x)\Rightarrow \exists r\in\{-1,1\}:y=rx.$

Consecuentemente, ``|'' es una relación de orden en el conjunto $Z\!\!\!Z^+$, que consta de los enteros estrictamente positivos. Es claro que los elementos minimales de este orden son los números primos.

Para cada $n\in Z\!\!\!Z$ el conjunto de múltiplos de n es $nZ\!\!\!Z=\{y\in Z\!\!\!Z:x\vert y\}$. Resulta que $nZ\!\!\!Z$ es un ideal de $Z\!\!\!Z$, es decir, se cumplen las propiedades siguientes:

$$\begin{array}{rrcr} & x,y\in nZ\!\!\!Z&\Rightarrow& x+y\in ... ...\!Z, & x\in nZ\!\!\!Z&\Rightarrow& tx\in nZ\!\!\!Z \end{array}$$

Dados $x,y\in Z\!\!\!Z$ decimos que ellos son congruentes módulo n, y escribimos $x\sim_n y$, si $x-y\in nZ\!\!\!Z$. Resulta, ahora, que $\sim_n$ es una relación de equivalencia. El conjunto de clases de equivalencia, o cociente, es $Z\!\!\!Z_n=\left(Z\!\!\!Z/\sim_n\right)=Z\!\!\!Z/nZ\!\!\!Z$. En consecuencia se tiene que $Z\!\!\!Z_n=\{0,1,\ldots,n-1\}$ es un anillo, pues de hecho, $Z\!\!\!Z_n$ hereda la estructura de anillo de $Z\!\!\!Z$. Si $x\sim_n y$ escribimos, como es más usual, $x\equiv y\mbox{\rm mod }n$.


Dados dos enteros $x,y\in Z\!\!\!Z$ un máximo común divisor (m.c.d.) de la pareja x,y es un supremo del conjunto de cotas inferiores de $\{x,y\}$, respecto al orden de divisibilidad. Es decir, z es un m.c.d. de x,y si

$$\begin{array}{rll} 1) & (z\vert x)\land(z\vert y) & \mbox{\r... ...w:(w\vert x)\land(w\vert y)\Rightarrow w\vert z & \end{array}$$

En tal caso escribimos $z=\mbox{\rm m.c.d.}(x,y)=(x,y).$


Dados $x,y\in Z\!\!\!Z$ el ideal generado por x,y es el conjunto de combinaciones lineales de x e y; éste es $I(x,y)=\{ax-by\vert a,b\in Z\!\!\!Z\}.$


Si w es un divisor común de x e y entonces w es también un divisor de cualquier elemento en I(x,y). Por tanto, el máximo común divisor (x,y) es el menor elemento positivo en el ideal generado por x,y. Así pues $\exists a_0,b_0\in Z\!\!\!Z:(x,y)=a_0x-b_0y$. Además esa combinación en mínima.

Siguiente: Algoritmo de Euclides Un nivel arriba: Función de Gödel Anterior: Función de Gödel