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.
viernes, 24 de febrero de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
22 comentarios:
(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$.
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$
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$).
(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$.
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.
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.
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.
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.
Perdón, por ahí omití un $-$, debería ser $-p(cp^{x-1})+1$ pero de todas formas no cambia el resultado.
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.
Donde no escribí bien el código, dice:
$\frac{b^{p}-1}{b-1},\frac{b^{p^{2}-1}}{b-1}|b_{n}$
nuevamente lo escribí mal:
$\frac{b^{p}-1}{b-1},\frac{b^{p^{2}}-1}{b-1}|b_{n}$
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.
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$.
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.
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.
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$.
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