C: Teoría elemental de números
- Page ID
- 118500
Aquí revisamos algunas definiciones teóricas básicas de números y resultados. En su mayor parte, nos limitaremos a exponer los resultados. Para un tratamiento más detallado, al alumno se le remiten referencias, o se le dan en la bibliografía. A menos que se indique lo contrario en este apéndice, todas las letras minúsculas\(a\)\(b\)\(c\),,,, etc. serán números enteros. Recordemos que usamos\(\mathbb{N}\) para denotar el conjunto de números naturales (también conocidos como los enteros positivos) y usamos\(\mathbb{Z}\) para denotar el conjunto de todos los enteros, es decir,\[\nonumber \mathbb{N}= \{ 1,2,3, \dots \}\] y\[\nonumber \mathbb{Z}= \{ \dots, -3,-2,-1,0,1,2,3,\dots \}.\]
Vamos\(a,b \in \mathbb{Z}\). Decimos\(b\) divide\(a\) y escribimos\(b\ \vert\ a\) si hay un elemento\(c \in \mathbb{Z}\) tal que\(a=bc\). Escribimos\(b \ \not \vert \ a\) si\(b\) no divide\(a\).
Si\(b \ \vert \ a\) también a veces decimos que\(b\) es un factor de\(a\) o que\(a\) es un múltiplo de\(b\). Para saber si\(b\) divide\(a\) dónde\(b \neq 0\), simplemente dividimos\(a\) por\(b\) y vemos si el resto es 0 o no. De manera más general, tenemos el siguiente resultado fundamental.
Para cualquier número entero\(a\) y\(b\) con\(b \neq 0\) existe enteros únicos\(q\) y\(r\) tal que\[ \nonumber a = bq+r, \qquad 0 \le r < |b|.\]
El número\(r\) en el Lema anterior se denota por\(a \bmod b\).
Por ejemplo tenemos
\[ \nonumber 17 \bmod 5 = 2 \qquad \mbox{ since \quad $17 = 3 \cdot 5 + 2$ \ and \ $0 \le 2 < 5$}\]y\[ \nonumber (-17) \bmod 5 = 3 \qquad \mbox{ since \quad $-17 = (-4) \cdot 5 + 3$ \ and \ $0 \le 3 < 5$}.\]
Se dice que un entero\(p\) es primo si\(p \ge 2\) y los únicos factores positivos de\(p\) son\(p\) y 1.
Dejar\(a\) y\(b\) ser enteros, al menos uno de los cuales es distinto de cero. El mayor divisor común de\(a\) y\(b\) es el mayor entero positivo\(\gcd(a,b)\),, que divide ambos\(a\) y\(b\). Definimos\(\gcd(0,0)=0\).
Si\(a\) y\(b\) son enteros distintos de cero, el mínimo común múltiplo de\(a\) y\(b\) es el entero positivo más pequeño,\(\text{lcm}(a,b)\), que es un múltiplo de ambos\(a\) y\(b\). Si\(a=0\) o\(b=0\), definimos\(\text{lcm}(a,b) = 0\).
Una propiedad importante de los primos viene dada por el siguiente lema.
Si\(p\) es primo y\(p | ab\) entonces\(p | a\) o\(p | b\).
Quizás el resultado más fundamental respecto a los enteros es el siguiente teorema, que a veces se llama El Teorema Fundamental de la Aritmética.
Si\(n \ge 2\) es un número entero, entonces existe una lista única de primos\(p_1, p_2, \dots, p_k\) tal que se mantienen las siguientes dos condiciones:
- \(p_1 \le p_2 \le \cdots \le p_k\),
- \(n = p_1 p_2 \cdots p_k\)
Por ejemplo, si\(n=72\) la lista única de primos es 2, 2, 2, 3, 3.
Ahora arregla un entero positivo\(n\). Recordemos que\(\mathbb{Z}_n = \{ 0, 1, \dots , n-1 \}\) y que la multiplicación y la suma en\(\mathbb{Z}_n\) se definen por
\(a + b =\)resto cuando la suma ordinaria de\(a\) y\(b\) se divide por\(n\), y
\(a \cdot b =\)resto cuando el producto ordinario de\(a\) y\(b\) se divide por\(n\).
Para facilitar la prueba de que estas dos operaciones binarias son asociativas, denotamos temporalmente suma en\(\mathbb{Z}_n\) por\(\oplus\) y multiplicación en\(\mathbb{Z}_n\) por\(\odot\). De esta manera podemos usar\(+\) y\(\cdot\) para suma ordinaria y multiplicación en\(\mathbb{Z}\). Así tenemos\[\begin{aligned} a \oplus b &=&(a + b) \bmod n \\ a \odot b &=& (ab) \bmod n\end{aligned}\]
Dejar\(n\) ser un entero positivo. Definir\(f: \mathbb{Z}\to \mathbb{Z}_n\) por la regla\(f(a) = a \bmod n\). Entonces
\[\begin{align} f(a + b) = f(a) \oplus f(b) \label{C1}\end{align}\]
y
\[\begin{align} f(a \cdot b) = f(a) \odot f(b). \label{C2} \end{align}\]
Prueba Dejar\(r_1 = f(a)\) y\(r_2 = f(b)\). Esto implica eso\[a = nq_1 + r_1, \quad 0 \le r_1 < n\] y\[b = nq_2 + r_2, \quad 0 \le r_2 < n\] De ahí\[a+b= nq_1 + r_1 + nq_2 + r_2 = n(q_1+q_2) + r_1+r_2\] Ahora\[f(a) \oplus f(b) = r_1 \oplus r_2 = r\] donde\[r_1 + r_2 = qn + r, \quad 0 \le r < n\] De ahí\[a+b=n(q_1+q_2+q) + r, \quad 0 \le r < n\] y se deduce eso\[f(a+b)=(a+b) \bmod n = r,\] y concluimos que\[f(a+b) = r = f(a) \oplus f(b).\] Esto prueba (C.1). La prueba de (C.2) es similar y se deja al lector interesado.
Las operaciones binarias\(\oplus\) y\(\odot\) on\(\mathbb{Z}_n\) son asociativas.
Prueba Usando la notación en el teorema, tenemos para\(a,b,c \in \mathbb{Z}_n\):\(f(a) = a\),\(f(b) = b\) y\(f(c) = c\). De ahí\[\begin{aligned} (a \oplus b) \oplus b &=& (f(a) \oplus f(b)) \oplus f(c)\\ &=& f(a+b) \oplus f(b) \\ &=& f( (a+b)+c)\\ &=& f(a + (b+c)) \\ &=& f(a) \oplus f(b+c) \\ &=& f(a) \oplus( f(b) \oplus f(c)) \\ &=& a \oplus (b \oplus c)\end{aligned}\] esto prueba que\(\oplus\) es asociativo en\(\mathbb{Z}_n\). El comprobante para\(\odot\) es similar y se deja al lector interesado.