[Gulgo]

Bien, he intentado resolver 4 ejercicios de congruencia de un libro, y me estan costando saber si la manera de resolverlos es valida o debo de trabajar mas:

Primer ejercicio: Tengo que probar que para cualquier \( n  \) natural impar se cumple que \( 8|n^2-1  \):

Lo hago por inducción completa

Base inductiva: Para n= 1 es trivial que se cumple 8|0

Si \( 8 |n^2-1  \), entonces \( n^2-1 = 8 * h \), como es para naturales impares, es para los n de la forma \( 2n+1  \) sustituimos en \( n^2-1 = 8 *h \) dando lugar a \( 4 n^2 + 4 n = 8 * h \)

Hipotesis: \( 4 k^2 + 4 k = 8 * y \) 

Pruebo para k+1:  \(   4 k^2 + 12 k + 8 = 8 * d  \)

\(  12k = 4k + 8k   \)

Entonces:\(   4 k^2 + 4k +8 k + 8 = 8 * d  \)

Sustituyo la hipotesis: \(   8 * y +8 k + 8 = 8 * d  \)

Sacamos factor comun 8:
\(   8 ( y + k + 1) = 8 * d  \)

Entonces no queda probado, el problema esta, en que ahora tengo que probarlo por congruencia, pero me he trancado:

Para ello dije bueno, si \( 8|n^2-1  \) , entonces \( n^2 \equiv 1 mod 8  \):
Entonces no se me ocurre muy bien que aplicar.

El segundo ejercicio constaba en probar que para todo natural n se cumple que \(  3 | 7^n - 4^n  \)
Lo mismo que antes \(  7^n - 4^n  = 3*h  \)
El problema fue que al probar para k+1 llegue a 
\( 7^{k+1} - 4^{k+1} = 3 * d  \)
\( 7^k * 7  - 4^{k+1} = 3 * d \)
\( 7^k * (3+4)  - 4^{k+1} = 3 * d  \)
\( 7^k * 3 + 7^k *4  - 4^{k+1} = 3 * d  \)
\( 7^k * 3 +  4 * (7^k  - 4^k) = 3 * d  \)
Tambien se me habia ocurrido aplicar un teorema del binomio con\(  (3+4)^{k+1}  \)pero no se que tan viable es
Y por congruencia, me tranco en exactamente lo mismo que en la anterior    \(  7^n \equiv 4^n mod 3  \)

El tercero me pide: Determinar el conjunto de los numeros naturales n para los cuales vale que \(  2^n < 2! \) entonces, yo lo que hice fue probar por tanteo, ir dandoles valor hasta llegar a 4, el cual lo cumplia. Pero el problema es que no se si al llegar, tengo que probarlo de haciendo \(  4 + k  \) con \(   k > 1  \) , o simplemente al encontrarlo, por el principio de buena ordenacion queda justificado.

Y el cuarto ejercicio: Tengo que probar que si p es primo, \( (a+b)^p \equiv a^p + b^p \) mod n
Y me tranco en exactamente lo mismo que los demas, no se que hacer... Creo que la idea estaria en probar que \(  (\overline{a} + \overline{b})^p = \overline{a}^p + \overline{b}^p \)

[robinlambada]

Hola.

El primero por inducción esta bien. El 2º no lo he comprobado.

Para el 1º basándote en congruencias llegados a:

\( n^2-1 \equiv 0 \, mod \,8\Leftrightarrow{}4k^2+4k \equiv 0 \,mod \,8 \)

Sacando factor común 4k tenemos:

\( 4\cdot{}k(k+1) \equiv 0\,mod \,8 \)

k y k+1 son consecutivos , ¿que puedes asegurar respecto a su paridad?

Respecto al 2º, solo debes ver que si \( a\equiv{r} \, mod\, p\Leftrightarrow{}a^n\equiv{r^n}\, mod \, p \)

Saludos.

[Luis Fuentes]

Hola

El segundo ejercicio constaba en probar que para todo natural n se cumple que \(  3 | 7^n - 4^n  \)
Lo mismo que antes \(  7^n - 4^n  = 3*h  \)
El problema fue que al probar para k+1 llegue a 
\( 7^{k+1} - 4^{k+1} = 3 * d  \)
\( 7^k * 7  - 4^{k+1} = 3 * d \)
\( 7^k * (3+4)  - 4^{k+1} = 3 * d  \)
\( 7^k * 3 + 7^k *4  - 4^{k+1} = 3 * d  \)
\( 7^k * 3 +  4 * (7^k  - 4^k) = 3 * d  \)
Tambien se me habia ocurrido aplicar un teorema del binomio con\(  (3+4)^{k+1}  \)pero no se que tan viable es

¿Pero por qué dices "el problema es qué"?. Lo tienes bien hecho y concluyes lo que querías.

Y por congruencia, me tranco en exactamente lo mismo que en la anterior    \(  7^n \equiv 4^n mod 3  \)

Como sugiere robinlambada basta tener en cuenta que:

\( 7=1 \) mod \( 3 \) y \( 4=1 \) mod \( 3 \)

Por tanto:

\( 7^n-4^n=1^n-1^n \) mod \( 3 \)

El tercero me pide: Determinar el conjunto de los numeros naturales n para los cuales vale que \(  2^n < 2! \) entonces, yo lo que hice fue probar por tanteo, ir dandoles valor hasta llegar a 4, el cual lo cumplia. Pero el problema es que no se si al llegar, tengo que probarlo de haciendo \(  4 + k  \) con \(   k > 1  \) , o simplemente al encontrarlo, por el principio de buena ordenacion queda justificado.

Revisa el enunciado. ¿Querías poner \( 2^n<2! \)? ¿O quizá \( 2^n<n! \)? ¿O alguna otra cosa?.

Y el cuarto ejercicio: Tengo que probar que si p es primo, \( (a+b)^p \equiv a^p + b^p \) mod n
Y me tranco en exactamente lo mismo que los demas, no se que hacer... Creo que la idea estaria en probar que \(  (\overline{a} + \overline{b})^p = \overline{a}^p + \overline{b}^p \)

Querías poner mod \( p \), en lugar de mod \( n \).

Ahí la clave está en usar la fórmula del binomio de Newton y probar que si \( p \) es primo entonces: \( \displaystyle\binom{p}{k} \) es divisible por \( p \) si \( 1\leq k\leq p-1 \). Para ello recuerda que:

\( \displaystyle\binom{p}{k}=\dfrac{p!}{k!(p-k)!} \)

Saludos.