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.
lunes, 10 de octubre de 2011
Problema del día, Teoría de números (10 de Octubre)
Ya que Karina y Daniel andan de viaje yo pondré los problemas de hoy y del miercoles.
Demuestra que $(n-1)^2$ divide a $n^{n-1}-1$ para todo entero $n$ con $n \geq 2$
entonces $n-1$ divide a $n^{n-1} -1 $, si $n-1$ dividiera a $ (n^{n-2} + \cdots + n + 1)$ entonces ya acabariamos
$ n \equiv n -(n-1) \equiv 1 mod n-1$ por ende $ n^k \equiv 1 mod n-1 $ y por lo tanto $ (n^{n-2} + \cdots + n) +1 \equiv (n-2) +1 mod n-1$ ya que hay $n-2$ factores de $n$, (n-2) +1 \equiv n-1 equiv 0 mod n-1
por ende $n-1$ divide a $(n^{n-2} + \cdots + n + 1)$ y por lo tanto $(n-1)^2$ divide a $n^{n-1} -1$
tenemos que $n^{n-1}-1=(n-1)(n^{n-2}+...+n+1)$ por lo tanto n-1 divide a $n^{n-1}-1$ y queremos que n divida a lo otro y como $n^{n-2},...,n$ son multiplos de n van a ser congruentes a -1 mod n-1 y esto se sumara n-2 veces, entonces la suma de todo eso va a ser congruente n-2 mod n-1 y 1 es congruente a 1 mod n-1 por lo tanto la suma de rodo esto es congruente a n-1 mod n-1 que es congruente a 0 y por lo tanto $(n-1)^2$ divide a $n^{n-1}-1$
Se puede decir que $n^{n-1}-1=(n-1)(n^{n-2}+ \dots +1)$ y el demuestra el problema si $n-1$ divide a $(n^{n-2}+\dots+n+1)$
Sabemos que cualquer multiplo de n sera congruente a 1 mod n-1 por lo que la suma anterior seria de n-1 unos y eso suman n-1 y es divisible entre n-1 y queda demostrado.
Primero factorizé $(n-1)^2$ y $n^{n-1}-1$ en $(n-1)(n-1)$ y $(n-1)(n^{n-2}+n^{n-3}+ ... + n+1)$ respectivamente. Si a*a*k=a*b entonces a*k=b, aplicando eso al problema, para demostrar que $(n-1)(n-1)$ divide a $(n-1)(n^{n-2}+n^{n-3}+ ... + n+1)$ basta con demostrar que n-1 divide a $(n^{n-2}+n^{n-3}+ ... + n+1)$. Vemos todo en mod n-1, como en todos son n's elevadas a alguna potencia, se pueden ver como 1's (porque n≡1 mod n-1) que elevados a cualquier potencia es 1, como estamos sumando los 1's con exponente de 0 hasta n-2, tenemos n-1 1's que sumados dan n-1 y por tanto congruencia 0. Para n=1, n-1=0, $0^2=0$ y creo que 0 no divide a ningún número. (No encontré una respuesta distinta a la que ya habían dicho)
Se expresa $n^(n-1) -1$ como una Diferencia de Potencias y se obtiene la siguiente igualdad: $n^{n-1} - (1)^ {n-1} = (n-1)(n^{n-2}*1^{0} + n^{n-3}*1^{1} + \cdots + n^{1}*1^{n-3} + n^{0}*1^{n-2})$. Se observa claramente que entonces, $n-1$ divide a $n^{n-1} -1$. Ahora resta demostrar que $n-1$ divide a $(n^{n-2}*1^{0} + n^{n-3}*1^{1} + \cdots + n^{1}*1^{n-3} + n^{0}*1^{n-2})$. Se llama a esta ecuación $\alpha$. En este paso tuve la idea de usar la formula de suma de potencias e intentar utilizar las igualdades obtenidas pero me di cuenta que estaba en algo incorrecto (Solo como comentario). De vuelta al problema, entonces es posible decir que: $(n^{n-2}*1^0 + n^{n-3}*1^1 + \cdots + n^1*1^{n-3} + n^0*1^{n-2}) = (n^{n-2} + n^{n-3} + \cdots + n^1 + n^0)$, ($1$ a k potencia seguirá siendo $1$). Se tiene una suma de potencias de base $n$ desde $n^0$ hasta $n^{n-2}$. Cada base $n$ es congruente a $1 \pmod{n-1}$. (De manera que 4 es congruente con 1 mod 3, por dar un ejemplo) Entonces se representa la ecuación antes mencionada como: $ n^{n-2} + n^{n-3} + \cdots + n^{1} + n^{0} \equiv (1)^{n-2} + (1)^{n-3} + \cdots + (1)^{1} + (1)^{0} $ Al tener $n-1$ elementos sumándose, el valor de esta operación será $n-1$. Por lo tanto, $n-1$ divide a $\alpha$. De esta queda demostrado lo que se pide.
$n^{n-1} -1 = (n-1)(n^{n-2} + \cdots + n + 1)$
ResponderBorrarentonces $n-1$ divide a $n^{n-1} -1 $, si $n-1$ dividiera a $ (n^{n-2} + \cdots + n + 1)$ entonces ya acabariamos
$ n \equiv n -(n-1) \equiv 1 mod n-1$ por ende
$ n^k \equiv 1 mod n-1 $ y por lo tanto
$ (n^{n-2} + \cdots + n) +1 \equiv (n-2) +1 mod n-1$ ya que hay $n-2$ factores de $n$,
(n-2) +1 \equiv n-1 equiv 0 mod n-1
por ende $n-1$ divide a $(n^{n-2} + \cdots + n + 1)$ y por lo tanto $(n-1)^2$ divide a $n^{n-1} -1$
Sabemos que $n^{n-1}-1=(n-1)(n^{n-2}+ \dots +1)$
ResponderBorrarEntonces aqui hay un $n-1$, y queremos que $n-1$ tambien divida a lo demas.
$n^{n-2}+ \dots +n+1 \equiv (1)^{n-2}+ \dots + (1) + 1 \equiv 1+ \dots +1 \equiv n-1 \equiv 0 \pmod{n-1}$
Entonces $(n-1)^2$ divide a $n^{n-1}-1$
tenemos que $n^{n-1}-1=(n-1)(n^{n-2}+...+n+1)$ por lo tanto n-1 divide a $n^{n-1}-1$ y queremos que n divida a lo otro y como $n^{n-2},...,n$ son multiplos de n van a ser congruentes a -1 mod n-1 y esto se sumara n-2 veces, entonces la suma de todo eso va a ser congruente n-2 mod n-1 y 1 es congruente a 1 mod n-1 por lo tanto la suma de rodo esto es congruente a n-1 mod n-1 que es congruente a 0 y por lo tanto $(n-1)^2$ divide a $n^{n-1}-1$
ResponderBorrarSe puede decir que
ResponderBorrar$n^{n-1}-1=(n-1)(n^{n-2}+ \dots +1)$
y el demuestra el problema si $n-1$ divide a
$(n^{n-2}+\dots+n+1)$
Sabemos que cualquer multiplo de n sera congruente a 1 mod n-1 por lo que la suma anterior seria de n-1 unos y eso suman n-1 y es divisible entre n-1 y queda demostrado.
Entonces $(n-1)^2$ divide a $n^{n-1}-1$
llo llegue a que $n^{n-1}-1\$ es igual a
ResponderBorrar${n-1}\$ ${n^{n-2} +\cdots +n+}1$
por lo cual ya tenemos que ${n-1}\$ divide a
$n^{n-1}-1\$
y luego tenemos que ${n^{n-2} +\cdots +n+1}\$ es multiplo de n
y eso es todo a lo que he llegado lo seguire intentando
Primero factorizé $(n-1)^2$ y $n^{n-1}-1$ en $(n-1)(n-1)$ y $(n-1)(n^{n-2}+n^{n-3}+ ... + n+1)$ respectivamente. Si a*a*k=a*b entonces a*k=b, aplicando eso al problema, para demostrar que $(n-1)(n-1)$ divide a $(n-1)(n^{n-2}+n^{n-3}+ ... + n+1)$ basta con demostrar que n-1 divide a $(n^{n-2}+n^{n-3}+ ... + n+1)$. Vemos todo en mod n-1, como en todos son n's elevadas a alguna potencia, se pueden ver como 1's (porque n≡1 mod n-1) que elevados a cualquier potencia es 1, como estamos sumando los 1's con exponente de 0 hasta n-2, tenemos n-1 1's que sumados dan n-1 y por tanto congruencia 0. Para n=1, n-1=0, $0^2=0$ y creo que 0 no divide a ningún número. (No encontré una respuesta distinta a la que ya habían dicho)
ResponderBorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarProblemas con LATEX una disculpa.
ResponderBorrarSe expresa $n^(n-1) -1$ como una Diferencia de Potencias y se obtiene la siguiente igualdad:
$n^{n-1} - (1)^ {n-1} = (n-1)(n^{n-2}*1^{0} + n^{n-3}*1^{1} + \cdots + n^{1}*1^{n-3} + n^{0}*1^{n-2})$.
Se observa claramente que entonces, $n-1$ divide a $n^{n-1} -1$. Ahora resta demostrar que $n-1$ divide a $(n^{n-2}*1^{0} + n^{n-3}*1^{1} + \cdots + n^{1}*1^{n-3} + n^{0}*1^{n-2})$. Se llama a esta ecuación $\alpha$.
En este paso tuve la idea de usar la formula de suma de potencias e intentar utilizar las igualdades obtenidas pero me di cuenta que estaba en algo incorrecto (Solo como comentario).
De vuelta al problema, entonces es posible decir que:
$(n^{n-2}*1^0 + n^{n-3}*1^1 + \cdots + n^1*1^{n-3} + n^0*1^{n-2}) = (n^{n-2} + n^{n-3} + \cdots + n^1 + n^0)$, ($1$ a k potencia seguirá siendo $1$).
Se tiene una suma de potencias de base $n$ desde $n^0$ hasta $n^{n-2}$.
Cada base $n$ es congruente a $1 \pmod{n-1}$. (De manera que 4 es congruente con 1 mod 3, por dar un ejemplo)
Entonces se representa la ecuación antes mencionada como:
$ n^{n-2} + n^{n-3} + \cdots + n^{1} + n^{0} \equiv (1)^{n-2} + (1)^{n-3} + \cdots + (1)^{1} + (1)^{0} $
Al tener $n-1$ elementos sumándose, el valor de esta operación será $n-1$. Por lo tanto, $n-1$ divide a $\alpha$.
De esta queda demostrado lo que se pide.
@Chuy,Alberto,Antonio,Alberto Ponce,Alex: tienen un detalle tan pequeño que lo voy a pasar por alto :) (ver siguiente comentario)
ResponderBorrar@Luis: Muy bien en mencionar al $1$ :)
@Martin: Sigue intentando :P