8 votos

Masiva expresión de mod $2^{2013}$

Encontrar $$1^1+3^3+5^5 + \cdots +(2^{2012}-1)^{(2^{2012}-1)}$$ modulo $2^{2013}$. By checking small cases I am pretty sure that it is $2^{2012}$. I tried applying induction but you "lose" powers of two at each step. So instead I used binomial theorem to reduce it to $$\sum_{i=1,i \text{ odd}}^{2^{2011}-1} i^i-i^{2^{2012}-i}$$ de nuevo se parece mucho a la inducción, pero no puedo hacer que funcione. Cualquier ayuda por favor.

EDIT: También $\phi({2^{2013}})=2^{2012}$ así que en realidad, por el teorema de euler el anterior se transforma en la $\sum_{i=1,i \text{ odd}}^{2^{2011}-1} i^i-i^{-i}$

2voto

ND Geek Puntos 880

Creo que la inducción no trabajo para mostrar que para $k\ge2$, $$ \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} \equiv 2^k \pmod{2^{k+1}}. $$ Un hecho que vamos a utilizar es la de $n\ge3$, en realidad tenemos $a^{2^{n-2}}\equiv1\pmod {2^n}$ para cualquier extraño $a$; este es un poder de $2$ más fuerte que el teorema de Euler.

La comprobación de la $k=2$ de los casos es fácil. Supongamos que se cumple para algunos en particular $k$. Entonces \begin{align*} \sum_{i=1}^{2^k} (2i-1)^{2i-1} &= \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=2^{k-1}+1}^{2^k} (2i-1)^{2i-1} \\ &= \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=1}^{2^{k-1}} (2^k+2i-1)^{2^k+2i-1} \\ &\equiv \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=1}^{2^{k-1}} (2^k+2i-1)^{2i-1} \pmod{2^{k+2}} \end{align*} por el hecho. Ahora tenga en cuenta que $(2^k+j)^m \equiv j^m + m2^kj^{m-1} \pmod{2^{k+2}}$ por el teorema del binomio (desde $k\ge2$); en particular, sólo $j\pmod4$ es importante, así que si $j$ $m$ son impares, a continuación,$(2^k+j)^m \equiv j^m + m2^k \pmod{2^{k+2}}$. Por lo tanto \begin{align*} \sum_{i=1}^{2^k} (2i-1)^{2i-1} &\equiv \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=1}^{2^{k-1}} \big( (2i-1)^{2i-1} + (2i-1)2^k \big) \\ &= 2\sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + 2^{2k-2} 2^k \\ &= 2\sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} \pmod{2^{k+2}} \end{align*} (de nuevo desde $k\ge2$). La inducción de la hipótesis de que la $\sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1}\equiv 2^k\pmod {2^{k+1}}$ ahora implica que $\sum_{i=1}^{2^k} (2i-1)^{2i-1} \equiv 2^{k+1}\pmod {2^{k+2}}$ como se desee.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X