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 $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.
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
$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.
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$
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 :
ResponderBorrar$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
$1104=3\times 2^4\times 23$, entonces 1104 es múltiplo de $4,12,16$
ResponderBorrar$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.
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:
ResponderBorrar$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$
:)
Borrarya por fin :p
Por pequeño teorema de Fermat sabemos que:
ResponderBorrar$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$
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:
ResponderBorrar$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.
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)$
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
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