Olimpiada de Matemáticas en Chihuahua: Problema del día. Teoría de números. (9 de octubre)

martes, 9 de octubre de 2012

Problema del día. Teoría de números. (9 de octubre)

Si se tiene que

$a^n\equiv a \pmod n$ para toda

$a$ entera, se dice que

$n$ es un número de Carmichael cuando

$n$ es compuesto. Muestre que

$1,105$ es de Carmichael.

12 comentarios:

antonio lopez14 de octubre de 2012, 6:47 p.m.
Veo que $1105=5*13*17$ luego analizo las congruencias con cada factor primo y utilizando fermat me fijo que :
$a^4\equiv 1\pmod 5$
$a^12\equiv 1\pmod 13$
$a^16\equiv 1\pmod 17$
Luego:
$a^1104=(a^4)^276\equiv 1\pmod 5$
$a^1104=(a^12)^92\equiv 1\pmod 13$
$a^1104=(a^16)^69\equiv 1\pmod 17$

Entonces $a^1104\equiv 1\pmod 1105$
entonces $a^1105\equiv a\pmod 1105$ .Q.E.D
ResponderBorrar
Respuestas
Luis Chacón14 de octubre de 2012, 7:11 p.m.
$1104=3\times 2^4\times 23$ , entonces 1104 es múltiplo de $4,12,16$
$1105=5\times 13 \times 17$ .
Como 5,13,17 son primos, entonces $a^4\equiv 1 \pmod{5},a^{12}\equiv 1 \pmod{13},a^{16}\equiv 1 \pmod{17}$ para $a\not\equiv 0$ .
$a^{1105}=a^{1104}\times a\equiv (a^4)^{276}\times a\equiv a(1^{276})=a \pmod{5}$
$a^{1105}=a^{1104}\times a\equiv (a^{12})^{92}\times a\equiv a(1^{92})=a \pmod{13}$
$a^{1105}=a^{1104}\times a\equiv (a^{16})^{69}\times a\equiv a(1^{69})=a \pmod{17}$
Y si $a\equiv 0 \pmod{5,13,17}$ entonces $a^{1105}\equiv 0^{1105}=0\equiv a \pmod{5,13,17}$
Entonces $a^{1105}\equiv a \pmod{5},a^{1105}\equiv a \pmod{13},a^{1105}\equiv a \pmod{17}$
Resolvemos con el teorema chino del residuo porque 5,13,17 son primos relativos.
$a_1=13\times 17=221, b_1=a, c_1\equiv a_1^{-1}=221^{-1}\equiv 1^{-1}=1 \pmod{5}$
$a_2=5\times 17=85, b_2=a, c_2\equiv a_2^{-1}=85^{-1}\equiv 7^{-1}=2 \pmod{13}$
$a_3=5\times 13=65, b_3=a, c_3\equiv a_3^{-1}=65^{-1}\equiv -3^{-1}=-6 \pmod{17}$
$a^{1105}\equiv a_1b_1c_1+a_2b_2c_2+a_3b_3c_3 \pmod{5\times 13\times 17}$
$\Rightarrow a^{1105}\equiv (221)(a)(1)+(85)(a)(2)+(65)(a)(-6)\pmod{1105}$
$\Rightarrow a^{1105}\equiv 221a+170a-390a \pmod{1105}$
$\Rightarrow a^{1105}\equiv a \pmod{1105}$
Por lo tanto, 1105 es Carmichael.
ResponderBorrar
Respuestas
Diego Astiazarán14 de octubre de 2012, 9:25 p.m.
Este comentario ha sido eliminado por el autor.
ResponderBorrar
Respuestas
Diego Astiazarán14 de octubre de 2012, 9:29 p.m.
Sabemos que $1105 = 5 \times 13 \times 17$ , utilizando el Pequeño Teorema de Fermat, tenemos que:
$a^{4} \equiv 1 \pmod {5}$
$a^{12} \equiv 1 \pmod {13}$
$a^{16} \equiv 1 \pmod {17}$
$\Rightarrow$
$a^{1104} = (a^{4})^{276} \equiv 1 \pmod {5}$
$a^{1104} = (a^{12})^{92} \equiv 1 \pmod {13}$
$a^{1104} = (a^{16})^{69}\equiv 1 \pmod {17}$
$\therefore$ Tenemos que:
$a^{1104} \equiv 1 \pmod {5 \times 13 \times 17}$
$a^{1104} \equiv 1 \pmod {1105}$
Multiplicamos por $a$ :
$a^{1104}(a) \equiv 1(a) \pmod {1105}$
$a^{1105} \equiv a \pmod {1105} \quad \blacksquare$
ResponderBorrar
Respuestas
Unknown14 de octubre de 2012, 9:53 p.m.
Por pequeño teorema de Fermat sabemos que:
$a^p\equiv a\ mod p$ y $a^{p-1}\equiv 1\ mod p$
Queremos demostrar que:
$a^{1105}\equiv a\ mod 1105$ $\leftarrow$ $a^{1104}\equiv 1\ mod 1105$

Factorizamos $1105 y 1104$
$1105=5*13*17$
$1104=16*3*23$

Por Fermat en los factores de $1104 y 1105$ tenemos que
$a^16\equiv 1\ mod 17$
$a^12\equiv 1\ mod 13$
$a^4\equiv 1\ mod 5$

$(a^16)^{69}\equiv 1\ mod 17$
$(a^12)^{92}\equiv 1\ mod 13$
$(a^4)^{276}\equiv 1\ mod 5$

Por el criterio de Korselt que dice: Un número natural $n$ es de Carmichael si y sólo si es libre de cuadrados y para todo $k$ factor primo de su descomposición se cumple que $k-1$ es un divisor de $n-1$ .

Por su factorizacion $1105$ es libre de cuadrados y se cumple que $17-1,13-1,5-1$ son divisores de $1104$

$\therefore$
$a^{1104}\equiv 1\ mod 1105$
$a^{1105}\equiv a\ mod 1105$
$Q.E.D$
ResponderBorrar
Respuestas
Unknown14 de octubre de 2012, 10:09 p.m.
Por el pequeño Teorema de Fermat:
$a^{4}\equiv{1}\pmod{5}$ , $a^{12}\equiv{1}\pmod{13}$ , $a^{16}\equiv{1}\pmod{17}$
Debido a que: $1004=3*2^{4}*23\Rightarrow (4, 12, 16)|1104$ tendremos el siguiente sistema de congruencias:
$a^{1004}\equiv{1}\pmod{(5, 13, 17)}$
Aplicando Teorema Chino del Residuo, tenemos que:
$a_1=221$ , $b_1=1$ , $c_1=1$ , $n_1=5\Rightarrow a_1b_1c_1=221*1*1=221$
$a_2=85$ , $b_2=1$ , $c_2=2$ , $n_2=13\Rightarrow a_2b_2c_2=85*1*2=170$
$a_3=65$ , $b_3=1$ , $c_3=11$ , $n_3=17\Rightarrow a_3b_3c_3=65*1*11=715$
De aquí que: $a_1b_1c_1+a_2b_2c_2+a_3b_3c_3=221+170+715=1106$
Entonces:
$a^{1004}\equiv{1106}\equiv{1}\pmod{1105}$
$\Rightarrow a^{1105}\equiv{a}\pmod{1105}$
Por lo que $1105$ es de Carmichael Q.E.D.
ResponderBorrar
Respuestas
Unknown14 de octubre de 2012, 10:32 p.m.
http://s739.photobucket.com/albums/xx34/leo0_9506/Ommch/?action=view&current=CAM001491.jpg

Muy buen problema por cierto:))
ResponderBorrar
Respuestas
Pepe Flores14 de octubre de 2012, 11:28 p.m.
Tenemos que $a^1^1^0^5\equiv a (mod1105)$ Entonces $a^1^1^0^4\equiv 1 (mod1105)$

Luego, usando el Peque;o teorema de Fermat:
$a^4\equiv 1 (mod5)$
$a^1^2\equiv 1 (mod13)$
$a^1^6\equiv 1 (mod17)$

Luego lo elevamos y nos queda que:
$(a^4)^2^7^6\equiv 1 (mod5)$ = $a^1^1^0^4\equiv 1 (mod5)$
$(a^1^2)^9^2\equiv 1 (mod13)$ = $a^1^1^0^4\equiv 1 (mod13)$
$(a^1^6)^6^9\equiv 1 (mod17)$ = $a^1^1^0^4\equiv 1 (mod17)$

Entonces $a^1^1^0^5\equiv a (mod 5, 13, 17)$

Luego usamos el teorema chino del residuo y nos queda que
$a_1=221$ , $b_1=a$ , $c_1=1$
$a_2=85$ , $b_2=a$ , $c_2=2$
$a_3=65$ , $b_3=a$ , $c_3=11$

Entonces $a^1^1^0^5\equiv 221a+170a+715a=1106a=a (mod1105)$

Q.E.D
ResponderBorrar
Respuestas
martin contreras carrera15 de octubre de 2012, 5:49 p.m.
sabemos que 1005=5*13*17 y sabemos que $a^4\equiv 1(mod5)$ $a^{12}\equiv 1( mod 13$ y que $a^{16}\equiv 1 (mod 17)$
y luego sabemos que
$a^{1005}\equiv a (mod 5,13,17)$ ya que 1004 es multplo de 12,4,6
entonces aplicamos teorema chino del residuo y nos da que
$a_1=221,b_1=a,c_1=1$
$a_2=85,b_2=a,c_2=2$
$a_3=65,b_3=a,c_3=11$
y al final nos da que $a^{1005}\equiv 1006a = a (mod 13*5*17=1005)$ y acabamos
ResponderBorrar
Respuestas

Olimpiada de Matemáticas en Chihuahua

martes, 9 de octubre de 2012

Problema del día. Teoría de números. (9 de octubre)

12 comentarios:

SC

Google Analytics