Saltar al contenido principal
LibreTexts Español

5.3: Declaraciones de divisibilidad y otras pruebas usando PMI

  • Page ID
    113997
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Hay un resultado muy famoso conocido como Pequeño Teorema de Fermat. Esto probablemente se abreviaría FLT excepto por dos cosas. En ciencia ficción FLT significa “más rápido que el viaje ligero” y hay otro teorema debido a Fermat que va por las iniciales FLT: El último teorema de Fermat. El último teorema de Fermat afirma que las ecuaciones de la forma\(a^n + b^n = c^n\), donde\(n\) es un número natural positivo, solo tienen soluciones enteras que son triviales (como\(0^3 + 1^3 = 1^3\)) cuando\(n\) es mayor que\(2\). Cuando\(n\) es\(1\), hay muchas soluciones enteras. Cuando\(n\) es\(2\), todavía hay muchas soluciones enteras — estas son las llamadas triples pitagóricas, por ejemplo\(3\),\(4\) &\(5\) o\(5\),\(12\) &\(13\). Es algo injusto que esta afirmación sea conocida como el último teorema de Fermat ya que no lo probó (o al menos no podemos estar seguros de que lo demostró). Cinco años después de su muerte, el hijo de Fermat publicó una versión traducida 1 de Aritmetica de Diofantus que contenía las anotaciones de su padre. Una de esas notaciones —cerca del lugar donde Diofantus estaba discutiendo la ecuación\(x^2 + y^2 = z^2\) y su solución en números enteros— fue la afirmación de lo que hoy se conoce como el último teorema de Fermat así como la siguiente afirmación:

    Cuius rei demonstrationem mirabilem cuerdo detexi hanc marginis exiguitas no caperet.

    En inglés:

    He descubierto una prueba verdaderamente notable de esto que el margen de esta página es demasiado pequeño para contener.

    Entre\(1670\) y\(1994\) muchos matemáticos famosos trabajaron en FLT pero nunca encontraron el “demostrationem mirabilem”. Por último en\(1994\), Andrew Wiles de Princeton anunció una prueba de FLT, pero en palabras propias de Wiles, la suya es “una prueba del siglo XX” no puede ser la prueba que Fermat tenía en mente.

    En estos días la mayoría de la gente cree que Fermat se equivocó. Probablemente pensó que una técnica de prueba que funciona para valores pequeños de\(n\) podría generalizarse. Sigue siendo una pregunta tentadora, ¿se puede lograr una prueba de FLT usando solo los métodos disponibles en el\(17^{\text{th}}\) siglo?

    Parte de la razón por la que tanta gente dedicó tanto esfuerzo a FLT a lo largo de los siglos es que Fermat tuvo un excelente registro en cuanto a ser correcto sobre sus teoremas y pruebas. El resultado conocido como pequeño teorema de Fermat es un ejemplo de un teorema y una prueba de que Fermat acertó. Probablemente se le conoce como su “pequeño” teorema porque su enunciado es muy corto, pero en realidad es un resultado bastante profundo.

    Teorema\(\PageIndex{1}\): Fermat's Little Theorem

    Por cada número primo\(p\), y para todos los enteros\(x\), el\(p\) -ésimo poder de\(x\) y\(x\) en sí mismo son congruentes\(\text{mod } p\). Simbólicamente:

    \[x^p ≡ x (\text{mod } p)\]

    Una ligera reafirmación del pequeño teorema de Fermat es que p es siempre un divisor de\(x^p − x\) (asumiendo que\(p\) es un primo y\(x\) es un entero). Los profesores de matemáticas disfrutan usando sus conocimientos del pequeño teorema de Fermat para preparar resultados de divisibilidad que se pueden probar mediante inducción matemática. Por ejemplo, considere lo siguiente:

    \(∀n ∈ \mathbb{N}, 3|(n^3 + 2n + 6).\)

    Este es realmente solo el\(p = 3\) caso del pequeño teorema de Fermat con un poco de camuflaje agregado:\(n^3 + 2n + 6 = (n^3 − n) + 3(n + 2)\). Pero echemos un vistazo a probar esta afirmación usando PMI.

    Teorema\(\PageIndex{2}\)

    \[∀n ∈ \mathbb{N}, 3|(n^3 + 2n + 6)\]

    Prueba

    (Por inducción matemática)

    Fundamento: Claramente\(3|6\).

    Paso inductivo:

    (Tenemos que demostrar eso\(3|(k^3 + 2k + 6) \implies 3|((k + 1)^3 + 2(k + 1) + 6\).)

    Considera la cantidad\((k + 1)^3 + 2(k + 1) + 6\).

    \(\begin{array} (k + 1)^3 + 2(k + 1) + 6 \\ &= (k^3 + 3k^2 + 3k + 1) + (2k + 2) + 6 \\ &= (k^3 + 2k + 6) + 3k^2 + 3k + 3 \\ &= (k^3 + 2k + 6) + 3(k^2 + k + 1). \end{array}\)

    Por la hipótesis inductiva,\(3\) es un divisor de\(k^3 + 2k + 6\) por lo que hay un entero\(m\) tal que\(k^3 + 2k + 6 = 3m\). Por lo tanto,

    \((k + 1)^3 + 2(k + 1) + 6 \\ = 3m + 3(k^2 + k + 1) \\ = 3(m + k^2 + k + 1)\).

    Q.E.D.

    Practica

    Elaborar una prueba inductiva de la declaración,\(∀n ∈ \mathbb{N}, 5|x^5+4x−10\).

    Hay otro truco sutil para idear declaraciones a probar por PMI que debes conocer. Un ejemplo debería bastar para dejarlo claro. Observe que\(7\) es equivalente a\(1 (\text{ mod } 6)\), se deduce que cualquier poder de\(7\) es también\(1 (\text{ mod } 6\)). Entonces, si restamos\(1\) de algún poder de\(7\) tendremos un número que es divisible por\(6\).

    La prueba (por PMI) de una afirmación como esta requiere otro pequeño truco sutil. En algún lugar del camino en la prueba necesitarás la identidad\(7 = 6+1\).

    Teorema\(\PageIndex{3}\)

    \[∀n ∈ \mathbb{N}, 6|7^n − 1\]

    Prueba

    (Por PMI)

    Base: Tenga en cuenta que\(7^0 − 1\) es\(0\) y también eso\(6|0\).

    Paso inductivo:

    (Tenemos que demostrar que si\(6|7^k − 1\) entonces\(6|7^{k+1} − 1\).)

    Considera la cantidad\(7^{k+1} − 1\).

    \(\begin{array} 7^{k+1} − 1 &= 7 · 7^k − 1 \\ &= (6 + 1) · 7^k − 1 \\ &= 6 · 7^k + 1 · 7^k − 1 \\ &= 6(7^k) + (7^k − 1) \end{array}\)

    Por la hipótesis inductiva,\(6 | 7^k − 1\) entonces hay un entero\(m\) tal que\(7^k − 1 = 6m\). De ello se deduce que

    \(7^{k+1} − 1 = 6(7^k) + 6m\).

    Entonces, claramente,\(6\) es un divisor de\(7^{k+1} − 1\).

    Q.E.D.

    La inducción matemática a menudo se puede utilizar para probar desigualdades. Hay bastantes ejemplos de familias de declaraciones donde hay una desigualdad por cada número natural. A menudo tales afirmaciones parecen ser ciertas y, sin embargo, idear una prueba puede ser ilusorio. Si tal es el caso, intente usar PMI. Una pista: es bastante típico que el paso inductivo en una prueba PMI de una desigualdad implique un razonamiento que no es particularmente agudo. Solo recuerda que si tienes una desigualdad y haces que el lado grande sea aún más grande, ¡la afirmación resultante ciertamente sigue siendo cierta!

    Considere las secuencias\(2n\) y\(n!\).

    \(n\) \(0\) \(1\) \(2\) \(3\)
    \(2^n\) \(1\) \(2\) \(4\) \(8\)
    \(n!\) \(1\) \(1\) \(2\) \(6\)

    Como ilustra la tabla, para valores pequeños de\(n\),\(2n > n!\). Pero a\(n = 4\) partir de ahora se invierte la desigualdad.

    Teorema\(\PageIndex{4}\)

    \[∀n ≥ 4 ∈ \mathbb{N}, 2^n < n!\]

    Prueba

    (Por inducción matemática)

    Bases: Cuando\(n = 4\) tenemos\(2^4 < 4!\), lo cual es ciertamente cierto\((16 < 24)\).

    Paso inductivo: Supongamos que\(k\) es un número natural con\(k > 4\), y eso\(2^k < k!\). Multiplique el lado izquierdo de esta desigualdad por\(2\) y el lado derecho por\(k + 1\) 2 para obtener

    \(2 · 2^k < (k + 1) · k!\).

    Entonces

    \(2^{k+1} < (k + 1)!.\)

    Q.E.D.

    El estudiante observante de Cálculo sin duda será consciente del hecho de que, asintóticamente, las funciones exponenciales crecen más rápido que las funciones polinómicas. Es decir, si tienes una base\(b\) que es mayor que\(1\), la función\(b^x\) es eventualmente más grande que cualquier polinomio\(p(x)\). Esto puede parecer un poco difícil de creer si\(b = 1.001\) y\(p(x) = 500x^{10}\). El gráfico de\(y = 1.001^x\) es prácticamente indistinguible de la línea\(y = 1\) (al principio), mientras que el gráfico de ya\(y = 500x^{10}\) ha alcanzado el valor astronómico de cinco billones\((5,000,000,000,000)\) cuando\(x\) es justo\(10\). Sin embargo, el exponencial eventualmente superará al polinomio. Podemos utilizar los métodos de esta sección para comenzar a probar el hecho mencionado anteriormente. Considera las dos secuencias\(n^2\) y\(2n\).

    \(n\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\)
    \(n^2\) \(0\) \(1\) \(4\) \(9\) \(16\) \(25\) \(36\)
    \(2^n\) \(1\) \(2\) \(4\) \(8\) \(16\) \(32\) \(64\)

    Si pensamos en una “carrera” entre las secuencias\(n^2\) y\(2^n\), note que\(2^n\) empieza con el plomo. Las dos secuencias están atadas cuando\(n = 2\). Brevemente,\(n^2\) entra en el liderato pero vuelven a estar empatados cuando\(n = 4\). Después de eso, parecería que\(2^n\) recaptura el plomo para siempre. Por supuesto, estamos haciendo una presunción bastante amplia — ¿es realmente cierto que\(n^2\) nunca\(2^n\) vuelve a ponerse al día? Bueno, si tenemos razón entonces debería ser demostrable el siguiente teorema:

    Teorema\(\PageIndex{5}\)

    Para todos los números naturales\(n\), si\(n ≥ 4\) entonces\(n^2 ≤ 2^n\).

    Prueba

    Bases: Cuando\(n = 4\) tenemos\(4^2 ≤ 2^4\), lo cual es cierto ya que ambos números lo son\(16\).

    Paso inductivo: (En el paso inductivo asumimos eso\(k^2 ≤ 2^k \) y luego lo mostramos\((k + 1)^2 ≤ 2^{k+1}\).)

    La hipótesis inductiva nos dice que

    \(k^2 ≤ 2^k\).

    Si sumamos\(2^{k + 1}\) al lado izquierdo de esta desigualdad y\(2^k\) al lado derecho produciremos la desigualdad deseada. Así seguirá nuestra prueba siempre y cuando así lo sepamos\(2^{k + 1} ≤ 2^k\). En efecto, basta con mostrar eso\(2^{k + 1} ≤ k^2\) ya que ya sabemos (por la hipótesis inductiva) eso\(k^2 ≤ 2^k\).

    Por lo que el resultado permanece en duda a menos que pueda completar el ejercicio que sigue.

    Q.E.D.???

    Practica

    Demostrar el lema: Para todos\(n ∈ \mathbb{N}\), si es que\(n ≥ 4\) entonces\(2^{n + 1} ≤ n^2\).

    Ejercicios:

    Dar pruebas inductivas de lo siguiente:

    Ejercicio\(\PageIndex{1}\)

    \(∀x ∈ \mathbb{N}, 3|x^3 − x\)2. 3. 4. 5. 6. 7.

    Ejercicio\(\PageIndex{2}\)

    \(∀x ∈ \mathbb{N}, 3|x^3 + 5x\)

    Ejercicio\(\PageIndex{3}\)

    \(∀x ∈ \mathbb{N}, 11|x^{11} + 10x\)

    Ejercicio\(\PageIndex{4}\)

    \(∀n ∈ \mathbb{N}, 3|4^n − 1\)

    Ejercicio\(\PageIndex{5}\)

    \(∀n ∈ \mathbb{N}, 6|(3n^2 + 3n − 12)\)

    Ejercicio\(\PageIndex{6}\)

    \(∀n ∈ \mathbb{N}, 5|(n^5 − 5n^3 + 14n)\)

    Ejercicio\(\PageIndex{7}\)

    \(∀n ∈ \mathbb{N}, 4|(13^n + 4n − 1)\)

    Ejercicio\(\PageIndex{8}\)

    \(∀n ∈ \mathbb{N}, 7|8^n + 6\)

    Ejercicio\(\PageIndex{9}\)

    \(∀n ∈ \mathbb{N}, 6|2n^3 − 2n − 12\)

    Ejercicio\(\PageIndex{10}\)

    \(∀n ≥ 3 ∈ \mathbb{N}, 3n^2 + 3n + 1 < 2n^3\)

    Ejercicio\(\PageIndex{11}\)

    \(∀n > 3 ∈ \mathbb{N}, n^3 < 3^n\)

    Ejercicio\(\PageIndex{12}\)

    \(∀n ≥ 3 ∈ \mathbb{N}, n^3 + 3 > n^2 + 3n + 1\)

    Ejercicio\(\PageIndex{13}\)

    \(∀x ≥ 4 ∈ \mathbb{N}, x^{2} 2^x ≤ 4^x)\)


    This page titled 5.3: Declaraciones de divisibilidad y otras pruebas usando PMI is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Joseph Fields.