\[ S_{k}= 1^{k}+2^{k}+\ldots+(p-1)^{k} \] Determina los valores de $k \in \mathbb{N} $ para los cuales $ p\, |\, S_{k} $.
jueves, 6 de enero de 2011
Problema del 6 de enero
Sea $p>2$ un número primo dado y sea
Suscribirse a:
Comentarios de la entrada (Atom)
24 comentarios:
Osea que para una $k$ definida, toda $p>2$ funciona?
El primo $p$ es fijo
Vemos que para $k$ par no funciona el problema.
Para esto, tomamos $p=3$, y tenemos que:
$S_k=1+2^(2m)$, pero $2^2=3x+1$ por lo que $(2^2)^m=2^(2m)=(3x+1)^m=(3x)^m+(3x)^(m-1)+...+3x+1=3y+1$ y por tanto, $2^(2m)+1=3y+2$ y $3$ no divide a $1+2^(2m)=S_k$.
Ahora veamos que para $k$ impar funciona:
Como $k$ es impar, sabemos que $p$ divide a $(p-a)^k+a^k$ para todo entero positivo $a$ menor a $(p+1)/2$. Con esto obtenemos que $p$ divide a:
$1^k+(p-1)^k+2^k+(p-2)^k+...+((p-1)/2)^k+((p+1)/2)^k$
y reordenando términos obtenemos:
$1^k+2^k+...+(p-1)^k=S_k$
Entonces concluimos que para toda $k$ impar funciona y para toda $k$ par no.
Oops... no había leído el comentario arriba, esa es una solución para una $k$ fija, que todos los $p$ funcionan...
reconosco este problema. problema 1 binacional Hungria-Israel 2009. Es trivial con raices primitivas y es cierto cuando p-1 no divide a k.
Mas aun, S_(r(p-1))=p-1 mod p.
Sea g raiz primitiva de p. tenemos que (1,g,...,g^(p-2)) es una permutacion modulo p de (1,2,...,p-1) porlotanto S_k=1+g^k+g^(2k)+...+g^(k(p-1)) mod p.
Si p-1|k entonces S_k=1+1^1+1^2..+1^(p-2) =p-1 mod p.
Si no,entonces g^k=t diferente de 1. Entonces S_k=(t^(p-1)-1)/(t-1). por fermat p|t^(p-1)-1 y aparte p no divide a t-1, entonces p|S_k
Como estoy seguro de que leíste esa solución, me gustaría que hicieras una distinta Diego. (Si hay)
esto es lo que llevo hasta ahora:
los numeros del 1 al p-1 son primo relativos con p, nota : "n" es un numero del 1 al p-1, y "==" simboliza "congruente a"
para k=0 no cumple ya que s_0=p-1.
para k=p cumple ya qe por fermat n^p == n Mod p, ademas que p es impar, por lo que s_p == 1+2+3+...+(p-1)== (p-1)p/2 == 0 Mod p. por lo que p divide a s_p.
Por fermat n^p==n Mod p, si k= tp+s con s entre 1 y p-1 , entonces(1) n^k==n^tp+s==((n^p)^t)(n^s)==(n^t)(n^s)==n^t+s Mod p.
Si k es multiplo de p-1, entonces k=b(p-1)=bp-b, entonces n^k==n^b-b==n^0==1 Mod p.
entonces para k muliplo de p-1, se tiene que s_k==p-1 Mod p, por lo que p no divide a s_k.
si k=b(p-1)+m=bp+m-b con m entre 1 y p-2, entonces n^k==n^b-b+m==n^m Mod p. entonces s_k==s_m Mod p. por lo que si se demuestra que para k entre 1 y p-2 se cumple la condicion, entonces para todo k no multiplo de p-1 se cumplira la condicion. para k=1,2,3 se verifica el resultado facilmente, para 1 haciendo suma de gauss, para 2 usando la formula de suma de cuadrados y tomando en cuanta que p mayor que 3, ya que para p=3 se tiene que cumple k=1 y k=3, pero k=2 no cumple.
Y para k=3 la formula de suma de cubos, tomando en cuenta que p mayor que 2.
Ademas hize una demostracion para k impar como lo hizo Adan, entonces me falta demostrar que la condicion se cumple para k par entre 4 y p-3.
no la lei, segun yo ya habiamos vito este problma en un entrenamiento
ya tengo una solucion con funciones generatrices. Tenemos que por fermat S_k es congruente a p-1 si k es multiplo de p-1. Y si no lo es entones sea k=(p-1)t+r con 0r>=i+1>i>=0 entonces p>i+1>0 Entonces p divide a C(p,i+1) y porlotanto divide a T_r. Entonces p divide a S_k cando p-1 no divide a k
argh, el html confundio y elimino coas que habia escrito. Aunque seguramente si ves directamente el codig html de la pagina podras leer la solucion completa
No se ve en el codigo HTML, Blogger elimina automaticamente cualquier cosa que pueda traer conflicto, por lo que si por accidente pones un menor que y luego un mayor que, todo lo que estaba entre esos dos simbolos se elimina.
Bueno, lo volvere a escribir. Notese que C(n,k) es "n en k". Sea k=(p-1)t+r con p-2 mayor o igual r mayor o igual 0. Entonces por fermat, S_k=S_r mod p.
Si r=0 entonces por fermat S_r=1+1+1+(p-1 veces)+1+1=p-1 mod p porlotanto p no divide a S_k. Supongamos que r mayor a 0
Es un hecho conocido que si p(x) es un polinomio de grado r tal que para todo n entero "suficientemente grande" p(n)es entero, entonces p(x)=c_rC(x,r)+c_{r-1}C(x,r-1)+...+c_0C(x,0) donde c_i es entero y C(x,r)=(x)(x-1)(x-2)...(x-r+1)/(r!).
De hecho, este fue el segundo problema que se posteo en el blog y ahi pueden consultar su demostración. (http://a-la-imo.blogspot.com/2010/05/problema-de-polinomios.html)
En particular p(x)=x^r cumple estas caracteristicas. Digamos que n^r=a_0C(n,0)+a_1C(n,1)+...+a_rC(n,r). Tenemos que la funcion generatriz de la sucecion (C(0,r),C(1,r),C(2,r),...) es x^r/(1-x)^(r+1). Porlotanto la funcion generatriz de (0^r,1^r,2^r,..) es q(x)=a_0/(1-x)+a_1x/(1-x)^2+...+a_rx^r/(1-x)^(r+1).
La funcion generatriz de (0^r,0^r+1^r,0^r+1^r+2^r,...) es (q(x))/(1-x)=q(x)=a_0/(1-x)^2+a_1x/(1-x)^3+...+a_rx^r/(1-x)^(r+2). Tenemos que x^r/(1-x)^(r+2) es la funcion generatriz de (C(1,r+1),C(2,r+1),C(3,r+1)...) porlotanto (q(x))/(1-x) tambien es la funcion generatriz de (a_0C(1,1)+a_1C(1,2)+...+a_rC(1,r+1),a_0C(2,1)+a_1C(2,2)+...+a_rC(2,r+1),...).
Porlotanto 0^r+1^r+2^r+...+n^r=a_0C(n+1,1)+a_1C(n+1,2)+...+a_rC(n+1,r+1). Osea S_r=0^r+1^r+2^r+...+(p-1)^r=a_0C(p,1)+a_1C(p,2)+...+a_rC(p,r+1). Si r+1(mayor o igual) i (mayor o igual) 1 entonces p-1 (mayor o igual) r+1 (mayor o igual) i (mayor o igual) 1 entones p|C(p,i) para todo i entre 1 y r+1 porlotanto p|S_r porlotanto p|S_k.
Si k es impar entonces por congruencias p divide a $x^k + (p-x)^k$ para $x=1,2,...,(p-1)/2$ y sumando las parejas nos da que P divide a $S_k$
Para k par
Como p es primo existe una congruencia (g) mod p que es raiz primitiva y por lo tanto
$S_k = 1 + g^k + g^{2k} + ... + g^{(p-2)k} mod p $ (en algun orden) queimplica que
$S_k= [g^{(p-1)k}-1]/[g^{k}-1] = [g^{k}-1]/[g^{k}-1] mod p $
Si $g^{k}$ no es congruente con 1 mod p, entonces podemos dividirlos y nos queda que $S_k = 1 mod p$ por lo que no lo divide.
y si $g^{k}=1 mod p$ como el orden de g mod p es p-1 entonces p-1 divide a k, y si esto pasa sabemos por Fermat que $a^k=1 mod p$
entonces $S_k=1+1+...+1=p-1 mod p$ y por lo tanto tampoco lo divide.
Entonces p divide para k impar.
Daniel:
5|1^2+2^2+3^2+4^2=30
Pues aqui dejo lo que llevo, no es mucho:
Es fácil notar que para todo k múltiplo de p-1 no funciona, ya que por Fermat, tenemos que cada uno es congruente a 1(modp), entonces la suma es congruente a: p-1(modp) entonces p no lo divide.
Después observamos que para k impar siempre funciona, ya que: i\equiv-(p-i)(modp)\Rightarrowi^{k}\equiv-(p-i)^{k}(modp)\Rightarrow p\mid i^{k}+(p-i)^{k}, con lo que vemos que p\mid\left[1^{k}+(p-1)^{k}+2^{k}+(p-2)^{k}+...+\left(\frac{p-1}{2}\right)^{k}+\left(\frac{p+1}{2}\right)^{k}\right]
Asociemos de la siguiente manera a los términos de S_k= (1^k+(p-1)^k) + (2^k +(p-2)^k) + ... + (((p-1)/2)^k + ((p+1)/2)^k)
Esto es posible ya que como p>2, p es impar.
De ésto podemos ver que si k es impar, cáda parte dentro del paréntesis es múltiplo de p tenemos que:
S_k= (1^k + (1^k)*((-1)^k) + (2^k + )2^k)*((-1)^k) +...+(((p-1)/2)^k + (((p-1)/2)^k)*((-1)^k) (mod p)
De manera que si k es impar, cada par de términos se convierten en 0 en su asociación y como contamos con una cantidad par de términos (en otras palabras, podemos completar las asociaciones de la manera que ya hicimos) p|S_k
Ahora, si k=r(p-1) con r natural, por el pequeño Teorema de Fermat, tenemos que S_K=1 + 1 + 1 +…+ 1 = p-1 (mod p) y por lo mismo, p no lo divide.
Mientras que si k no es múltiplo de p-1 tenemos que:
Ahora, consideremos a “q” como una congruencia módulo p que sea raíz primitiva, entonces sabemos que:
P|S_k <-> P|1 + g^k + g^2k +…+ g^((p-2)k) ya que S_k=1 + g^k + g^2k +…+ g^((p-2)k) (mod p)
De modo que esto se da si, y sólo si P|(g^((p-1)k) -1)/(g^k – 1)
Y como el orden de g módulo p es de p-1, por lo que g^k – 1 no es múltiplo de P y podemos saber que lo anterior se cumple si, y sólo si
P|g^((p-1)k) -1 y por el pequeño Teorema de Fermat, sabemos que:
g^((p-1)k) -1= 1 -1 (mod p) por lo que es cierto y todo lo anterior también.
pues creo que mi solucion es parecida a la de los demas, usas una raiz primitiva g y reduces el problema a ver cuando
p|1+g^t+g^2*t+...+g^((p-1)/t - 1)*t) donde t=(k,p-1)
y eso es equivalente a
p|(g^(p-1) - 1)/(g^t - 1) y eso pasa si y solo si t<>p-1, si y solo si p-1 no divide a k
Bien pues yo resolví que se puede para impares emparejando para los demás y usando fermat para demostrar que no se puede cuando p-1 divide a k, como todos los demás al parecer... ahora para p par no lo he podido hacer, y la verdad no quería ver lo que habían escrito pero ya habiendolo hecho como que no le entiendo muy bien...
alguien podría sugerirme un buen sitio sobre raices primitivas?? y/o decirme por que S_k = 1+g^t+... según a como yo entiendo eso es por que g^a (para a menor a p) te dará todos los temrinos menors a p así que g^a*k me dará algun valor de la secuencia S_k
ahora suponiendo que eso está bien, sumamos todo eso y usamos que g^(p-1)t = 1 mod p y que g^k no es congruente a 1 mod p para ver que toda esa suma es congruente a 0 mod p... por lo cual cumple para todo k, aunque no veo como eso excluye el caso k=(p-1)t...
En el Niven "Introduction to the Theory of Numbers" puedes encontrar lo que necesitas de raíces primitivas. Pero lo único que necesitas saber es que una raíz primitiva mód m es un entero k cuyo orden es $\phi (m)$. Esto equivale a que el conjunto $\{k,k^2,k^3,...,k^{\phi (m)}\}$ es un sistema reducido de residuos mod m. Otra cosa importante es que existen raíces primitivas para los números 2,4, $p^{\alpha}$ y $2p^{\alpha}$, donde $p$ es un primo impar.
Aunque este problema se puede hacer sin raíces primitivas. Se puede hacer por ejemplo por inducción la parte de mostrar que si $p-1$ no divide a $k$ entonces $p$ divide a $S_k$. El truco es el mismo que se ocupa para encontrar la suma de los cuadrados de los primeros $n$ enteros positivos, una suma telescópica.
Publicar un comentario