Calcular el resto de dividir por 68 a:
$$\sum_{k=1}^{100} 2^{k!}$$
Firma
"If debugging is the process of removing bugs, then programming must be the process of putting them in." -- Dijkstra
Tema
[Resuelto] 2ºParcial verano 2007
Este ejercicio es para usar el teorema chino del resto. Bueno, ahora, una resolución:
\(\textrm{Calculemos\;los\;b\;que\;cumplen}\;\sum_{k\eq=1}^{100} {2}^{k!}\equiv b(68)\)
$$\textrm{Dado\;que}\;68\eq=17\cdot 4,\;\textrm{como\;17\;y\;4\;son\;coprimos,\;el\;teorema\;chino\;del\;resto\;asegura\;que\;b\;es\;unico\;y:}$$
$$\sum_{k\eq=1}^{100} {2}^{k!}\equiv b(68)\Leftrightarrow\;\sum_{k\eq=1}^{100} {2}^{k!}\equiv b(17)\;\land\;\sum_{k\eq=1}^{100} {2}^{k!}\equiv b(4)$$
$$\textrm{Veamos\;cada\;caso\;por\;separado.}$$
a)
$$\sum_{k\eq=1}^{100} {2}^{k!}\equiv b(4)$$
$$4\eq={2}^{2}\Rightarrow\;4|{2}^{r}\Leftrightarrow\;r\geq 2$$
$$\textrm{Recordando\;que}\;2!\eq=2,\;2|k!\Leftrightarrow\;k\geq 2,\;\textrm{vale\;escribir}\;k!\eq=2\cdot q,\;q\in \mathbb{N},\;k\geq2$$
$$\textrm{Observemos,\;luego,\;que}\;{2}^{k!}\eq={2}^{2\cdot q}\eq={({2}^{2})}^{q}\eq={4}^{q}\equiv 0(4),\;k\geq2$$
$$\textrm{Escribamos\;luego:}$$
$$\sum_{k\eq=1}^{100} {2}^{k!}\eq={2}^{1!}+\sum_{k\eq=2}^{100} {2}^{k!}\equiv 2+0\eq=2(4)$$
b)
$$\sum_{k\eq=1}^{100} {2}^{k!}\equiv b(17)$$
$$\textrm{Vale\;que}\;(2:17)\eq=1 \Leftrightarrow ({2}^{k}:17)\eq=1$$
$$\textrm{Estamos\;en\;la\;situacion\;del\;Teorema\;de\;Fermat:}$$
$${2}^{16}\equiv1(17)$$
$$\textrm{Estudiemos}\;k!;\;6!\eq=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\eq= 2\cdot 3\cdot {2}^{2}\cdot 5\cdot 2\cdot 3\eq= {2}^{4}\cdot {3}^{2} \cdot 5\eq=16\cdot {3}^{2}\cdot 5$$
$$6!|k!\Leftrightarrow\;k\geq 6.\;\textrm{Luego,}16|6!\;\land\;6!|k!\Rightarrow 16|k!\Leftrightarrow k!\eq=16\cdot q,\;q\in \mathbb{N}$$
$$k\geq6,\;{2}^{k!}\eq={2}^{16\cdot q}\eq={({2}^{16})}^{q}\equiv{1}^{q}\equiv1(17)$$
$$\textrm{Escribamos,\;luego:}$$
$$\sum_{k\eq=1}^{100} {2}^{k!}\eq={2}^{1!}+{2}^{2!}+{2}^{3!}+{2}^{4!}+{2}^{5!}+\sum_{k\eq=6}^{100} {2}^{k!}\equiv 2+{2}^{2}+{2}^{6}+{2}^{24}+{2}^{120}+\sum_{k\eq=6}^{100} 1$$
$$\textrm{Observando\;que}\;{2}^{4}\eq=16\equiv(-1)(17)$$
$$2+{2}^{2}+{2}^{6}+{2}^{24}+{2}^{120}+\sum_{k\eq=6}^{100} 1\eq=2+4+16\cdot4+{({2}^{4})}^{6}+{({2}^{4})}^{30}+95\equiv2+4-4+{(-1)}^{6}+{(-1)}^{30}+95\eq=2+4-4+1+1+95\eq=99\equiv14(17)$$
$$\textrm{Sabemos:}$$
$$\sum_{k\eq=1}^{100} {2}^{k!}\equiv2(4)$$
$$\sum_{k\eq=1}^{100} {2}^{k!}\equiv14(17)$$
$$\textrm{Concluimos,\;luego:}$$
$$\sum_{k\eq=1}^{100} {2}^{k!}\equiv2\cdot17+14\cdot4\cdot13\eq=34+728\eq=762\equiv14(68)$$
\(\textrm{Concluimos\;que\;el\;resto\;es\;14}\)
Dos cosas; en un momento dije que la solución es única; esto es cierto mirando congruencias, o lo que es lo mismo, mirando ''b'' como resto.
La otra aclaración es como calculé el último paso; no hice nada raro, es usar el teorema chino del resto, de vuelta. Espero haber sido claro( y no haber cometido errores...). Saludos.
Firma
I offer her that kernel of myself that I have saved, somehow; the central heart that deals not in words, traffics not with dreams and is untouched by time, by joy, by adversities
Si, esta bien, y lo hice de la misma manera y me dio lo mismo (Y)
Pero... si en vez de separar el 68 en 4*17, uso directamente el 68 tengo que \(2^{3!} = 64 \equiv -4 (68)\)
Entonces, con el mismo analisis, los restos de los sumandos em quedan 2 + 4 - 4 -4 -4 -4 ..... -4 -4. Pero tomo mod 68 a eso y me da 22 no 14.... donde esta el problema???
Gracias por la ayuda!
Nico.. el problema en lo que vos pusiste es que el primer 4 lo estás sumando.. hiciste 2 + 4 - 4 ... cuando debería ser 2 - 4 - 4 ... con eso da perfecto.
Edit:
No dije nada, me confundí, ese +4 estaba bien, no sé xq no da :S
Porque estás haciendo \({(-4)}^{k!}\equiv(-4)(68)\), lo cual... está mal. Ojo con eso, en la resolución vale porque tengo 1 elevado a un exponente. Si tenés otra cosa... no ganás nada. Espero ser claro en donde está el error.
Si, clarisimo despiste mio, muchas gracias!ª