Congruencia Modulo, Cuarta Parte(Problemas Propuestos) Opciones

[Rurouni Kenshin]

Y finalmente tenemos la parte en que ustedes pondran a prueba cuanto han aprendido...y no crean que les sera tan facil...tendran que esforzarse para aprender y aplicar esta poderosa arma.



Saludos

[Guía Rojo]

el 2 es el que me parece "menos difícil":

2. Muestre que para cualquier entero a, a^3 = 1 , 0 , ó 6 (mód 7)

Usaremos la notación a[k] para designar a los números congruentes con k en módulo 7 (k toma los valores enteros desde 0 hasta 6)
Esto se representa así:
a[k] = k (mód 7)
entonces:
(a[k])^3 = k^3 (mód 7)

Todos los números serán congruentes en módulo 7 con 0, 1, 2, 3, 4, 5, ó 6

Para los congruentes con 0 en módulo 7, se tiene:
a[0] = 0 (mód 7)
entonces:
(a[0])^3 = 0 (mód 7)

Para los congruentes con 1 en módulo 7, se tiene:
a[1] = 1 (mód 7)
entonces:
(a[1])^3 = 1 (mód 7)

Para los congruentes con 2 en módulo 7, se tiene:
a[2] = 2 (mód 7)
entonces:
(a[2])^3 = 8 (mód 7)
pero:
8 = 1 (mód 7)
entonces:
(a[2])^3 = 1 (mód 7)

Para los congruentes con 3 en módulo 7, se tiene:
a[3] = 3 (mód 7)
entonces:
(a[3])^3 = 27 (mód 7)
pero:
27 = 6 (mód 7)
entonces:
(a[3])^3 = 6 (mód 7)

Para los congruentes con 4 en módulo 7, se tiene:
a[4] = 4 (mód 7)
entonces:
(a[4])^3 = 64 (mód 7)
pero:
64 = 1 (mód 7)
entonces:
(a[4])^3 = 1 (mód 7)

Para los congruentes con 5 en módulo 7, se tiene:
a[5] = 5 (mód 7)
entonces:
(a[5])^3 = 125 (mód 7)
pero:
125 = 6 (mód 7)
entonces:
(a[5])^3 = 6 (mód 7)

Y, finalmente, para los congruentes con 3 en módulo 7, se tiene:
a[6] = 6 (mód 7)
entonces:
(a[6])^3 = 216 (mód 7)
pero:
216 = 6 (mód 7)
entonces:
(a[6])^3 = 6 (mód 7)

Tenemos, finalmente:
(a[0])^3 = 0 (mód 7)
(a[1])^3 = 1 (mód 7)
(a[2])^3 = 1 (mód 7)
(a[3])^3 = 6 (mód 7)
(a[4])^3 = 1 (mód 7)
(a[5])^3 = 6 (mód 7)
(a[6])^3 = 6 (mód 7)

Con esto se deduce que todo cubo de entero es congruente con 0 , 1 , ó 6 en módulo 7.

[MasterIN®]

Problema 1

Demostrar que 41 divide a 2^20 - 1

SOL

Primero, nos damos cuenta que debemos llegar a 2^20=1 mod 41...eso es como intuitivo....

Bueno... experimentando un poco, se nota que:

2^10 = -1 (mod 41)
(2^10)^2 = (-1)^2 (mod 41)
2^20 = 1 (mod 41) /-1
2^20-1= 0 (mod 41)

gracias....



by mAsTeR®

[Guía Rojo]

Demuestre que:

Primero, veamos el desarrollo de :


Algo complicado, pero sin asustarse, es sólo el binomio de Newton...

Pero como es primo, entonces será múltiplo de (para entero)

(Demostración)

Como es primo, ningún entero positivo menor que él (excepto el 1) lo divide...
tiene en su factorización prima a , y como lo estamos dividiendo por dos factoriales de enteros menores que (que no tienen a en su factorización prima), el cociente seguirá siendo un múltiplo de

Cada término es múltiplo de , excepto y

Tenemos entonces:


Probando lo pedido...

[Francisco Muñoz]

Demuestre que:
(a+b)^p = a^p + b^p (mód p)

Este problema al igual que el anterior serian muy sencillo si se pudiese ocupar el pequeño teorema de fermat, ya que:


1) (a+b)^p = a + b (mód p) ,y ademas

2) a^p = a (mód p)
3) b^p = b (mód p)

entonces de 2) y 3) se deduce que:

4) a^p + b^p= a+b (mód p) , por simetria de la congruencia, se obtiene:

5) a+b = a^p + b^p(mód p) , y ahora por transitividad de conguencia modulo (de 1) y 5) ), nos da lo pedido:

(a+b)^p = a^p + b^p (mód p).

Bueno eso seria, el metodo de Peñe, tb esta correcto e incluso es mas explicativo que este, para aquellas personas que aun comenzando con congruencia, porque segun lo que veo la idea es justamente no usar este teorema ...pero bueno...

Francisco Muñoz Espinoza

[Guía Rojo]

Había quedado en demostrar que (p!/(p-r)!r!) es múltiplo de p.

Sabemos ke este número es entero (p sobre r).
Pero (p-r)! ni r! tienen divisores comunes con p, ya que éste es primo. Por lo tanto, (p!/(p-r)!r!) = (p * (p-1)!/(p-r)!r!)

(p-1)!/(p-r)!r! es entero, ke se deduce de lo anterior. Por lo tanto, "p sobre r" es múltiplo de p.

[Guía Rojo]

Bueno, esta demostración resuelve el ejercicio 12, pero tomándose b=1 , se resuelve el ejercicio 11 también .

Guía Rojo

[MasterIN®]

ia..... el problema 5...es así:

fijemonos que: a^2-a = a(a-1) ==> el producto de dos numeros consecutivos...

Por otro lado, expresemos a como:

Reemplazaramos inmediatamente 10^0 por 1

1*x0+10^1*x1+10^2*x2+10^3*x3+...................+10^k*xk
xi= x sub i , y k es un entero positivo.

Bueno...según eso, a-1 esta dado por:

1*(x0-1)+10^1*x1+10^2*x2+10^3*x3+...................+10^k*xk

para verlo de manera más simple, digamos que sea y=10^1*x1+10^2*x2+10^3*x3+...................+10^k*xk . entonces y=0 (mod10)

entonces: a= x0 + y ==> a= x0 (mod 10)
a-1= (x0-1) +y ==> a-1= x0-1 (mod 10)

Osea, a*(a-1)= x0 * (x-1) (mod 10) donde x0 es un digito del 0 al 9.

Ufff... la media explicacion para decir que el resto que deja un numero en la division por 10 es la unidad....eso es todo...xD,...pero para que sepan el por qué...ahi ta...

Sigamos....solo hay que reemplazar:

Entonces, los productos posibles son:
0*1= 0 +7= 7 (congruente con 7 mod 10)
1*2= 2 + 7= 9 (congruente con 9 mod 10)
2*3=6 +7 = 13 (congruente con 3 mod 10)
3*4= 12 +7 = 19 (congruente con 9 mod 10)
4*5= 20 +7 = 27 (congruente con 7 mod 10)
5*6= 30 +7 = 37 (congruente con 7 mod 10)
6*7= 42 +7 = 49 (congruente con 9 mod 10)
7*8= 56 +7= 63 (congruente con 3 mod 10)
8*9= 72 +7 = 79 (congruente con 9 mod 10)

Listo.,..y como se mostró anteriormente, la congruencia en mod 10 de un numero es el último dígito, el cual en este caso puede ser: 9,3 ó 7....fin...gracias

QUEPD

by mAsTeR® ... volviendo a empezar desde lo más básico...

[MasterIN®]

El 7....

notemos que :

2^11 = 1 (mod. 89)
(2^11)^4 = 1^4 (mod. 89)
2^44 = 1 (mod 4) ===> 2^44 -1 = 0 (mod. 89)

Gracias

QUEPD

Empezando desde lo más básico

by mAsTeR®

[MasterIN®]

Ia-.el 6

ia..primero como decía el hint: 495= 5*9*11

Osea..el numero es divisible por 5 por 11 y por 9...vamos a usar los "principios" del colegio, pero los vamos a demostrar al principio.

Ia....el del 9.

Sea un número N= a0*10^0 + a1*10^1 + a2*10^2 + ...... + ak*10^k

Donde ai es a sub i y k es un numero entero y positivo.

DIVISIBILIDAD POR 9
Bueno..Notemos que 10 = 1 (mod 9) x lo que cualquier potencia de 10 deja resto 1 mod 9.

Si??? reemplazan eso osea...

N = a0*1 + a1*1 + a2*1 + ...... + ak*1 (mod. 9)

En otras palabras, para que N sea congruente con 0 mod. 9, o dicho de otra forma, que 9|N , entonces, a1+a2+a3.....+ak= 0 (mod.9), osea, la suma de los dígitos de N debe ser un múltiplo de 9.

Para hacer el criterio para el 3 es igual.

DIVISIBILIDAD POR 5

Dejemos el mismo número N, y ahora démonos cuenta que 10= 0 (mod 5) , por lo que toda potencia de 10 (mayor que 0) deja resto 0 mod. 5

Entonces , sea y = a1*10^1 + a2*10^2 + ...... + ak*10^k

Eso claramente deja resto 0 mod. 5 asi que no entraré en detalle.

Por lo tanto:

N = y + a0 (mod 5)
N= a0 ( mod 5)

Y como a0 es un dígito del 0 al 9, para que N=0 (mod 5), a0 debe ser 0 ó 5.

Dicho en otras palabras : un número N es divisible por 5 si su último dígito es 0 ó 5

DIVISIBILIDAD POR 11

sea N = a0*10^0 + a1*10^1 + a2*10^2 + ...... + ak*10^k

Notemos que 10 = -1 (mod 11)

De donde se concluye que 10^2z= 1 (mod 11) y que 10^(2z+1) = -1 (mod. 11)

El resto tarea para la casa porque me aburri de anotar en base 10 xD
el criterio es:
Un número es divisible por 11 si la diferencia entre la suma de los dígitos que ocupan posiciones pares y la suma de los dígitos que ocupan la posición impar es divisible por 11.

----------------------------------------------------------------------------------------

PROBLEMA EN SI:

Bueno, vamos al problema:

273x49y5 ese numero debemos hacer que sea div. por 495. Y como dije anteriormente, debe ser div. por 11,9 y 5. Por 5 ya lo es. Hagamos ahora que sea div. por 9

Se debe tener que

2+7+3+x+4+9+y+5= 0 (mod. 9)
30 +x +y = 0 (mod.9)
x+y = -30 (mod 9)
x+y = 3 (mod 9)

Osea, x+y = 9a-3

Como x e y son dígitos, los posibles valores son:
x+y= 6
x+y= 15


Por otro lado.
(y+4+3+2) - (5+9+x+7) = 0 (mod. 11)

9 + y -21 -x= 0 (mod 11)
1 + y -x = 0 (mod. 11)
y-x= 10 (mod. 11)

Entonces y-x= 11k - 10

Osea, y-x= 1

Luego:

x+y=6
y-x= 1
--------------
2y= 7 no sirve......

x+y= 15
y-x= 1
---------------
2y= 16 ==> y = 8 , por lo tanto x=7

Por lo que el número buscado es 27374985

FIN.-..graciaas......


by mAsTeR®