Otras carreras Confusión con condición necesaria.

[Fortuna]

Buenos días.

No soy matemático y estoy confundido en saber demostrar si una condición es necesaria, habiendo demostrado la suficiente.

Sé que para demostrar $p \Leftrightarrow q$ normalmente se demuestra $p \Rightarrow q$ y $p \Rightarrow q$ pero en este caso, no lo sé hacer así. Intento demostrar el siguiente teorema que creo que es cierto. En todos los casos, los números son naturales.


He demostrado previamente este lema: si $p\ge 3, 3^t-1\,mod\,2^p=0\Rightarrow3^{nt}-1\,mod\,2^{p}=0$ por inducción sobre n.



Teorema. $\forall p\ge3,\,3^t-1\,mod\,2^p=0\Leftrightarrow t=n\cdot2^{p-2}$


La condición suficiente del teorema se demuestra por inducción sobre p para n=1, es decir:

Si $p\ge3, t=2^{p-2}\Rightarrow{3^{t}-1\,mod\,2^{p}=0}$

Para p=3 y n=1, $t=2^{3-2}=2$ tenemos $3^{2}-1\,mod\,2^{3}=0$

Hipótesis. $3^{2^{p-2}}-1\,mod\,2^{p}=0$

$3^{2^{p-2}}-1\,mod\,2^{p}=0\Rightarrow3^{2^{p-2}}-1=q_{1,p}2^{p}\Rightarrow3^{2^{p-2}}=q_{1,p}3^{2^{p-2}}+1$

Donde $q_{1,p}$ es un natural que satisface la ecuación para n=1 y para $p\ge 3$.

Inducción:

$3^{2^{(p-2)+1}}-1=3^{2^{p-2}\cdot2}-1=(3^{2^{p-2}})^{2}-1=(q_{1,p}2^{p}+1)^{2}-1=$$q_{1,p}^{2}2^{2p}+2q_{1,p}2^{p}=q_{1,p}2^{p}(q_{1,p}2^{p}+2)=q_{1,p}2^{p+1}(q_{1,p}2^{p-1}+1)=q_{1,p+1}2^{p+1}$

con la condición $q_{1,p+1}=q_{1,p}(q_{1,p}2^{p-1}+1)$.

Por el lema indicado si $3^{2^{p-2}}-1\,mod\,2^{p}=0\Rightarrow3^{n2^{p-2}}\,mod\,2^{p}=0$.

Para n>1 $q_{n,(p+1)}=q_{n,p}(q_{n,p}2^{p-1}+1)$



Hasta aquí creo que está bien y que queda demostrada la condición suficiente, aunque es la primera vez que me sale una fórmula extra como condición necesaria para que la demostración por inducción funcione y eso me genera alguna duda.

El problema viene ahora:



Recordando que para que $3^t-1$ sea divisible por $2^{p}$ es necesario que lo sea al menos por $2^{p-1}$:

Si n es impar, ¿$3^{n\cdot2^{(p-2)-1}}-1$ es divisible por $2^p$?.

$3^{n\cdot2^{p-3}}-1\,mod\,2^{p}=0\Rightarrow3^{n\cdot2^{p-3}}-1$$=q\cdot2^{p}\Rightarrow\frac{1}{3}3^{n\cdot2^{p-2}}-1=q\cdot2^{p}\Rightarrow3^{n\cdot2^{p-2}}-3=$$3q\cdot2^{p}\Rightarrow3^{n\cdot2^{p-2}}-1=3q\cdot2^{p}+2$

Pero $3^{n\cdot2^{p-2}}-1=q_{n,p}2^{p}$ (esto no sé si se puede hacer, utilizar una condición suficiente para demostrar la necesaria)

$q_{n,p}2^{p}=3q\cdot2^{p}+2\Rightarrow2^{p}=\frac{2}{q_{n,p}-3q}$

Lo cual es imposible ya que $p\ge3$. Con lo cual para que $3^{t}-1\,mod\,2^{p}=0$ no es suficiente que $t=2^{n2^{p-3}}$ con n impar. Por tanto es necesario que $t=2^{n2^{p-2}}$.

Sobre todo la última frase me da la impresión de que o está mal formulada o es falsa. En todo caso no me convence.


Alguien me da alguna ayuda para poner la demostración de la condición necesaria de forma aceptable?.

Gracias de antemano.

[Dj_jara]

Re: Confusión con condición necesaria.

$3^{n\cdot2^{p-3}}-1\,mod\,2^{p}=0\Rightarrow3^{n\cdot2^{p-3}}-1$$=q\cdot2^{p}\Rightarrow\frac{1}{3}3^{n\cdot2^{p-2}}-1=q\cdot2^{p}\Rightarrow3^{n\cdot2^{p-2}}-3=$$3q\cdot2^{p}\Rightarrow3^{n\cdot2^{p-2}}-1=3q\cdot2^{p}+2$

No es lo mismo $3^{n \cdot 2^{p-3}}$ que $\dfrac{1}{3} 3^{n \cdot 2^{p-2}}$, para ejemplificarlo supongamos n = 1 y p =4 $3^{ \cdot 2^{1}} = 9$ y $\dfrac{1}{3} 3^{ \cdot 2^{2}} = 27$, eso en general, si aplicáramos modulo 16 (2^4) tampoco sería correcto uno daría 9 y el otro 11


Algunas demostraciones de doble implicación es mejor empezarlas en un sentido y otras en otro.

Veamos, para empezar la inducción supongamos p = 3, no es un caso muy complicado así que vamos a ejercitar un poco el cálculo numérico y voy hacer las dos condiciones a la vez (se puede seguir la demostración en un sentido u otro):
$3^0 = 1 mod 8$

$3^1 = 3 mod 8$

$3^2 = 1 mod 8$ Como vemos a partir de aquí se va a repetir el mismo comportamiento para todos los casos

$3^3 = 3 mod 8$

$3^4 = 1 mod 8$ generalizando se puede escribir como

$3^{2n} = 1 mod 8$ y $3^{2n+1} = 3 mod 8$

Pero para lo que nos interesa a nosotros es sólo $t = 2n = n 2^{p-2}$

Ahora pasemos a inducción, suponiendo que se cumple para $p-1\ge 3$, ?que ocurre con p?

Voy a empezar de derecha a izquierda $t = n 2^{p-2} \Rightarrow 3^t = 1 \mod 2^p$:

$t = n 2^{p-2} =2 n 2^{p-3} = 2 \tau$

donde he definido $\tau = n 2^ {p-3}$ para ayudar en el cálculo, como estamos suponiendo en que la doble implicación se cumple para p-1, entonces:
$3^\tau = K 2^{p-1}+1 \rightarrow 3^t = (K 2^{p-1}+1)^2 = (K^2+K) 2^p +1 \rightarrow 3^t = 1 mod 2^p$

Ya tenemos un sentido, ahora el otro de izquierda a derecha $3^t = 1 \mod 2^p\Rightarrow t = n 2^{p-2}$:

$3^t = 1 \mod 2^p \rightarrow = 3^t = K 2^p +1 = (2K) 2^{p-1}+1 \rightarrow t = R 2^{p-3}$

Ahora se pueden dar dos casos R es un número par, en cuyo caso ya tendríamos la demostración o R es un número impar, supongamos que es impar R = 2 Z +1:

$t = R 2^{p-3} = Z 2^{p-2} + 2^{p-3}\rightarrow 3^t = 3^{Z 2^{p-2}}3^{2^{p-3}}$ pero ya hemos demostrado antes que $3^{Z 2^{p-2}} = 1 \mod 2^p$ es decir $3^{t} = 3^{2^{p-3}} \mod 2^p$

La suposición inicial es que $3^{t} = 1 \mod 2^p$ con lo que $3^2\cdot 3^{t} = 9 \mod 2^p$ pero $3\cdot 3^{2^{p-3}} = 3^{2^{p-2}} \mod 2^p$, esto ya hemos demostrado antes que tiene que dar 1, con lo que llegamos a $1=9 mod 2^p$ lo cual sólo es posible si p fuera 0,1,2 o 3 pero en nuestro caso p es mayor que 3, con lo que no es posible tener R impar.

[Fortuna]

Re: Confusión con condición necesaria.

Muchas gracias por contestar.

No es lo mismo $3^{n \cdot 2^{p-3}}$ que $\dfrac{1}{3} 3^{n \cdot 2^{p-2}}$, para ejemplificarlo supongamos n = 1 y p =4 $3^{ \cdot 2^{1}} = 9$ y $\dfrac{1}{3} 3^{ \cdot 2^{2}} = 27$, eso en general, si aplicáramos modulo 16 (2^4) tampoco sería correcto uno daría 9 y el otro 11

Un lapsus. ... en fin, siempre he sido muy despistado y ya van 59 años.

$3^2 = 1 mod 8$ Como vemos a partir de aquí se va a repetir el mismo comportamiento para todos los casos

$3^3 = 3 mod 8$

$3^4 = 1 mod 8$ generalizando se puede escribir como

$3^{2n} = 1 mod 8$ y $3^{2n+1} = 3 mod 8$

Esto habría que demostrarlo por inducción para el caso p=3 , ¿no?. Es trivial, pero ¿cómo diferenciar entre una caso trivial de otro que no lo es?. Generalizando he cometido muchos errores.

[Error LaTeX: Compilación LaTeX fallida]

Aquí supongo que se debe leer, " supongamos que t es de la forma $t=R2^{p-3}$ " y la demostración continúa hasta demostrar que necesariamente R es par. Y aquí tengo la duda. ¿Cómo sé yo que t no tiene otra forma?, es decir, involucrar sumas o funciones, no necesariamente una potencia de 2. Está claro que R es par o impar y no hay más casos, pero formas que puede tener t(p) hay infinitas y no las hemos comprobado todas.

Gracias por tu tiempo.

[Dj_jara]

Re: Confusión con condición necesaria.

Esto habría que demostrarlo por inducción para el caso p=3 , ¿no?. Es trivial, pero ¿cómo diferenciar entre una caso trivial de otro que no lo es?. Generalizando he cometido muchos errores.

Sí se puede demostrar por inducción sobre n que es el parámetro que varía en ese caso (p esta fija a 3). En ese caso es fácil ver que siempre vas a estar oscilando entre un caso que da 1 y otro que da 3, si no se ve perfectamente claro (que viene a ser, que la demostración forma por inducción la puedes hacer en 1 línea), nada de generalizar.

Aquí supongo que se debe leer, " supongamos que t es de la forma $t=R2^{p-3}$ " y la demostración continúa hasta demostrar que necesariamente R es par. Y aquí tengo la duda. ¿Cómo sé yo que t no tiene otra forma?, es decir, involucrar sumas o funciones, no necesariamente una potencia de 2. Está claro que R es par o impar y no hay más casos, pero formas que puede tener t(p) hay infinitas y no las hemos comprobado todas.

Sí, no estaba mostrando una flecha, ahora ya debería salir la flecha y el 1 y la t no estar juntas. No hay ninguna suposición ahí sobre la forma de t, viene de la primera de todas que la condición se cumple para p-1, lo que muestra lo anterior es que$3^t = 1 \mod 2^{p-1}$ y por tanto t ha de tener esa forma.

[Fortuna]

Re: Confusión con condición necesaria.

Ahora sí, no vi que se empleaba la inducción en las dos direcciones.

Gracias.

PD. ¿Has visto que números monstruosos salen? Para que un número de la forma $3^t -1$ sea divisible por $2^{32}$ sale que ese número debe tener 512 millones de cifras ($3^{2^{30}}-1$)