La raíz de un entero (no cuadrado) es irracional

En Gaussianos hemos visto ya unas cuantas demostraciones de la irracionalidad de algunos números reales. Entre ellas, podemos destacar la irracionalidad de Pi (y II) y la irracionalidad de e (y II), pero posiblemente sea la irracionalidad de raíz de 2 la que más se ha visto por aquí.

Sobre ella podéis encontrar varios artículos en el blog. Os dejo algunos enlaces:

y uno más general sobre la irracionalidad de \sqrt[n]{2}:

Hoy vamos a ver una demostración elemental (en el sentido de los conocimientos que utiliza) de que \sqrt{m} es irracional, siempre que m no sea un cuadrado perfecto. Vamos con ella:

Teorema: Si m no es un cuadrado perfecto, entonces \sqrt{m} es un número irracional.

Demostración:

Como m no es un cuadrado perfecto, entonces \sqrt{m} no es un número entero, por lo que sea racional (no entero) o irracional. Esto significa que podemos encontrar un número entero n tal que \sqrt{m} se encuentra entre n y n+1:

n < \sqrt{m} < n+1

Lo que vamos a demostrar es que a=\sqrt{m}-n es irracional (lo que, sabiendo que n es un número entero, implicaría que \sqrt{m} también es irracional).

Supongamos que a no es irracional. Por su propia definición, se tiene que 0 < a < 1, por lo que, si no es irracional, será de la forma

a=\cfrac{p}{q}

siendo 0 < p < q. Podemos asumir sin ningún problema que q es lo más pequeño posible. Si tomamos la fracción inversa y operamos un poco obtenemos lo siguiente:

\cfrac{q}{p}=\cfrac{1}{a}=\cfrac{1}{\sqrt{m}-n}=

Multiplicamos ahora numerador y denominador por el conjugado del denominador actual, \sqrt{m}+n, y seguimos operando:

=\cfrac{\sqrt{m}+n}{\sqrt{m}+n} \cdot \cfrac{1}{\sqrt{m}-n}=\cfrac{\sqrt{m}+n}{m-n^2}=\cfrac{a+2n}{m-n^2}

Hemos llegado a la siguiente igualdad:

\cfrac{q}{p}=\cfrac{a+2n}{m-n^2}

Ahora despejamos a:

a=\cfrac{q \cdot (m-n^2)}{p}-2n=\cfrac{q \cdot (m-n^2)-2np}{p}=\cfrac{k}{p}

Acabamos de obtener que a se puede expresar mediante una fracción cuyo denominador, p, es más pequeño que el denominador anterior, q (por definición, p era menor que q). Pero eso es imposible, ya que habíamos supuesto que q era el menor denominador posible.

Esta contradicción proviene del hecho de suponer que a=\sqrt{m}-n es un número racional. En consecuencia, a es irracional, lo que implica que \sqrt{m} también es un número irracional.


Creo que es la primera demostración de este hecho que publico en Gaussianos, salvo las cuestiones sobre ello que se hayan tratado en los comentarios de alguna entrada. Si encontráis algo sobre ello en alguna entrada o comentario de este blog os agradecería que nos lo comunicarais en los comentarios.


Demostración de Harley Flanders a partir de una demostración de Theodor Estermann. Vía Fermat’s Library.

imagen tomada de aquí.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

4 Comentarios

  1. Conjetura

    La solucion de una funcion aleatoria es un variable determinitica

    Contradiccion del concepto de Kolmogorov respecto a un campo probabilistico

    Publica una respuesta
  2. Copio y pego lo siguiente para quien interese y pueda entenderlo completamente. De cómo la factorización de un entero grande en el menor tiempo posible es una cuestión algorítmica y matemática compleja, al alcance sólo de los especialistas. (Y de cómo los problemas computacionales son problemas de alta matemática, aunque hay gente que cree erróneamente que los computadores matan a la matemática y eso no es cierto).

    We report on a discrete logarithm computation in GF(p^5) for a
    20-decimal digit prime, using the number field sieve algorithm
    (NFS-DL), and a relation collection phase over degree-two polynomials,
    instead of the more classical degree-one case.

    We select the 20-decimal-digit (dd) prime
    p = 31415926535897932429 = Floor(10^(19)*pi) + 45,
    and consider the finite field GF(p^5) where
    p^5-1 = (p-1)*11*101*191*7363691*33031656232204364259865845615041*l,
    and
    l = 18872357657025660688767070155926911 is a 35dd prime.
    Our aim is to compute discrete logarithms in the prime order subgroup of
    GF(p^5)* of cardinality l.
    Since the extension degree is prime, the ExTNFS [1] algorithm is
    restrained to its TNFS original form [2], where the base-ring R is a
    degree-5 number field above Q and sieving in dimension 10, or to the
    high degree variant of NFS-DL (NFS-HD), with R=Q (no tower). We
    implemented the latter option: NFS-HD.

    Our computations were done using Xeon CPU E5520 @ 2.27GHz cores. Details
    can be found in
    https://members.loria.fr/AGuillevic/files/record-computations/2017_GremyGuillevicMorain_p5dd20hd.pdf
    and soon in https://hal.inria.fr/hal-01568373.

    Polynomial selection
    ——————–

    We selected polynomials with the Joux-Lercier-Smart-Vercauteren
    method [3] that produced this pair of polynomials:
    f0 = x^5 – 5*x^4 – 5368736472*x^3 + 10737472959*x^2 – 5368736477*x – 2
    f1 = 5851642500*x^5 – 29258212500*x^4 + 25042672429*x^3
    + 37689292642*x^2 – 4215540071*x – 11703285000
    and alpha(f0) = -4.0, alpha(f1) = -8.3.

    Three-dimensional relation collection
    ————————————-

    The relation collection was performed using the special-q sieve [4] and
    the three-dimensional sieving algorithms described in [5]. The
    smoothness bounds are set to 2^{25}, and the cofactorization is
    performed if on both sides, the remaining norms are smaller than 2^{80}.
    The special-qs are set on side 1 and have norm in ]2^{21}, 2^{23.75}[:
    inside a special-q-lattice, we sieve on both sides the ideals of inertia
    degree 1 that have a norm bellow 2^{21}.

    In each special-q-lattice, we consider a sieving region containing
    2^{25} elements c of the lattice. The cost to find the 6,171,924
    relations was about 359 CPU days.

    Filtering
    ———

    On the 6,171,924 relations produced with the three-dimensional
    relation collection, 4,999,773 were unique, and this led to a
    1,489,631 * 1,489,625 matrix after singleton removal, reduced to a
    final 490,307 * 490,301 matrix after more intensive filtering.

    Linear algebra
    ————–

    The linear algebra step is performed using the block-Wiedemann algorithm. The
    parameters used were m=12 and n=6. Then 6 parallel jobs were used, one for
    each of the 6 sequences. Each parallel job used a 2*2 node topology,
    each node having 8 cores.

    The time to compute the Krylov subspaces was 237 hours, then 4 hours for the
    linear generator and 35 hours to create the solutions from the
    generator. 3,787,509 logs were reconstructed (out of at most 4,128,343
    possible logs).

    Individual logarithms
    ———————

    To completely validate our work, we report the computation of an
    individual logarithm. We first note that h = X+1 generates the whole
    multiplicative group GF(p^5)*. We find that h lifts to K_0 as z+1: its
    virtual logarithm is vlog(h) = 6948023766431672832537048942111617 mod l.

    Now, consider the target t made of the decimals of pi:
    t = 3141592653589793238*X^4 + 4626433832795028841*X^3
    + 9716939937510582097*X^2 + 4944592307816406286*X
    + 2089986280348253421.
    After 20,000 seconds we find that the lift of
    h^{9002259}*t has a smooth norm.

    Contrary to the relation collection step, we can re-express the elements
    by looking for a relation given by a degree one polynomial which took
    11,958 seconds, finally leading to
    vlog(t) = 2842707450406843989059381483536738 mod l.

    Summary of the computation
    ————————–

    Timings (CPU days)
    Polynomial selection: 15
    Relation collection: 359
    Linear algebra: 11.5
    Individual logarithm: 0.37

    Total: 386 CPU days

    Laurent Grémy
    Aurore Guillevic
    François Morain

    CNRS/Inria/Université de Lorraine, LORIA UMR 7503, Nancy, France
    École Polytechnique/CNRS-LIX UMR 7161/Université Paris-Saclay, Palaiseau, France

    Sage verification script
    ————————

    Q. = ZZ[]

    p = floor(10^19*pi) + 45; n = 5
    ell = 18872357657025660688767070155926911; cof = (p^n-1) // ell

    f0 = x^5 – 5*x^4 – 5368736472*x^3 + 10737472959*x^2 – 5368736477*x – 2
    f1 = 5851642500*x^5 – 29258212500*x^4 + 25042672429*x^3 + 37689292642*x^2 \
    – 4215540071*x – 11703285000
    varphi = f0

    Fpn. = GF(p^n, modulus=varphi)

    gen = T + 1
    target1 = 3141592653589793238*T^4 + 4626433832795028841*T^3 \
    + 9716939937510582097*T^2 + 4944592307816406286*T \
    + 2089986280348253421

    vlog_gen = 6948023766431672832537048942111617
    vlog_target1 = 2842707450406843989059381483536738

    assert(gen^(cof * vlog_target1) == target1^(cof * vlog_gen))

    [1] Kim, T., Barbulescu, R.: Extended Tower Number Field Sieve: A New Complexity
    for the Medium Prime Case. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016.
    LNCS, vol. 9814, pp. 543–571. Springer (2016)

    [2] Barbulescu, R., Gaudry, P., Kleinjung, T.: The Tower Number Field Sieve.
    In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp.
    31–55. Springer (2015)

    [3] Joux, A., Lercier, R., Smart, N., Vercauteren, F.: The number field sieve in
    the medium prime case. In: Dwork, C. (ed.) CRYPTO~2006. LNCS, vol. 4117,
    pp. 326–344. Springer (Aug 2006)

    [4] Hayasaka, K., Aoki, K., Kobayashi, T., Takagi, T.: An experiment of number
    field sieve for discrete logarithm problem over GF(p^{12}). In:
    Fischlin, M., Katzenbeisser, S. (eds.) Number Theory and Cryptography. LNCS,
    vol. 8260, pp. 108–120. Springer (2013)

    [5] Gaudry, P., Gr{\’e}my, L., Videau, M.: Collecting relations for the Number
    Field Sieve in GF(p^6). LMS Journal of Computation and Mathematics 19,
    332–350 (2016)

    Publica una respuesta
  3. ¿Y por qué conformarnos con raíces cuadradas?

    Decir que existe un numero entero cuya raíz enésima es un racional no entero, equivale a decir que existe un racional no entero cuyo potencia enésima es un entero.

    Si existe este número racional y es de la forma (irreducible) a/b, entonces tenemos que b es distinto de 1, y mcd(a, b) = 1

    Pero a^n/b^n no puede ser un entero. Porque b^n es diferente de 1, y si mcd(a^n, b^n) = d (diferente de 1), entonces tenemos que p (un factor primo cualquiera de d) divide a a^n, y b^n, pero entonces también es divisor de ‘a’ y ‘b’. Contradicción

    Publica una respuesta
  4. Me parece una demostración excesivamente complicada. Aquí va una más simple: asumamos que la raíz de n es un número racional (no entero) a/b, siendo a y b coprimos. n=(a/b)^2=a^2/b^2. Pero a^2 y b^2 también tienen que ser coprimos porque no tienen factores primos en común (a^2 tiene los mismos factores primos que a pero con los exponentes del doble). Por tanto, y dado que ninguno de los dos cuadrados es uno (a/b no es entero), n no es entero.

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *