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:
- Dos demostraciones de la irracionalidad de raíz de 2.
- Una demostración geométrica de la irracionalidad de raíz de 2.
- (Posiblemente) La demostración más elemental de la irracionalidad de raíz de dos.
y uno más general sobre la irracionalidad de ![\sqrt[n]{2}](https://s0.wp.com/latex.php?latex=%5Csqrt%5Bn%5D%7B2%7D&bg=T&fg=000000&s=0 "\sqrt[n]{2}")
Hoy vamos a ver una demostración elemental (en el sentido de los conocimientos que utiliza) de que 
Teorema: Si
Demostración:
Como
tal que
:
Lo que vamos a demostrar es que
es irracional (lo que, sabiendo que
Supongamos que
no es irracional. Por su propia definición, se tiene que
, por lo que, si no es irracional, será de la forma
siendo
. Podemos asumir sin ningún problema que
es lo más pequeño posible. Si tomamos la fracción inversa y operamos un poco obtenemos lo siguiente:
Multiplicamos ahora numerador y denominador por el conjugado del denominador actual,
, y seguimos operando:
Hemos llegado a la siguiente igualdad:
Ahora despejamos
Acabamos de obtener que
, es más pequeño que el denominador anterior,
Esta contradicción proviene del hecho de suponer que
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í.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Conjetura
La solucion de una funcion aleatoria es un variable determinitica
Contradiccion del concepto de Kolmogorov respecto a un campo probabilistico
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)
¿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
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.
+Ferran …lo mismo que sucede para (a/b)^2, también sucede para (a/b)^3, (a/b)^4 ..etc. y es que al ser (a, b) sin ningún factor primo en común (son coprimo: su descomposición en factores primos, no contiene ninguno en común) sucede lo mismo con (a^2, b^2), (a^3, b^3), (a^4, b^4), … etc no? esta bien la demostración? esta completa?
…las preguntas (no? esta bien la demostración? esta completa?), se refieren a que si
[ la demostración buscada se puede reducir a la demostración de que la potencia natural* de un racional irreducible* y no-entero* nunca puede ser un entero ]?
*irreductible: los números naturales a y b (de la fracción a/b), tienen una descomposición en factores primos, con ningún factor primo en común. (si tuviesen algun primo en comun, la fraccion se podria simplificar, o sea que no sería irreductible)
*no-entero: b diferente de 1
____________________
ejemplo: con a=2^3 por 5 = 8*5 = 40 tiene los primos 2 y 5
y con b=7 que tiene el primo 7,
tenemos la fracción irreducible 40/7
si la elevamos a la ^3: (40/7)^3 = (40^3) / (7^3), tenemos 64000/343
…con a = 64000 = 2^9 por 5^3
y b= 343= 7^3
con los mismos primos para a 2 y 5; y para b, 7, asi que sigue siendo una fracción irreductible y nunca sera un entero.
pero me sigue quedando la misma pregunta:
la demostración de que la raíz enésima (mayor que 2, o sea, raíz cuadrada, tercera, …etc) de un número natural nunca sera un racional irreducible no-entero ( y por lo tanto sera, o un entero, o un irracional), queda demostrada por la demostración de que la potencia enésima de un racional irreducible y no-entero, nunca sera un entero?
no se, me queda la sensación de que no está completa.
?
Sres Gaussianos, no he podido publicar en los comentarios una fórmula generadora de primos. simplemente no me la publican como hago?
Se puede establecer una forma generalizada de un irraciinal como la suma de un racional más la raíz de un racional?
No. Quedarían pendientes en tu fórmula los irracionales trascendentes.
Demostrar que si la raíz n-ésima de un número natural A no es un número entero, entonces es un número irracional.
Demostración. Supongamos que (A)^(1/n) = a/b, donde (a/b) es un número racional mayor que un cierto entero positivo E y menor que (E+1). a y b no tienen factores primos comunes.
Al elevar al exponente n en ambos miembros, se obtiene:
(a/b)^n = A (*).
Sea F = (f1,f2, … , fk) el conjunto de los factores primos de a, y sea G = (g1,g2, … , gl) el conjunto de los factores primos de b.
Sabemos que F ∩ G = ∅.
Los factores primos de (a)^n son (f1,f1,f1,…,f1), (f2,f2,…,f2), …, (fk,fk, …, fk), donde en cada grupo el factor se repite n veces.
Por tanto,como están repetidos, el conjunto de factores primos de (a)^n es:
H = (f1,f2,…,fk) = F.
Además, los factores primos de (b)^n son (g1,g1,…g1), (g2,g2, …,g2), … , (gl,gl, …,gl), donde en cada grupo el factor se repite n veces.
Por tanto, debido a que están repetidos, el conjunto de los factores primos de (b)^n es:
I = (g1,g2, …,gl) = G
Como H = F e I = G, H ∩ I = ∅.
Se deduce que (a)^n y (b)^n no tienen factores primos comunes.
Entonces, (a^n)/(b^n) es una fracción irreducible.
Debido a que (a/b) es mayor que E y menor que (E+1), b ≠ 1. Y al calcular el cociente (a^n)÷(b^n), el resultado, necesariamente, es un racional no entero.
Así, (a^n)/(b^n)=(a/b)^n ≠ k, donde k es un número natural.
En particular,(a/b)^n ≠ A.
Entonces, según la expresión (*), hemos llegado a una contradicción. La suposición inicial es falsa. (A)^(1/n) no es un racional. Finalmente, (A)^(1/n) es un irracional.
De modo que si la raíz n-ésima de un número natural A no es un número entero, entonces es un irracional.