2.1: Lema de Bézout

Definición 2.1

El piso de un número real\(\theta\) se define de la siguiente manera:\(\lfloor \theta \rfloor\) es el mayor entero menor que o igual a\(\theta\). La parte fraccionaria\(\{\theta\}\) del número\(\theta\) se define como\(\theta-\lfloor \theta \rfloor\). De igual manera, el techo de\(\theta\)\(\lceil \theta \rceil\),, da el entero más pequeño mayor o igual a\(\theta\).

Por el principio bien ordenado, Corolario 1.8, el número\(\lfloor \theta \rfloor\) y\(\lceil \theta \rceil\) existir para cualquiera\(\theta \in \mathbb{R}\).

Definición 2.2

Dado un número\(\xi \in \mathbb{R}\), denotamos su norma (o valor absoluto)\(|\xi|\) por\(N(\xi)\).

Esta última definición parece torpe e innecesaria en el contexto actual. Pero nos ahorrará muchos problemas más adelante (ver Sección?? ).

Lema 2.3

Dado\(r_{1}\) y\(r_{2}\) con\(r_{2} > 0\), entonces hay únicos\(q_{2}\) y\(r_{3} \ge 0\) con\(N(r_{3}) < N(r_{2})\) tal que\(r_{1} = r_{2}q_{2}+r_{3}\).

Prueba

Señalando que\(\frac{r_{1}}{r_{2}}\) es un número racional, podemos elegir el entero\(q_{2} = \lfloor \frac{r_{1}}{r_{2}} \rfloor\) para que

\[\frac{r_{1}}{r_{2}} = q_{2}+\epsilon \nonumber\]

donde\(\epsilon \in [0, 1)\). El entero\(q_{2}\) se llama cociente. Multiplicar por\(r_{2}\) da el resultado.

Tenga en cuenta que\(r_{3} \in \{0, \cdots, r_{2}-1\}\). Así, entre otras cosas, este lema implica que cada entero tiene un residuo único (ver Definición 1.6). Si\(N(r_{1}) < N(r_{2})\), entonces\(q_{2} = 0\). En este caso,\(\epsilon = \frac{r_{1}}{r_{2}}\) y no aprendemos nada nuevo. Pero si\(N(r_{1}) > N(r_{2})\), entonces\(q_{2} \ne 0\) y hemos escrito\(r_{1}\) como múltiplo de\(r_{2}\) más un resto\(r_{3}\).

Definición 2.4

Dado\(r_{1}\) y\(r_{2}\) con\(r_{2} > 0\), el cálculo\(q_{2}\) y\(r_{3}\) satisfacción de Lemma 2.3 se llama algoritmo de división. Tenga en cuenta que\(r_{3} = \mbox{Res}_{r_{2}} (r_{1})\).

Teorema 2.5 (Lema de Bezout)

Dejar\(a\) y\(b\) ser tal que\(\gcd (a,b) = d\). Entonces\(ax+by = c\) tiene soluciones enteras para\(x\) y\(y\) si y solo si\(c\) es un múltiplo de\(d\).

Prueba

Dejar\(S\) y\(ν(S)\) ser los conjuntos:

\[S = \{ax+by |x, y \in \mathbb{Z}, ax+by \ne 0\} \nonumber\].

\[ν(S) = \{N(s) |s \in S\} \subseteq \mathbb{N} \nonumber\]

Entonces\(ν(S) \ne 0\) y se delimita desde abajo. Así, por el principio bien ordenado de\(\mathbb{N}\), tiene un elemento más pequeño\(e\). Entonces hay un elemento\(d \in S\) que tiene esa norma:\(N(d) = e\).

Para ello\(d\), utilizamos el algoritmo de división para establecer que hay\(q\) y\(r \ge 0\) tal que

\[\begin{array}{ccc} {a = qd+r}&{and}&{N(r) < N(d)} \end{array} \nonumber\]

Ahora suplente\(d = ax+by\). Un breve cálculo muestra que se\(r\) puede reescribir como:

\[r = a(1-qx)+b(qy) \nonumber\]

Esto demuestra que\(r \in S\). Pero también sabemos por (2.1) que\(N(r)\) es menor que\(N(d)\). A menos que\(r = 0\) esto sea una contradicción por que\(d\) se defina la forma. Pero\(r = 0\) implica que\(d\) es un divisor de\(a\). El mismo argumento muestra que también\(d\) es un divisor de\(b\). Así\(d\) es un divisor común de ambos\(a\) y\(b\).

Ahora dejemos\(e\) ser cualquier divisor de ambos\(a\) y\(b\). Entonces\(e | (ax+by)\), y así\(e|d\). Pero si\(e|d\), entonces\(N(e)\) debe ser menor o igual a\(N(d)\). Por lo tanto,\(d\) es el mayor divisor común de ambos\(a\) y\(b\).

Al multiplicar\(x\) y\(y\) por\(f\), logramos eso por cualquier múltiplo\(fd\) de\(d\) ese

\[afx+bfy = fd \nonumber\]

Por otro lado, seamos como\(d\) se definió anteriormente y supongamos que\(x, y\), y\(c\) son tales que

\[ax+by = c \nonumber\]

Ya que\(d\) divide\(a\) y\(b\), debemos tener eso\(d|c\), y así\(c\) debe ser un múltiplo de d.