Problema 1.
Sean $b,n\geq 2$ numero naturales tal que para cada $k\geq 2$ natural exista un entero $a_k$ que cumpla que $b-a_k^n$ es multiplo de $k$. Demuestra que $b=A^n$ para algún $A$ natural.
Problema 2.
Sea $n$ un numero natural. Demuestra que
\[ \binom{2^{n}-1}{0},\;\binom{2^{n}-1}{1},\;\binom{2^{n}-1}{2},\;\ldots,\;\binom{2^{n}-1}{2^{n-1}-1} \]
Son congruentes modulo $2^n$ a $1,3,\ldots, 2^n-1$ en algún orden.
7 comentarios:
Para el primero tengo algo, pero está muy fácil, no se si la regué :S Ahí va de todos modos.
Sea $p$ un primo que divide a $b$ y sea $v_{p}\left(b\right)=P$. Ahora, tomamos $k=p^{P+1}$ y sea $x$ el entero que satisface que $p^{P+1}$ divide a $b-x^{n}$.
Claramente, $p$ divide a $x$, por lo que $x=p^{a}\cdot X$ con $\left(p, X\right)=1$. Entonces, tenemos que $x^{n}=p^{an}\cdot X^{n}$, de donde vemos que:
Si $an$ es menor a $P$, entonces la máxima potencia de $p$ que divide a $b-x^{n}$ será $an$, que es menor a $P$, y menor a $P+1$ lo cual es una contradicción.
Si $an$ es mayor a $P$ entonces la máxima potencia de $p$ que divide a $b-x^{n}$ será $P$ que es menor a $P+1$ y eso es una contradicción.
Entonces $P=an$, lo que nos dice que $n$ divide a $P$. Esto lo hacemos para cada exponente de cada primo de $b$ y vemos que $n$ divide a cualquier exponente, de donde $b=A^{n}$, como queríamos.
El primero está sencillo, tomas un primo tal que $p_{i}^{\alpha_{i}}||b$ ahora tomamos a $k=p_{i}^{\alpha_{i}+1}$ y entonces $\frac{k}{p}||a_{k}^{n}$. Ahora, sea $\beta_{i}$ un natural tal que $p^{\beta_{i}}||a_{k}$ por lo tanto $\beta_{i}\cdot n=\alpha_{i}$ de modo que $\beta_{i}=\frac{\alpha_{i}}{n}$ de modo que si $b=\prod_{i=1}^{x}{p_{i}^{\alpha_{i}}}$ entonces
$b^{\frac{1}{n}}=\prod_{i=1}^{x}{p_{i}^{\beta_{i}}}=A\in\mathbb{N}$ por lo tanto $b=A^{n}
El segundo está mal escrito, ¿ no? supongo que más bien te refieres a que son todos los residuos módulo $2^{n-1}$... porque de lo contrario no hay suficientes coeficientes binomiales para tener todos esos residuos...
No es que esté mal el exponente, es que piden que sean congruentes a los impares.
En realidad devería de decir:
Demuestra que esos coeficientes binomiales son congruentes modulo $2^n$ a $1,3,5...2^n-1$ en algún orden.
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1555932&sid=91cd28187194d14ad2fb9bf125981b73#p1555932
El 1 vino en el selectivo de méxico del 2009 y es el N2 de la SL de IMO del 2007.
Lo reduje a inentar probar la siguiente proposición:
Si $1\leq a\leq b\leq 2^{n-1}-1$ entonces $\prod_{k=a}^b \frac{2^n-k}{k}$ no puede ser $\equiv 1\pmod{2^n}$.
De ahí ya no vi que hacer, ¿algún hint?
Ya tengo la demostración. Se divide en varias partes. Primero chequeamos que los primeros casos cumplan, fácil.
Notemos que $\binom{n}{m}\frac{n-m}{m+1}=\binom{n}{m+1}$. En particular, $\binom{2^n-1}{m}=\binom{2^n-1}{m-1}\frac{2^n-m}{m}=\binom{2^n-1}{m}(\frac{2^n}{m}-1)$.
Por lo tanto,
$\binom{2^n-1}{2r+1}\equiv \binom{2^n-1}{2r}(\frac{2^n-(2r+1))}{2r+1})\equiv \binom{2^n-1}{2r} (\frac{2^n}{2r+1}-1)\equiv -\binom{2^n-1}{2r}$
Mirando modulo $2^n$ (y obviamente $2^{n-1}$ también)
Después, demostramos que $\binom{2^n-1}{4k}\equiv \binom{2^{n-1}-1}{2k}$ modulo $2^{n-1}$.
Para eso fijémonos que
\[ (\frac{2^n}{4i+1}-1)(\frac{2^n}{4i+2}-1)(\frac{2^n}{4i+3}-1)(\frac{2^n}{4i+4}-1)\equiv (-1)(\frac{2^{n-1}}{2i+1}-1)(-1)(\frac{2^{n-1}}{2i+2)-1)\equiv (\frac{2^{n-1}}{2i+1}-1)(\frac{2^{n-1}}{2i+2}-1) \]
Modulo $2^{n-1}$. Asi que llendo de 4 en 4 multiplicandos, podemos concluir que $\binom{2^n-1}{4k}\equiv \binom{2^{n-1}-1}{2k}$ dado que $\binom{2^n-1}{0}=1=\binom{2^{n-1}-1}{0}$.
Ahora veamos que $(\frac{2^{n}}{2i+1}-1)(\frac{2^{n-1}}{2i+1}-1)\equiv -1$ con modulo $2^{n-1}$ y $2^{n}$.
También $(\frac{2^{n}}{2i+1}-1)(\frac{2^{n}}{2i+2}-1)\equiv(\frac{2^{n}}{2i+1}-1)(\frac{2^{n-1}}{i+1}-1)\equiv 1$, modulo $2^{n-1}$. Más aún, tenemos que $(\frac{2^{n}}{4i+1}-1)(\frac{2^{n}}{4i+2}-1)\equiv (-1)(\frac{2^{n-1}}{2i+1}-1)\equiv (-1)(2^{n-1}-1} \equiv 2^{n-1}+1$.
Entonces
$$\binom{2^n-1}{4k}\equiv\binom{2^n-1}{4k+2}\equiv\binom{2^{n-1}-1}{2k}$$
y
$$\binom{2^n-1}{4k+1}\equiv\binom{2^n-1}{4k+3}\equiv\binom{2^{n-1}-1}{2k+1}\equiv -\binom{2^{n-1}-1}{2k}$$.
modulo $2^{n-1}$
Pero también, como $2^{n-1}+1\not\equiv 1$ tenemos que $\binom{2^n-1}{4k}\equiv\binom{2^n-1}{4k+2}+2^{n-1}$ y $\binom{2^n-1}{4k+1}\equiv\binom{2^n-1}{4k+3}+2^{n-1}$ modulo $2^n$.
Ahora supongamos que para $n=m-1$ se cumple. Asi que lo demostraremos para $n=m$. Queremos ver si el impar $1\leq T\leq 2^m-1$ esta en esa secuencia. Supongamos que es congruente a $t$ modulo $2^{m-1}$, con $1\leq t\leq 2^{m-1}-1$. Entonces existe exactamente un entero $0\leq q\leq 2^{m-2}-1$ tal que $\binom{2^{m-1}}-1}{q}\equiv t$ modulo $2^{n-1}$. Entonces sea $r=2q$ si $q$ es par y $2q-1$ si $q$ es impar. Tenemos que, por lo anterior demostrado, $\binom{2^n-1}{r}\equiv t$ modulo $2^{n-1}$. Pero $\binom{2^n-1}{r+2}\equiv \binom{2^n-1}{r}+2^{n-1}$ modulo $2^n$, asi que exactamente uno de esos dos coeficientes cumplen que es congruente a $T$ modulo $2^n$. Por lo tanto, existe un coeficiente binomial de la secuencia que es $T$, para todo $T$ impar entre esos.
Como hay tantos impares en $1,3,\ldots, 2^n-1$ como coeficientes binomiales, entonces cada uno esta exactamente una vez.
Publicar un comentario