La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
martes, 9 de octubre de 2012
Problema del día. Teoría de números. (9 de octubre)
Si se tiene que an≡a(modn) 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.
Veo que 1105=5∗13∗17 luego analizo las congruencias con cada factor primo y utilizando fermat me fijo que : a4≡1(mod5) a12≡1(mod1)3 a16≡1(mod1)7 Luego: a1104=(a4)276≡1(mod5) a1104=(a12)92≡1(mod1)3 a1104=(a16)69≡1(mod1)7
Entonces a1104≡1(mod1)105 entonces a1105≡a(mod1)105.Q.E.D
1104=3×24×23, entonces 1104 es múltiplo de 4,12,16 1105=5×13×17. Como 5,13,17 son primos, entonces a4≡1(mod5),a12≡1(mod13),a16≡1(mod17) para a≢. 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.
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\leftarrowa^{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
Sinceramente no esperaba que alguien utilizara ese criterio para resolver este problema.
Tu solucion es correcta, pero en vista de que el criterio no se ve en los entrenamientos, veo necesario que si lo utilizas, entonces pongas tambien la demostracion por aqui.
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.
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
Veo que 1105=5∗13∗17 luego analizo las congruencias con cada factor primo y utilizando fermat me fijo que :
ResponderBorrara4≡1(mod5)
a12≡1(mod1)3
a16≡1(mod1)7
Luego:
a1104=(a4)276≡1(mod5)
a1104=(a12)92≡1(mod1)3
a1104=(a16)69≡1(mod1)7
Entonces a1104≡1(mod1)105
entonces a1105≡a(mod1)105.Q.E.D
1104=3×24×23, entonces 1104 es múltiplo de 4,12,16
ResponderBorrar1105=5×13×17.
Como 5,13,17 son primos, entonces a4≡1(mod5),a12≡1(mod13),a16≡1(mod17) para a≢.
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.
Teorema Chino del residuo, muy bien!
Borrar:)
Este comentario ha sido eliminado por el autor.
ResponderBorrarSabemos que 1105 = 5 \times 13 \times 17 , utilizando el Pequeño Teorema de Fermat, tenemos que:
ResponderBorrara^{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
:)
Borrarya por fin :p
Por pequeño teorema de Fermat sabemos que:
ResponderBorrara^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
Sinceramente no esperaba que alguien utilizara ese criterio para resolver este problema.
BorrarTu solucion es correcta, pero en vista de que el criterio no se ve en los entrenamientos, veo necesario que si lo utilizas, entonces pongas tambien la demostracion por aqui.
Saludos!
Por el pequeño Teorema de Fermat:
ResponderBorrara^{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.
http://s739.photobucket.com/albums/xx34/leo0_9506/Ommch/?action=view¤t=CAM001491.jpg
ResponderBorrarMuy buen problema por cierto:))
Tenemos que a^1^1^0^5\equiv a (mod1105) Entonces a^1^1^0^4\equiv 1 (mod1105)
ResponderBorrarLuego, 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)
Entoncesa^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
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)
ResponderBorrary 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