Tema

Ejercicio 35 pratica 5

4 respuestas 6430 visitas 2008-11-08

#1 LaRy 2008-11-08 21:02

Hola.. aca volvi con mis dudas... Alguien tiene idea de como hacer esto????

Calcular el resto de la division de
$\sum_{1}^{1759} {i}^{42}$ por 56

#2 exequiel131719 2008-11-08 21:54

Una idea:

$\sum_{i\eq=1}^{1759}{i}^{42}$. Como $56\eq={2}^{3}\cdot 7$, como ${2}^{3},7$ son coprimos, estudiás cada congruencia por separado:

\sum_{i\eq=1}^{1759}{i}^{42}\equiv r(7)

Pero por el teorema de Fermat, ${i}^{6}\equiv 1(7)$ si $(i:7)\eq=1$. Luego, como ${i}^{42}\eq={({i}^{6})}^{7}\eq={({i}^{7})}^{6}\equiv {i}^{6}$,(usé que ${i}^{7}\equiv i(7)$), los múltiplos de $7$ no aportan a la suma, módulo 7(tales términos son congruentes 0 módulo 7), mientras que los otros, aportan $1$, por Fermat, nuevamente. Luego, como $\frac{1759}{7}$ tiene parte entera $251$, resulta que, por ser $7\cdot 251\eq=1757<1759,\;7\cdot 252\eq=1764>1759$, hay $251$ múltiplos de $7$. Luego, $1759-251\eq=1508$:

\sum_{i\eq=1}^{1759}{i}^{42}\equiv \sum_{i\eq=1}^{1759}{i}^{6}\equiv \sum_{i\eq=1}^{1508}1\eq=1508\equiv 3(7)

\sum_{i\eq=1}^{1759}{i}^{42}\equiv r({2}^{3})

El truco es similar, los múltiplos de $2$, satisfacerán que son de la forma ${2k}^{42}$, con lo que ${2}^{3}|{2k}^{42}$, luego tales términos serán congruentes a $0$ módulo ${2}^{3}$. Con los impares, el estudio es ligeramente más fino. Si mal recuerdo, en un ejercicio de la práctica te piden probar que ${a}^{{2}^{n-1}}\equiv 1({2}^{n})$, o uno parecido, o más general. Bueno, usando ese resultado, tenés que ${a}^{{2}^{3-1}}\eq={a}^{4}\equiv 1({2}^{3})$. Como ${i}^{42}\eq={{i}^{4}}^{10}{i}^{2}\equiv {i}^{2}({2}^{3})$, resulta que basta estudiar el ciclo de restos de los cuadrados. Como: ${1}^{2}+{3}^{2}+{5}^{2}+{7}^{2}\eq=84\equiv 4({2}^{3})$(los pares, ya dijimos que valían 0), y como este ciclo se repite cada $8$ números, contamos el número de tales ciclos de $1$ a $1759$. Como $\frac{1759}{8}$ tiene parte entera $219$, se repite $219$ veces el ciclo, de manera entera, y luego, de $1752$ a $1759$, tenemos ${1}^{2}+{3}^{2}+{5}^{2}+{7}^{2}\equiv 4({2}^{3})$(estos son los restos módulo ${2}^{3}$ de $1753,1755,1757,1759$). Los pares, en la congruencia, como dijimos, aportan $0$. Luego, en resumen: $\sum_{i\eq=1}^{1759}{i}^{42}\equiv \sum_{i\eq=1}^{219}{i}^{2}+{1}^{2}+{3}^{2}+{5}^{2}+{7}^{2}\eq=\sum_{i\eq=1}^{219}4+4\eq=4\cdot 220\eq=8\cdot 110\equiv 0 ({2}^{3})$. Luego, tenemos:

\sum_{i\eq=1}^{1759}{i}^{42}\equiv 3(7)

\sum_{i\eq=1}^{1759}{i}^{42}\equiv 0(7)

Después, falta aplicar teorema chino del resto y listo. Perdón si terminé sin ser claro; quise ser detallado, y obtuve el resultado opuesto. Cualquier cosa preguntá. 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

#3 crazy2k 2009-03-06 02:41

Resolví este ejercicio en el wiki.

#4 kv310 2011-08-01 17:11

Editado 1 vez.

#5 kv310 2011-08-01 17:33

exequiel131719 escribió:

Una idea:

$\sum_{i\eq=1}^{1759}{i}^{42}$. Como $56\eq={2}^{3}\cdot 7$, como ${2}^{3},7$ son coprimos, estudiás cada congruencia por separado:
$\sum_{i\eq=1}^{1759}{i}^{42}\equiv r(7)$ Pero por el teorema de Fermat, ${i}^{6}\equiv 1(7)$ si $(i:7)\eq=1$. Luego, como ${i}^{42}\eq={({i}^{6})}^{7}\eq={({i}^{7})}^{6}\equiv {i}^{6}$,(usé que ${i}^{7}\equiv i(7)$), los múltiplos de $7$ no aportan a la suma, módulo 7(tales términos son congruentes 0 módulo 7), mientras que los otros, aportan $1$, por Fermat, nuevamente. Luego, como $\frac{1759}{7}$ tiene parte entera $251$, resulta que, por ser $7\cdot 251\eq=1757<1759,\;7\cdot 252\eq=1764>1759$, hay $251$ múltiplos de $7$. Luego, $1759-251\eq=1508$: $\sum_{i\eq=1}^{1759}{i}^{42}\equiv \sum_{i\eq=1}^{1759}{i}^{6}\equiv \sum_{i\eq=1}^{1508}1\eq=1508\equiv 3(7)$ $\sum_{i\eq=1}^{1759}{i}^{42}\equiv r({2}^{3})$ El truco es similar, los múltiplos de $2$, satisfacerán que son de la forma ${2k}^{42}$, con lo que ${2}^{3}|{2k}^{42}$, luego tales términos serán congruentes a $0$ módulo ${2}^{3}$. Con los impares, el estudio es ligeramente más fino. Si mal recuerdo, en un ejercicio de la práctica te piden probar que ${a}^{{2}^{n-1}}\equiv 1({2}^{n})$, o uno parecido, o más general. Bueno, usando ese resultado, tenés que ${a}^{{2}^{3-1}}\eq={a}^{4}\equiv 1({2}^{3})$. Como ${i}^{42}\eq={{i}^{4}}^{10}{i}^{2}\equiv {i}^{2}({2}^{3})$, resulta que basta estudiar el ciclo de restos de los cuadrados. Como: ${1}^{2}+{3}^{2}+{5}^{2}+{7}^{2}\eq=84\equiv 4({2}^{3})$(los pares, ya dijimos que valían 0), y como este ciclo se repite cada $8$ números, contamos el número de tales ciclos de $1$ a $1759$. Como $\frac{1759}{8}$ tiene parte entera $219$, se repite $219$ veces el ciclo, de manera entera, y luego, de $1752$ a $1759$, tenemos ${1}^{2}+{3}^{2}+{5}^{2}+{7}^{2}\equiv 4({2}^{3})$(estos son los restos módulo ${2}^{3}$ de $1753,1755,1757,1759$). Los pares, en la congruencia, como dijimos, aportan $0$. Luego, en resumen: $\sum_{i\eq=1}^{1759}{i}^{42}\equiv \sum_{i\eq=1}^{219}{i}^{2}+{1}^{2}+{3}^{2}+{5}^{2}+{7}^{2}\eq=\sum_{i\eq=1}^{219}4+4\eq=4\cdot 220\eq=8\cdot 110\equiv 0 ({2}^{3})$. Luego, tenemos: $\sum_{i\eq=1}^{1759}{i}^{42}\equiv 3(7)$ $\sum_{i\eq=1}^{1759}{i}^{42}\equiv 0(7)$ Después, falta aplicar teorema chino del resto y listo. Perdón si terminé sin ser claro; quise ser detallado, y obtuve el resultado opuesto. Cualquier cosa preguntá. Saludos.

Fijate que, $a \equiv 1, 2, 3, 4, 5, 6, 0 \, (7)$ entonces
debe ser $a^{42} \equiv 1, 1, 1, 1, 1, 1, 0 \, (7)$ porque ( $a^{42} = (a^3)^{14}$ )

donde $\sum_{1}^{1759} i^{42} \equiv (1+1+1+1+1+1+0)*251 + (1758^{42} + 1759^{42}) \equiv (6)251 + 2 \equiv 3 \, mod(7)$

Esto sale de que $1759 = 7*251 + 2$

De la misma manera para los congruentes a 8.

Saludos!