viernes, 24 de febrero de 2012

Problema del dia: Viernes

A) Demuestre que para todo entero $a>2$ existen una infinidad de enteros positivos $n$ tales que $n|a^n-1$
B)Sea $n\ge 2$ natural. Si $\frac{b^n-1}{b-1}$ es potencia de un primo para algun entero positivo $b$, entonces $n$ es primo.

22 comentarios:

Juan dijo...

(a)Si tenemos $v_{p_1}(n)=\alpha_1 \ge 1$ para cierto primo $p_1$ y un número $n$, entonces, si $ord_{p_1}a=d$, $p_1\mid a^n-1 \Rightarrow d \mid n \Rightarrow d \mid (n, p_1-1) \Rightarrow d \mid \frac{n}{p_1^{\alpha_1}} \Rightarrow p_1 \mid a^{\frac{n}{p_1^{\alpha_1}}}-1 \Rightarrow v_{p_1}(a^n-1)=v_{p_1}(a^{n/p_1^{\alpha_1}*p_1^{\alpha_1}}-1^{p_1^{\alpha_1}})=\alpha_1+v_{p_1}(a^{n/p_1^{\alpha_1}}) \textgreater \alpha_1$. Así, $p_1 \mid a^n-1 \Leftrightarrow p_1^{\alpha_1}\mid a^n-1$. Entonces, $n\mid a^n-1 \Leftrightarrow p_1p_2\ldots p_k \mid a^n-1$, considerando $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$. Ésto demuestra $n \mid a^n-1 \Rightarrow n^{\lambda} \mid a^{n^{\lambda}}-1 \forall \lambda \in \mathbb{N}$. Por consiguientes es suficiente encontrar un $n\textgreater1$ que cumpla. Ésto es fácil, un primo que divida a $a-1$ cumple, y existe pues $a \textgreater 2$. Quod erat demonsrandum. $\clubsuit$.

Juan dijo...

Donde no se alcanza a leer dice $p_1\mid a^n-1 \Rightarrow d \mid n $$\Rightarrow d \mid (n, p_1-1) \Rightarrow$$ d \mid \frac{n}{p_1^{\alpha_1}} \Rightarrow$$ p_1 \mid a^{\frac{n}{p_1^{\alpha_1}}}-1 \Rightarrow$$ v_{p_1}(a^n-1)=v_{p_1}(a^{n/p_1^{\alpha_1}*p_1^{\alpha_1}}-1^{p_1^{\alpha_1}})=$$\alpha_1+v_{p_1}(a^{n/p_1^{\alpha_1}}) $$\textgreater \alpha_1$

Juan dijo...

Hice un Lifting Exponent allí, y donde dice $a^{\frac{n}{p_1^{\alpha_1}}}-1$ es $a$ a la ($n$ entre $p_1$ a la $\alpha_1$).

Juan dijo...

(b)$\displaystyle\frac{b^n-1}{b-1}=p^m$. Fácilmente se ve que si $q\mid b-1$ es primo no $p$, entonces por Lifting, $v_q\left(\displaystyle\frac{b^n-1}{b-1}\right)=$$v_q(b^n-1)-v_q(b-1)=v_q(n)\Rightarrow v_q(n)=0$$\Rightarrow (b-1,n)=p^j$ para algún $j$. Si $p \mid b-1 \Rightarrow m = v_p\left(\displaystyle\frac{b^n-1}{b-1}\right)=$$v_p(b^n-1)-v_p(b-1)=v_p(n)\Rightarrow n \ge p^m \ge $$\displaystyle\frac{b^n-1}{b-1} \ge $$\displaystyle\frac{2^n-1}{2-1}=2^n-1$. Contraidicción, pues $n \ge 2$. Así, $p \mid b-1$ es falso y $(n,b-1)=1$ ($j=0$). Ahora si $ord_pb=d\textless n$ entonces $d \neq 1$ y $m=v_p(b^d-1)+v_p(n) $$\Rightarrow \displaystyle\frac{b^n-1}{b-1}=p^m \le n(b^d-1) $$\le n(b^{n/2}-1) \Rightarrow \displaystyle\frac{b^{n/2}+1}{b-1} $$\le n \Rightarrow \displaystyle\frac{2^{n/2}+1}{2-1} \le n$. Contradicción. Así, $ord_pb=n \Rightarrow n \mid p-1$ Así, $p$ no divide a $n$. Si $ord_qb=x\textgreater 1$ y $q$ no es $p$ entonces es inmediato que $x\mid n$ es falso, de ahí que $q-1 \mid n$ es falso. Así, supongamos a modo de contradicción que tenemos un primo $r \mid n$ y $r\neq n$. Ahora es fácil ver que si hay un primo $s \mid b^n-1$ no $p$, se concluye que $s\mid b-1, v_s(n)=0\Rightarrow (n,b^n-1)=1$. También se da con $s$ no $p$ que $ord_sb \mid n \Rightarrow ord_sb =1$. Así, $ord_sb\neq r \forall s$ primo. Ahora consideremos $A=\displaystyle\frac{b^r-1}{b-1}$. Tenemos $v_p(A)=0$ por que $ord_pb=n$. Tenemos que si $s \neq p \Rightarrow$ ó $v_s(A)=0$ ó $ord_sb \mid n \Rightarrow ord_sb=1 $$\Rightarrow v_s(A)=v_s(b^r-1)-v_s(b-1)=v_s(r) $$\Rightarrow A = r$ Ó $1$ de lo cual con desigualdades se puede deducir una contradicción fácilmente, por lo que $r$ no existe, y así $n$ es primo. Quod erat demonstrandum. $\clubsuit$.

José A. dijo...
Este comentario ha sido eliminado por el autor.
José A. dijo...
Este comentario ha sido eliminado por el autor.
José A. dijo...

A) Tenemos un lema que nos dice:
Si $x^m-1|x^n-1\Leftrightarrow m|n$
Ahora, para cualquier $a$ podemos encontrar un $p$ tal que $a\equiv 1(\bmod{p})$. Encontrar este $p$ es tan simple como encontrar algún factor primo de $a-1$.
Ahora, sabemos que $p|a^p-1$ por teorema de Fermat. Pero como eso pasa, también tenemos que:
$a^p-1|a^{a^p-1}-1$.
Si pensamos que $a^p-1=N_{1}$ entonces $N_{1}|a^{N_{1}}-1$.De esta divisibilidad, podemos concluir que:$a^{N_{1}}-1|a^{a^{N_{1}}-1}-1$. Considerando a $a^{N_{1}}-1=N_{2}$ tenemos que $N_{2}|a^{N_{2}}-1$ creando otro número que también cumple. Por lo tanto, como para cada nuevo $N_{k}$ podemos crear otro $N_{k+1}$ queda demostrado que son una infinidad.

alberto dijo...

a) Si encontramos una $n_0$ que cumpla que $n_0|a^{n_0}-1$, entonces usando que $a^x-1|a^y-1 \iff x|y$, podemos formar $n_1=a^{n_0}-1$ que por el lema anterior se cumple que $n_1|a^{n_1}-1$. Y de seguimos formando una sucesion donde $n_k=a^{n_{k-1}}-1$, y asi encontramos infinitas $n$'s que cumplen apartir de una.
Entonces hay que encontrar $n|a^n-1$
$\Rightarrow a^n \equiv 1 \pmod{n}$
Vemos $n=a-1$
$a^n \equiv a^{a-1} \equiv (1)^{a-1} \equiv 1 \pmod{a-1}$
Entonces esta n cumple y ya podemos formar infinitas $n$'s que tambien cumplen.

Unknown dijo...

a. Sea $p$ tal que $p|a-1$. Demostrare que $p^r$ cumple para tal $n$. Tengo que demostrar que
$v_p(a^(p^r)-1)\geq r$, pero $v_p(a^(p^r)-1)=v_p(a-1)+v_p(p^r)=r+v_p(a-1)\geq r$. Asi que $n=p^r$ cumple para todo $r$ natural.

b. Obviamente $b>1$, porque si no se divide entre $0=b-1$. Supongamos que $\frac{b^n-1}{b-1}=q^k$ con $q$ primo y tal que $q|b-1$.
Entonces $v_q(b^n-1)=v_q(n)+v_q(b-1)$. Entonces $k=v_q(q^k)=v_q(\frac{b^n-1}{b-1})=v_q(n)$ asi que $n\geq q^k$ porque $q^k|n$. Es facil ver que $q^k=\frac{b^r-1}{b-1}>b^{r-1}$.
Entonces $q^k>b^{n-1}\geq 2^{n-1}\geq 2^{q^k-1}$. Es facil ver que $2^t\geq t+1$ para todo $t$ natural. Entonces
$q^k>2^{q^k-1}\geq q^k$. Contradicción!

Asi que $q\not | b-1$. Si $n$ es compuesto entonces $n=rs$ con $r,s>1$. Tenemos que $b^r-1|b^n-1$. Asi que
$\frac{b^r-1}{b-1}\frac{b^{rs}-1}{b^r-1}=q^k$. Es facil ver que $\frac{b^r-1}{b-1}$ es potencia de $q$ y no es $1$ asi que $q|b^r-1$. Sea $c=b^r$. También $\frac{b^{rs}-1}{b^r-1}$ es potencia de $q$.
Entonces $\frac{c^s-1}{c-1}=q^u$ con $q|c-1$. Lo cual es contradicción por lo que ya habiamos dicho. Asi que $n$ es primo.

Chuck dijo...

a) Sea $p$ un primo tal que $p|a-1$ (existe pues $a\geq 3$. Demostremos por inducción que funciona para $p^k$ para cualquier entero positivo $k$. Así que como $k=1$ cumple (porque $p|a-1$ y $a-1|a^{p}-1$), supongamos que $k=x-1$ funciona, ahora veamos $k=x$; sabemos por hipótesis de inducción que $a^{p^{x-1}}\equiv 1\pmod{p^{x-1}}$ así que de inmediato vamos a escribir a $c:=\frac{a^{p^{x-1}}-1}{p^{x-1}}$ de modo que $(cp^{x-1}-1)^{p}=\sum_{i=0}^{p}{{p\choose i}(cp^{x-1})^{p-i}}$. Así pues, $(cp^{x-1}-1)^{p}\equiv p(cp^{x-1})+1\equiv 1\pmod{p^{x}}$ pues todos los factores con $i\geq 2$ tienen a $p$ con un exponente mayor o igual a $x$, de modo que podemos garantizar que $p^{x}|a^{p^{x}}-1$, así que como $x$ tiene una infinidad de posibles valores, el problema es cierto.

Chuck dijo...

Perdón, por ahí omití un $-$, debería ser $-p(cp^{x-1})+1$ pero de todas formas no cambia el resultado.

Chuck dijo...

b) El problema no tiene sentido para $b=1$, así que lo consideraremos mayor, además $b_{n}:=\frac{b^{n}-1}{b-1}$ y usaremos continuamente que $a^{x}-1|a^{y}-1\Leftrightarrow x|y$. Si $n$ es primo, entonces $b_{n}$ puede o no ser potencia de un primo, de cualquier modo, no nos interesa ver cuándo lo es y cuándo no, pues no el problema no exige una condición suficiente y necesaria.

Si $n$ es no primo, entonces es una potencia de primo, o tiene a dos primos que lo dividen. Si es potencia de un primo $p$, entonces sabemos que $\frac{b^{p}-1}{b-1},\frac{b^{p^{2}-1}{b-1}|b_{n}$ de este modo, ambos son potencias del mismo primo $q$, y por lo tanto el menor divide al mayor con su cociente siendo también la potencia de un primo. Por todo esto $A:=\sum_{i=0}^{p-1}b^{ip}$ es potencia de $q$ así como $B:=\sum_{i=0}^{p-1}b^{i}$ pero al ser mayor, entonces este último divide al primero, de modo que $B|A$. Esto es absurdo pues eso querría decir que si $C:=\sum_{i=2}^{p}(i-1)(Bb^{p(p-i)+1}-Bb^{p(p-i)})$, entonces $B|C$ y $C=A-p$ entonces $B|A-C$ por lo tanto $B|p$ pero esto no es posible pues $B\textgreater p$ porque $b^{p-1}\textgreater p$ pues $p|b^{p-1}-1$ si $b\leq p-1$, y en caso contrario, evidentemente $b\geq p$ y $B\textgreater p$. Por lo tanto si $n$ es potencia de un primo (mayor al primo), entonces $b_{n}$ no lo es.

Si $p\textless q$ son primos que dividen a $n$, entonces $\sum_{i=0}^{p-1}b^{i},\sum_{i=0}^{q-1}b^{i}|b_{n}$ y entonces ambos son potencias del mismo primo, así que el menor divide al mayor, es decir que $\sum_{i=0}^{p-1}b^{i}|\sum_{i=0}^{q-1}b^{i}$ pero entonces si los multiplicamos por $b-1$ también se debe cumplir por lo que $b^{p}-1|b^{q}-1$ pero es imposible pues esto implica que $p|q$ por lo tanto, si se cumple el enunciado, $n$ es primo.

Chuck dijo...

Donde no escribí bien el código, dice:
$\frac{b^{p}-1}{b-1},\frac{b^{p^{2}-1}}{b-1}|b_{n}$

Chuck dijo...

nuevamente lo escribí mal:
$\frac{b^{p}-1}{b-1},\frac{b^{p^{2}}-1}{b-1}|b_{n}$

jorge garza vargas dijo...
Este comentario ha sido eliminado por el autor.
jorge garza vargas dijo...

Como $a\leq 3$ entonces existe un primo $p$ tal que $p|a-1$, veremos que $p^k|a^{p^k}-1$ para todo $k$ entero positivo. Hagamosolo por inducción, si $k=1$ es claramente cierto, ahora si $p^s|a^{p^s}-1$ entonces veamos que $p^{s+1}|a^{p^{s+1}}-1$$=(a^{p^{s}}-1)(1+a^{p^{s}}\cdots+a^{(p^{s})(p-1)})$, pero $p$ divide al segundo paréntesis ya que $a\equiv 1\pmod{p}$ y hay $p$ términos, además $p^s|a^{p^s}-1$ por hipótesis de inducción, con lo cual se concluye el paso inductivo.

Adán dijo...

Como $a\geq 3$ existe un primo que divide a $a-1$. Entonces tenemos que $p|a^{p}-1$. Ahora, veamos que $a^{b}-1|a^{c}-1$ si y solo si $b|c$. Entonces, vamos a construir a $n$ de la siguiente manera

$p, a^{p}-1, a^{a^{p}-1}-1, \ldots$

Y veamos que todas esas $n$ cumplen que $n|a^{n}-1$, ya que $p|a-1$.

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Supongamos que $\frac{b^{n}-1}{b-1}=p^{k}$ y supongamos que $p|b-1$. Entonces sea $b=p^{m}l+1$ donde $\gcd{\left(p, l\right)}=1$. Entonces tenemos que

$\frac{b^{n}-1}{b-1}=p^{m\left(n-1\right)}l^{n}+\dbinom{n}{1}p^{m\left(n-2\right)}l^{n-1}+\ldots+\dbinom{n}{n-2}p^{m}l^{2}+\dbinom{n}{n-1}$

Así que si la expresión arriba es $p^{k}$, y por LTE, tenemos que

$v_{p}\left(b^{n}-1\right)=v_{p}\left(b-1\right)+v_{p}\left(n\right)$
$v_{p\left(n\right)=k$
$p^{k}|n$

Y obtenemos que la expresión expandida arriba es mayor que $p^{k}$, pues $\dbinom{n}{n-1}=n\geq p^{k}$, y obtenemos una contradicción.

Entonces, tenemos que $p$ no divide a $b-1$. Ahora, si $n=xy$ es compuesto, con $x-1, y-1 \in \mathbb{Z}^{+}$, tenemos que

$\frac{b^{xy}-1}{b-1}=\frac{b^{x}-1}{b-1}\cdot \frac{b^{xy}-1}{b^{x}-1}=p^{k}$

donde vemos que claramente $p$ divide a $b^{x}-1$, pero eso es una contradicción, pues eso implica que $\frac{\left(bx\right)^{y}-1}{\left(b^{x}\right)-1}$ no es potencia de $p$. Entonces $n$ no puede ser compuesto, y por ende es primo.

Enrique dijo...

a) Consideremos un divisor primo $p$ de $a-1$ (existe pues $a-1\geq 2$), luego $a\equiv 1$ (mod p) y $p\mid a-1$. Entonces, por LTE $v_{p}(a^{p^{k}}-1)=v_{p}(a-1)+v_{p}(p^{k})>v_{p}(p^{k})=k$, luego $p^{k}\mid a^{p^{k}}-1$ para todo $k$, y hay infinitos $k$, con lo que acabamos.
b) Supongamos que $n$ es compuesto, luego $n=px$ para algún primo $p$ y un entero $x>1$. Supongamos que $\frac{b^{n}-1}{b-1}=q^{k}$ con $q$ primo y $k$ entero positivo. Entonces, $b^{x}-1\mid b^{n}-1$, de donde $\frac{b^{x}-1}{b-1}\mid \frac{b^{n}-1}{b-1}\Rightarrow \frac{b^{x}-1}{b-1}=q^{l}$ para un entero positivo $l$ (pues x>1) menor a $k$ . De aquí obtenemos que $\frac{b^{n}-1}{b^{x}-1}=q^{k-l}$. Por LTE, $v_{q}(b^{n}-1)=v_{q}(b^{x}-1)+v_{q}(p)$ $\Rightarrow v_{q}(p)=v_{q}(b^{n}-1)-v_{q}(b^{x}-1)=k-l>0$ pues $k>l$, luego $p=q$ y $k-l=1$. Entonces, $n=qx$ y $\frac{b^{qx}-1}{b^{x}-1}=q\Rightarrow b^{qx}-1=q(b^{x}-1)$. Sin embargo, es fácil probar por inducción que $q\leq 2^{q-1}$, luego $q\leq 2^{q-1}\leq b^{q-1}\leq b^{x(q-1)}$ $\Rightarrow b^{qx}\geq qb^{x}$ $\Rightarrow b^{qx}-1\geq qb^{x}-1>q(b^{x}-1)=b^{qx}-1$, que es una contradicción. Entonces, $x=1$, de donde $n$ es primo.

JulioC dijo...

a) La secuencia $x_{1}=1$ y
$x_{n}=a^{ x_{n-1}}-1$ cumple que $x_{n}|a^{x_{n}}-1$, pues por un paso inducctivo
$1|a-1$, y si $x_{n-1}|a^{x_{n-1}}-1$, entonces
$a^{x_{n-1}}-1|a^{a^{x_{n-1}}}-1$, entonces
$x_{n}|a^{x_{n}}-1$.

JulioC dijo...

b) Sea $\frac{b^n-1}{b-1}=p^m$ con p primo.
Tenemos dos casos:
i) $p|b-1$, Entonces por LTE
$v_{p}(b^n-1)=v_{p}(b-1)+v_{p}(n)$
Pero $b^n-1=(p^m)(b-1)$, entonces
$v_{p}(b^n-1)=v_{p}(b-1)+v_{p}(p^m)=v_{p}(b-1)+m$
Entonces $m=v_{p}(n)$. Entonces $n\ge p^m$.
Pero $\frac{b^n-1}{b-1}>b^{n-1}\ge 2^{n-1}\ge n$
la primera desigualdad por factorización, la segunda por hipótesis y la tercera por paso inductivo.
Entonces $p^m>n\ge p^m$ Contradicción.
ii)$p\nmid b-1$. Supongamos que n=rs con r y s enteros positivos distintos de 1.
Entonces $\frac{b^r-1}{b-1}\frac{b^{rs}-1}{b^r-1}=p^m$ Entonces $p|b^r-1$ porque cada factor que es diferente de cero debe ser potencia de p.
Pero $\frac{b^{rs}-1}{b^r-1}$ tambien debe ser potencia de p y $p|b^r-1$ entonces por el caso i) hay una contradicción.
Por lo tanto n es primo

Publicar un comentario