viernes, 13 de enero de 2012

Problema del jueves de números

Se me pasó postear el problema ayer. El problema es el siguiente: Considere una circunferencia centrada en el origen y radio $2^{2011}$. Cuantos puntos con coordenadas enteras están sobre la circunferencia? Y si el radio es $3^{2011}$? Y si es $2011^{2011}$? Y en general para cualquier radio de la forma $p^{2011}$ con p primo?

55 comentarios:

Adán dijo...

Mmm, podrías aclarar la notación de los radios? A que se refiere con $p^{2}011$, se refiere a, por ejemplo $2^{2}011=4011$?

Unknown dijo...

Supongo que te refieres a $p^{2011}$.

Basicamente queremos encontrar todas las parejas $(a,b)\in \mathbb{Z}^2$ tal que $p^{2011}=a^2+b^2$.

Bueno, si $p$ es $2$ entonces esta la solución $(\pm 2^{1005})^2+(\pm 2^{1005})^2=2^{2011}$. Si $a^2+b^2=2^{2011}$ entones viendo modulo $4$, tenemos que $2|a,b$ entonces ahora tenemos $a'^2+b'^2=2^{2009}$. Inductivamente se reduce a $x^2+y^2=2$. Hay cuatro soluciones/puntos para $p=2$.

Si $p\equiv 3\bmod{4}$ entonces si hay una solución, $p|a^2+b^2$. Entonces si esprimo relativo con alguno lo es con ambos entonces daria que $p|(\frac{a}{b})^2+1$ que es una contradicción. Asi que inductivamente hay $x,y$ tal que $x^2+y^2=p$. Pero esto es una contradicción. Entonces no hay puntos.

Si $p\equiv 3\bmod{4}$ por formulazo tenemos que hay $4\cdot 2012 =8048$ soluciones/puntos. Esto esta dada por la formula $r(n)$ en general donde es igual a $0$ si tiene algún factor primo 3 modulo 4 tal que su exponente es impar y si no es $0$ entonces $r(n)=\prod _{p\in\mathbb{P},p\equiv 1\bmod{4}} (v_p(n)+1)$ donde $v_p(n)$ es el exponente de $p$ en $n$.

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Primero notemos que si un punto $\left(x, y\right)$ está sobre dicha circunferencia, entonces por Pitágoras cumplirá que $x^{2}+y^{2}=p^{4022}$. También se puede ver que para cada $p$ habrán al menos $4$ puntos que cumplen, que son las intersecciones de los ejes del plano con la circunferencia, así que no contaremos esas por el momento. Además, si $\left(X, Y\right)$ cumple, también cumplen $\left(\pm X, \pm Y\right)$. Entonces asumiremos por el momento que los puntos tienen coordenadas enteras positivas. Dividiremos pues en casos.

Si $p=2$, entonces tendremos que $2^{4022}=x^{2}+y^{2}$. Sea $d=\gcd{\left(x, y\right)}$. Entonces tenemos que $x=da$ y $y=db$ Así $x^{2}+y^{2}=d^{2}\cdot \left(a^{2}+b^{2}\right)$ y $d^{2}\left(a^{2}+b^{2}\right)=2^{4022}$. Entonces, con esto vemos que $d=2^{k}$. Entonces queremos que $a^{2}+b^{2}=2^{2\left(2011-k\right)}$, notemos que si $k<2011$, entonces tenemos que $a^{2}+b^{2}$ es divisible por $4$, y como $x^{2} \equiv 0, 1 \pmod{4}$, tenemos que $2$ divide a $a$ y $b$, pero eso es una contradicción, pues $\gcd{\left(a, b\right)}=1$. Entonces $k=2011$, y eso es una contradicción, pues $d^{2}\left(a^{2}+b^{2}\right)>2^{4022}$, pues $a+b>1$. Entonces no hay solución con $x, y \in \mathbb{Z}^{+}$.

(No creo que quepa, así que continúa en el siguiente comentario.)

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Si $p=4k-1$, entonces usando el símbolo de Legendre vemos que si $p$ divide a $x^{2}+y^{2}$, entonces $p$ divide a $x, y$. entonces, de nuevo sea $d=\gcd{\left(x, y\right)}$ y $x=da, y=db$. Entonces $d=p^{k}$ y tenemos que $a^{2}+b^{2}=p^{2\cdot \left(2011-k\right)}$. Entonces, si $k<2011$, tenemos que $p$ divide a $a^{2}+b^{2}$, por lo que $p$ divide a $a, b$ y eso es una contradicción. Entonces con $k=2011$, tenemos que $x^{2}+y^{2}>p^{4022}$, lo cual es una contradicción. Entonces no hay soluciones en $x, y \in \mathbb{Z}^{+}$.

Adán dijo...

Nota, también si $\left(X, Y\right)$ cumple cumplen $\left(\pm Y, \pm X\right)$.

Flavio dijo...

Si, es $p^{2011}$, Diego, no está bien lo que hiciste, te confundiste en una parte.

Adán dijo...

Ahora, si $p=4k+1$, vamos a hacer lo siguiente. De la misma manera que antes definiremos $d, a, b, k$. Entonces queremos que $a^{2}+b^{2}=p^{2\cdot \left(2011-k\right)}$. Vamos a ver cuantas soluciones tiene $p^{2m}=a^{2}+b^{2}$ donde $\gcd{\left(a. b\right)}=1$. Sea $C_{m}$ esa cantidad. Entonces queremos encontrar $\sum_{i=1}^{2011}{C_{i}}$.

Unknown dijo...

Otra forma, más constructiva, de solucionarlo es con el anillo de los enteros gaussianos $\mathbb{Z}[i]$. El problema de encontrar cuantas parejas hay $(a,b)\in\mathbb{Z}^2$ tal que $a^2+b^2=n$ es el mismo que encontrar cuantos enteros gaussianos $z$ tienen norma $n$. Digamos que el numero es $r(n)$.

Es facil ver que $r(n)=r(2n)$ con la transformaciones $(a,b)\mapsto (a+b,a-b)$ y $(r,s)\mapsto (\frac{r+s}{2},\frac{r-s}{2})$, que nos llevan de una pareja de la primera a la segunda y viceversa. Como $r^2+s^2=2n$ entonces $r+s$ y $r-s$ son impares asi que la segunda sí es valida. Son transformaciones inversas asi que es una biyección y por lo tanto $r(n)=r(2n)$. Asi que reducimos el problema a $n$ impar.

Sabemos que $r(n)=0$ si y solo si tiene un $p$ que deja residuo $3$ modulo $4$ que lo divide con exponente impar, osea $2\nmid v_(p)$ para $p\equiv 3\bmod{4}$. Si $p|n$ y $r(n)>0$ entonces si tenemos una solución $(a,b)$ es facil ver que $p|a,b$ ya que divide a uno si y solo si divide al otro si no fuera asi entonces $p\mid (\frac{a}{b})^2+1$ lo cual es imposible. Asi que $p|a,b$ entonces $p^2|a^2,b^2$ entonces $p^2\mid n$ y por la biyección $(a,b)\mapsto (\frac{a}{p},\frac{b}{p})$ nos da que $f(n)=f(\frac{n}{p^2})$. Asi que podemos suponer que los unicos factores primos de $n$ son $1$ modulo $4$.

Es conocido que cada $p\equiv 1\bmod{4}$ tiene una solución $(x,y)$, salvo permutaciones y signos,a $x^2+y^2=p$. Como $2\nmid p$ tenemos que $x\neq y$ asi que $r=x+yi\neq y+xi=s$. Es facil ver que las $8$ soluciones (contando permutaciones y signos) se pueden expresar como $r,ri,ri^2,ri^3,s,si,si^2,si^3$.

Sean $r_p,s_p$ (las) dos soluciones diferentes con $Re(r_p)=Im(s_p)>0$, $Re(s_p)=Im(r_p)>0$ y $N(r_p)=N(s_p)=p$. Es conocido que $r_p$ y $s_p$ son primos gaussianos, y $\mathbb{Z}[i]$ es un anillo de factorización única, salvo unidades.

Sean $a_p$ tal que $0\leq a_p\leq v_p(n)$ para todo $p\in\mathbb{P}$ (notemos que si $p=2$ o $p\equiv 1\bmod{4}$ entonces $v_p(n)=0$). Entonces consideremos $z=i^t\prod_{p\in\mathbb{P}} r_p^{a_p} s_p^{v_p(n)-a_p}$.

Es facil ver que $N(z)=\prod_{p\in\mathbb{P}} N(r_p)^{a_p} N(s_p)^{v_p(n)-a_p}=\prod_{p\in\mathbb{P}} p^{a_p} p^{v_p(n)-a_p}$ entonces $N(z)=\prod_{p\in\mathbb{P}} p^{v_p(n)}=n$. Asi que $z$ cumple.

Cada elección de $t$ en $0,1,2,3$ y $a_i$ en $0,\cdots,v_p(n)$ nos da un numero diferente, dado que $\mathbb{Z}[i]$ tiene factorización unica.

Para $z=z_0$ tal que cumpla $N(z)=n$ entonces $N(z)=\prod{p\in\mathbb{P}}p^{v_p(n)}$. Si $v_p(n)\geq 1$ entonces lo debe dividir ya sea $s_p$ o $r_p$, que son los primos $t$ que cumplen $N(t)=p$. Y luego considerariamos $N(z_1)=N(\frac{z}{t})=\frac{n}{p}$, con $t=s_p$ o $r_p$. Podemos ir factorizando asi a $z_i$ hasta que nos quede $N(z_u)=1$ entonces $z_u=i^t$ para algun $t$ en $\left{0,1,2,3\right}$ y revirtiendo los pasos nos quedaria que $z$ lo dividen $s_p$ o $r_p$ si y solo si $p|n$ y la suma de las potencias en que $s_p$ y $r_p$ dividen a $z$ seria igual a la de $p$ con $n$, $v_p(n)$. Asi que $z$ es de la forma $i^t\prod_{p\in\mathbb{P}} r_p^{a_p}s_p^{v_p(n)-a_p}$ para algunas $a_p$ que cumplan $0\leq a_p\leq v_p(n)$.

Asi que hay tantos $z\in\mathbb{Z}[i]$ que cumplen $N(z)=n$, con $n$ producto de primos que son $1$ modulo $4$, como numeros de la forma $i^t\prod_{p\in\mathbb{P}} r_p^{a_p}s_p^{v_p(n)-a_p}$, con $0\leq t\leq 4$ y $0\leq a_p\leq v_p(n)$. Hay en total $4\cdot\prod_{p\in\mathbb{P}}(v_{p}(n)+1)$
de estos.
En general, entonces si $r(n)>0$ tenemos que $r(n)=4\cdot\prod_{\substack{p\in\mathbb{P}\\ p\equiv 1\mod 4}}(v_{p}(n)+1)$ y $r(n)=0$ para los $n$ con algún primo $p$ que los divida con un exponente impar y cumpla $4|p-3$.

Entonces las respuestas serian $4,0$ y $4\cdot 2012=8048$ para $p=2,p\equiv 1\bmod{4}$ y $p\equiv 3\bmod{4}$ respectivamente.

Unknown dijo...

Donde esta la caja roja era $t$ en $0,1,2,3$

Unknown dijo...

En el penultimo parrafo también es $0\leq t\leq 3$.

Unknown dijo...

Oh, ya vi el error que dices, es $N(z)=p^{4022}$. Bueno, igual, en este caso salen $4,0$ y $4\cdot 4023=1696$ para los casos $p=2,p\equiv 3$ y $p\equiv 1\bmod{4}$.

Juan dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...

Calcularé el número de soluciones a la siguiente ecuación:
$a^2+b^2=p^n$,
con p primo, n natural, a y b enteros, con $p | ab$ falso. (la respuesta al problema se dará con n=4022).
Bueno, hay tres casos esencialmente:
CASO I: p=2
Se debe cumplir $a=1=b=n$, a menos de que $n>1$, lo que implica $4|a^2+b^2$. En éste caso, podemos dividir a a y b entre 2 (los residuos cuadráticos modulo 4 son 1 y 0), y restarle 2 a n. Podemos continuar este proceso hasta que n=1 o 2 (dependiendo de la paridad de n). Así, lo que hicimos es identificar soluciones (a, b) de la ecuación (con n fija), con soluciones de la ecuación con n=1 o 2.Para n=1, hay 4 soluciones de (a, b) : (+-1, +-1), por lo que si p=2, hay 4 soluciones (a, b) de la ecuación original si n es impar. Si n es par, podemos aplicar el razonamiento de arriba otra vez aunque esta vez terminaremos en $n=0$. Aquí, hay 4 soluciones, otra vez: (0, +-1) = (a, b). Así, si n es par, también hay 4 soluciones, la respuesta a este caso.
CASO II: 4|p+1.
En este caso tenemos que -1 no es residuo cuadrático módulo p. Así, si la ecuación se da, a menos de que b=0, tendremos $p|(ab^{-1})^2+1$, donde $b^{-1}$ es el inverso multiplicativo de b mod p. Pero ésto implica que -1 es residuo cuadrático modulo p, y habíamos quedado con que ésto no era cierto. Así, $p|a$, y asi $p|b$. Por tanto, $p^2|a^2+b^2=p^n \Rightarrow n \geq 2$. Por ésto, podemos restarle 2 a n y obtener otra ecuación similar, como lo hicimos en el primer caso. Así, al final acabaremos con lo siguiente n=2. Podemos aplicar otra vez el razonamiento, pero ahora n=0, y no será natural, por lo que ya no podremos aplicar el razonamiento. Pero si n=0, tenemos que {a,b} = {0, +-1}, y habrá 4 soluciones en éste caso, independientemente de la n (con que sea par). Si n es impar, terminamos con $a^2+b^2=p \Rightarrow$ $p|a$, $p|b$ $\Rightarrow$ $p^2|p$. Contradicción. Asi, aqui la respuesta es 4 si n es par y 0 si n es impar.
CASO III: $4|p-1$

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Si $p^{2m}=a^{2}+b^{2}$, entonces $\left(p^{m}-b\right)\left(p^{m}+b\right)=a^{2}$. Como $p=4k+1$, tenemos que $a^{2}+b^{2} \equiv 1 \pmod{4}$, por lo que sin pérdida de la generalidad, podemos asumir que $a=2A+1$ y $b=2B$, para algunos $A, B \in \mathbb{Z}^{+}$. Entonces, si $q$ es un primo que divide a $a$, entonces si $q$ divide a $p^{m}+b$ y $p^{m}-b$, tenemos que $q$ divide a $2b$, pero como $q\neq 2$, tenemos que $q$ divide a $b$ lo cual es una contradicción. Como $q$ debe dividir a $p^{m}-b$ ó $p^{m}+b$, tenemos que estos $2$ últimos son primos relativos, y por lo tanto cuadrados, pues la máxima potencia de $q$ que divide a $q$ es par, digamos $2z$, y por lo tanto, tenemos que $q^{2z}$ divide a uno de los $2$ factores anteriores.

Juan dijo...

Bueno pues si n es par, por la fórmula pitagórica tendremos $a^2+b^2=p^{n/2}$ para algunos a y b. Así, podemos seguir dividiendo entre 2 hasta que n sea impar. Ahora es conocido que éstos primos pueden ser escritos como suma de cuadrados de exactamente una forma. Ahora, si n=2m-1, demostraré que hay $m$ soluciones a la ecuación (positivas). Esto es cierto si m=1, por lo recién dicho.

alberto dijo...

Queremos $a^2+b^2=p^{4022}$ por Pitagoras, podemos suponer que $a,b \textgreater 0$, y tambien seran soluciones $(\pm a, \pm b)$, y aparte consideramos cuando alguna de las dos coordenadas es 0, que en estos casos para todos los p hay 4 soluciones, que son las intersecciones del circulo con los ejes.

a) $p=2$
$a^2+b^2=2^{4022}$
Entonces 4 divide a lo de la izquierda, y por congruencias $a \equiv b \equiv 0 \pmod{2}$.
Entonces dividimos entre dos a y b y tenemos:
$a_1^2+b_1^2=2^{4020}$
Repetimos esto hasta llegar a:
$a_{2010}^2+b_{2010}^2=2^2=4$
Y no existen soluciones para esta ecuacion si ninguno de los dos es 0, por lo tanto la original no tiene solucion, y para este caso la respuesta es 4.

b) $p \equiv 3 \pmod{4}$
$a^2+b^2=p^{4022}$
Supongamos que esta es una terna pitagora primitiva, entonces existen $a_1,b_1$ tal que $a_1^2+b_1^2=p^{2011}$, pero si vemos las congruencias modulo 4, lo de la derecha es congruente a 3, y lo de la izquierda no puede ser congruente a tres, contradiccion, entonces no es primitiva.
$(a,b,p^{2011})=p^z$
Entonces tenemos que:
$a_1^2+b_1^2=p^{2(2011-z)}$
y esta si va a ser una terna primitiva, entonces van a existir $a_2,b_2$ tal que:
$a_2^2+b_2^2=p^{2011-z}$
Si 2011-z es impar, eso no va a tener solucion por que es congruente a 3 modulo 4, entonces es par, entonces es otra terna pitagorica, y como por definicion $(a_2,b_2)=1$, entonces es primitiva, y tenemos que:
$a_3^2+b_3^2=p^{\frac{2011-z}{2}}$
Si repetimos lo que hicimos para pasar de $(a_2,b_2)$ a $(a_3,b_3)$ llegara un momento en el que le quitemos todas las potencias dos que tenia 2011-z, entonces nos va a quedar un impar:
$a_r^2+b_r^2=p^{2k+1}$ pero ya vimos que esto no tiene solucion, entonces el original no tenia solucion.
Y la respuesta en este caso tambien es 4.

c) $p \equiv 1 \pmod{4}$
cuando tenga este caso hecho lo pongo =P

Unknown dijo...
Este comentario ha sido eliminado por el autor.
Unknown dijo...
Este comentario ha sido eliminado por el autor.
Unknown dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...

Continuando mi demostración, demostraré que para cada n=2m+1, existe exactamente una pareja de naturales primos relativos a y b con a^2+b^2=p^n, con lo cual habré acabado. Demostraré el siguiente lema:
LEMA: Si n y a son naturales primos relativos, existen 1 $\le$ x,y $\le$ (raiz de n) con xa=((-1)^z)y (mod n), para algun entero z.
DEMOSTRACION: Si consideramos todos los valores de xa-y, (considerando u=piso de raiz de n), seran (u+1)^2 $ge$ n, por lo que existen dos de esos valores con el mismo residuo modulo n, digamos x1a-y1 y x2a-y2. entonces tomamos x=x1-x2 y y =|y1-y2| y acabamos (suponiendo sin perdida de generalidad x1 mayor que x2).
FIN DEL LEMA.
Ahora porque 4|p-1, existe k con p^n|k^2+1, así, aplicamos el lema y encontramos enteros x y y menores a la raiz de p^n (menor estricto pues n es impar) y tendremos que p^n|k^2x^2-y^2. Esto implica p^n|x^2+y^2, pero por las desigualdades, se dará la igualdad p^n = x^2 + y^2. QED

Unknown dijo...

Primero consideraremos las soluciones con x,y positivos, y al final sólo consideraré las parejas $\ (\pm x, \pm y)$ pues también estarán sobre la circunferencia si $\ ( x, y)$ lo está. Además de sumar los 4 puntos cuando una coordenada es 0 y la otra es $\ p^2011 $.

Lo primero es notar que por teorema de Pitagóricas,, la condición necesaria y suficiente para que estén sobre la circunferencia es que:

$$\ x^2+y^2=p^{4022} $$

Examinemos el caso si $\ p=2$:

Digamos que $\(x,y)=d$, entonces de suma potencia de 2 pues debe dividir a $\ 2^{4022}$, digamos $\ d=2^m $.
Si dividimos la ecuación entre 2 un total de 2m veces llegamos a que el problema equivale a encontrar las soluciones a:
$$\ a^2+b^2=2^{4022-2m} $$
con a y b primos relativos

El exponente del 2 claramente es par, si este fuera positivo tendríamos que $\4|x^2+y^2$
pero los restos cuadráticos de 4 únicamente son 1 y 0 por lo que la única forma sería que 2 dividiera ambos números, pero dijimos que eran primos relativos, por lo que no es posible. De esto que veamos que el exponente es 0, entonces nuestra se vuelve:
$$\ a^2+b^2=1 $$ que no tiene solución en los enteros positivos.

Entonces cuando $\ p=2$ solo habrá 4 puntos.

Unknown dijo...

Con d me refiero al mcd de x,y y en el primer párrafo es p elevado a la 2011... Aprendiendo Latex...

Unknown dijo...
Este comentario ha sido eliminado por el autor.
Unknown dijo...

Veamos ahora que sucede si p diferente de 2.

Nuevamente digamos que el mcd de x, y es d, este tendría que dividir a p, por lo que es una potencia de p digamos $\ d=p^m $.

De igual manera que en el caso anterior hacemos la división por p un total de 2m veces y nos queda

$$\ a^2+b^2= p^{4022-2m} $$
con a y b primos relativos, entonces si $/ 4022-2m=0 $ tenemos el mismo caso que el anterior (no hay solución para reales positivos), y si $\ 4022-2m \textgreater 0 $ tenemos que $\ p|a^2+b^2 $ pero como a y b son primos relativos:

$$\ 1=(\frac{-b^2}{p})=(\frac{-1}{p})$$

que solo sucede si $\ p \equiv 1 \pmod{4} $

Unknown dijo...

Hasta aquí ya vi que con 3 y 2011 habrá solo las 4 soluciones que están sobre los ejes... Aun no termino la prueba si $\ p=4k+1 $ se las entrego después que me salga.

Adán dijo...

Bueno, ya para concluir, es conocido que si $n \in \mathbb{Z}^{+}$, y escribimos a $n$ como $n=2^{a}\cdot \left(p_{1}^{P_{1}}p_{2}^{P_{2}}\ldots p_{s}^{P_{s}}\right)\cdot \left(q_{1}^{Q_{1}}q_{2}^{Q_{2}}\ldots q_{s}^{Q_{s}}\right)$, donde $p_{i}$ es un factor primo de la forma $4k+1$ y $q$ de la forma $4k-1$, tenemos que la cantidad de tri\'angulos con hipotenusa $n$ de lados enteros positivos es $\frac{\left(2P_{1}+1\right)\left(2P_{2}+1\right)\ldots \left(2P_{s}+1\right)-1}{2}$. Como queremos $p^{2011}$ y $p=4k+1$, entonces la cantidad que buscamos es $\frac{2\cdot 2011+1-1}{2}=2011$, pero eso es para enteros positivos. Además, si $p^{4022}=a^{2}+a^{2}$, tendríamos que $p$ divide a $2$, lo cual no es el caso. Entonces, todos los casos resultan con lados de diferente longitud, por lo que tenemos $8\cdot2011=16088$ triángulos.

Adán dijo...

Entonces, si $p=2$, hay $4$ vértices sobre la circunferencia; si $p=4k-1$, también hay solo $4$ vértices sobre la circunferencia; y si $p=4k+1$ entonces hay $16088+4=16092$ vértices sobre la circunferencia. Esto implica que para $p=3, 2011$ solo hay $4$ vértices de los buscados en la circunferencia.

Unknown dijo...

Corrección, las soluciones para $p=2$, $p\equiv 3 \bmod{4}$ y $p\equiv 1\bmod{4}$ son $4,4$ y $4\cdot 4023=16092$ puntos respectivamente.

Juan dijo...

Para concluir, si p no es 1 modulo 4, entonces hay 4 soluciones. Si sí lo es, entonces llamémosle $x_n$ al número de soluciones $a^2+b^2=p^n$ con (a,b)=1 y a y b naturales. Entonces por lo que dije anteriormente $x_{2n}=0$ siempre. Ahora, quiero encontrar $x_0+x_1+x_2+...+x_{4022}+1$, y luego multiplicarlo por 4, y ésta será la respuesta. Así, nada más analizo los casos $x_{2m-1}$. Por lo dicho anteriormente, si $a^2+b^2=p^{2m-1}$, si y sólo si $an= \pm b$ (mod $p^{2m+1})$ y $ 1 \le a,b \le p^{m+(1/2)}$. Entonces hemos reducido el problema a encontrar el número de parejas que cumplen ésto, y también que (a,b)=1.

Juan dijo...

(donde n es un numero tal que $p^{2m+1} \mid n^2+1$).

Unknown dijo...
Este comentario ha sido eliminado por el autor.
Unknown dijo...

Para concluir demostraré que una potencia impar de un primo puede ser escrita de manera única como suma de cuadrados primos relativos.

Para esto demostraré el siguiente lema:
Si tenemos $\ m \textgreater 1 $ y $\ (x,y)=1 $ con x,y positivos; el número de formas de escribir
$$\ m=x^2+y^2 $$ (1)
es igual al número de soluciones de la congruencia
$$\ z^2 +1 \equiv 0 \pmod{m} $$ (2)

Prueba:
Si x, y son números que cumplan (1), tenemos que si tomamos la congruencia
$$\ x \equiv zy \pmod{m} $$ (3)
,cada solución $\ z \equiv z_0 \pmod{m} $ (4) cumplirá también con la congruencia (2)

Entonces diremos que la expresión (1) está ligada con la solución (4) de la congruencia (2).

Ahora probaremos que cada solución (4) de la congruencia (2) está ligada a no menos de una expresión (1):
Considerando la sucesión de Farey correspondiente a m y por una propiedad conocida, podemos escribir:

$$\ \frac{z_0}{m}= \frac{P}{Q} + \frac{\theta}{Q\sqrt{m}} $$
con $\ (P,Q)=1 $ Q positivo menos o igual a la raíz cuadrada de m y con $\ |\theta| \textless 1 $

Entonces $\ z_0 Q=mP+r $ donde $\ |r| \textless \sqrt{m} $
Después, a partir de (2) llegamos a que $\ |r|^2 + Q^2 \equiv 0 \pmod{m} $ .

Unknown dijo...
Este comentario ha sido eliminado por el autor.
Unknown dijo...

De la última congruencia y de que $\ 0 \textless |r|^2+Q^2 \textless 2m $, se obtiene lo siguiente

$$\ m= |r|^2 + Q^2 $$ (5)

Ahora veremos que r y Q son primos relativos:
$$\ 1= \frac{r^2+Q^2}{m} = \frac{(z_0 Q-mP)z_0 Q - rmP +Q^2}{m} \equiv -rP \pmod{Q} $$.

Si |r|=r, $\ r \equiv z_0Q \pmod{m} $, la expresión (5) está ligada con la solución (4). Si |r|= -r, como $\ z_0^2Q \equiv z_0r \pmod{m} $ , $\ Q \equiv z_0|r| \pmod{m} $, la expresión (5) esta ligada a (4).

Al final, con cada solución (4) está ligada no más de una expresión (1), pues si dos expresiones del número m de la forma (1),
$\ m = x^2 + y^2 $ y $\ m= x_1^2 + y_1^2 $ están ligadas con una solución de (4), entonces de $\ x \equiv z_0y \pmod{m}$ y $\ x_1 \equiv z_0y_1 \pmod{m}$ se deduce que $\ xy_1 \equiv x_1y \pmod{m} $. Por lo tanto $\ xy_1=x_1y $ y como cada pareja son primos relativos, teneos que $\ x_1=x $ y $\ y_1 = y$ lo que concluyer la demostración del lema...

Unknown dijo...
Este comentario ha sido eliminado por el autor.
Unknown dijo...

Volviendo al problema, por una teorema conocido, si definimos $\ f(z)= z^2+1 $ y vemos que $\ f'(z)= 2z $, entonces por un lema conocido la congruencia $\ f(z) \equiv 0 \pmod{p^{2m-1}} $ tendrá tantas soluciones como las tenga $\ f(z) \equiv 0 \pmod{p}} $ que son 2...

Entonces de aquí podemos ver lo que quería probar, en el caso de que queramos escribir la potencia como una suma de dos cuadrados en general, podemos ver que cuando x, y no son primos relativos, podemos factorizar un p al cuadrado, lo que nos deja con la potencia impar anterior, con lo que solo tenemos que ir tomando la potencia impar anterior, y con una inducción sencilla tenemos que $\ p^{2m-1}} $ puede ser escrito exactamente de 2m maneras como suma de cuadrados (considerando que un primo puede escribirse de dos maneras como suma de cuadrados al cambiar de lugar los números).

Unknown dijo...

Volviendo al ultimo caso, queremos ver como puedo escribir $\ p^{4022} = x^2+y^2 $, entonces por ternas pitagóricas, las soluciones se pueden obtener con $\ p^{2011}=u^2+v^2 $ y cada una de estas u,v da dos soluciones en positivos, pero por lo que demostré arriba esto tendrá exactamente 2012 soluciones, por dos, habrá 4024, por los 4 cuadrantes del plano más los que están sobre los eje da un total de 16100 puntos si el primo es de la forma 4k+1 y un total de 4 en caso contrario.
Tal vez me equivoque en alguna cuenta, peor la idea ya está. En el comentario anterior quise poner que como la derivada de la función es 2z y z debe ser primo relativo con p por las condiciones del problema, tenemos que la derivada de la función y p son primos relativos, lo que implica lo que puse ahí.

Juan dijo...

Ahora, supongamos que hay dos soluciones (sabemos que hay al menos una por el lema) esencialmente diferentes de $an= \pm b$ (mod $p^k)$: $(a_1,b_1)$ y $(a_2,b_2)$. Fácilmente se ve que $a_1/b_1 = -a_2/b_2$ (mod $p^k$), por lo que $p^k \mid (a_1b_2 + b_1a_2)$. (NOTA: las fracciones están definidas porque p no divide a ninguno de los 4 números). Pero por las desigualdades con las raices de $p^k$ se ve fácilmente que $p^k=a_1b_2+b_1a_2=a_1a_1 + a2_a_2$. por lo que:
$a_1(b_2-a_1) = a_2(b_1-a_2)$ (mod $p^k$). Pero como las diferencias de números menores a $p^{m{(1/2)}$ son también menores a ese número, tenemos que los números de la anterior congruencia son menores a $p^k$, por lo que los números son iguales, de lo que se obtiene que las soluciones son esencialmente iguales con álgebra. ¡Contradicción! Por lo tanto hay exactamente una solución para la ecuación, y como (a,b) y (b,a) también valen, tendremos que $x_k$ = 2, por lo que la respuesta será 16092 si 4$\mid$p-1, y 4 si 4 no divide a p-1. Quod erat demonstrandum. $\clubsuit$.

Juan dijo...

donde dice $a2_{a2}$ debería decir $a_{2}a_{2}$.

alberto dijo...

No supe como demostrar para $p=4k+1$ de otra forma asi que usare la formula que esta en wolfram.

$s=2^{a_0}(p_1^{a_1} \cdots p_n^{a_n})(q_1^{b_1} \cdots q_r^{b_r})$

Donde $p_i$ son los primos de la forma $4k-1$ y $q_i$ son de la forma $4k+1$. La formula para la cantidad de ternas pitagoricas primitivas y no primitivas con hipotenusa $s$ es:

$H(s)=\frac{1}{2}[(2b_1+1)(2b_2+1) \cdots (2b_r+1)-1]$

Estas son las ternas con ambos positivos, entonces multiplicamos por 4 por los cuatro cuadrantes, y por 2 porque esta formula cuenta $(x,y)$ y $(y,x)$ como la misma terna, cuando te da dos puntos distintos en el plano, excepto si $x=y$, que da $2x^2=p^{4022}$, pero esto no tiene soluciones cuando $p=4k+1$, entonces hay que multiplicar por 8.

Entonces el total que buscamos va a ser $T(p^2011)=4+8H(p^{2011})$

$H(p^{2011})=\frac{[2(2011)+1]-1}{2}=2011$

$\Rightarrow T(p^2011)=4+8H(p^{2011}) = 4+8\times 2011=16092$

Marco dijo...

Buscaremos las soluciones enteras de $x^2+y^2=p^{4022}$ .Para el caso ${2^2011}$ ,sea k la mayor potencia de k que divide tanto a x como a y. Entonces, escribiendo $x=2^{k}m$ y $y=2^{k}n$, tenemos $2^{2k}m^2+2^{2k}n^2=2^4022$. Si 2k es menor estricto que 4022, entonces $m^2+n^2$ tendría que ser divisible entre 4, lo cual es una contradicción a la definición de k, porque m,n tendrían que ser ambos pares (checando módulo 4) entonces k=2011, pero entonces nos queda $m^2+n^2=1, lo cual no es posible porque la parte izquierda es mayor estricto a la derecha, ya que m,n son enteros positivos.

Marco dijo...

(una disculpa por la fallas de escritura..) lo anterior suponiendo que x,y son distintos de 0... entonces las únicas soluciones son las cuatro triviales en las que alguno de x,y es 0

Marco dijo...

Ahora vayamos directo a la generalización para p, suponiendo primero que p es de la forma 4k+3.Como $x^2+y^2$ debe ser múltiplo de p, como ambos términos son claramente residuos cuadráticos módulo p, la congruencia implica que $-x^2$ debe ser residuo cuadrático módulo p. Luego, como el símbolo de Legendre de $-x^2$ es igual al de $x^2$ por el de -1 y el de el primero es 1, entonces necesitamos que -1 sea residuo cuadrático, pero es conocido que para p de la forma 4k+3 esto no es posible. Entonces tanto x como y deben ser múltiplos de p. Sustituyendo 2 por p en la solución del caso particular anterior obtenemos una solución análoga, de manera que de nuevo las únicas 4 soluciones se dan cuando alguno de x,y es 0

Marco dijo...

el caso p=4k+1 tampoco supe como hacerlo, y ya chequé como está lo de la fórmula de wolfram de Adán, pero supongo que no tiene caso que lo reescriba

Enrique dijo...

Vemos que sacar el número de puntos con coordenadas enteras sobre la circunferencia de radio $p^{2011}$ es lo mismo que sacar el número de soluciones enteras $(x,y)$ a $x^{2}+y^{2}=p^{2011(2)}$
Si $p=2$, por ternas pitagóricas tenemos que sin pérdida de generalidad $x=t(u^{2}-v^{2})$,$y=2tuv$, $2^{2011}=t(u^{2}+v^{2})$ con $(u,v)=1$. Entonces, $t=2^{k}$ y $u^{2}+v^{2}=2^{2011-k}$ para algún entero no negativo $k$ menor o igual que $2011$. Si alguno de $u,v$ es $0$, obtenemos soluciones. Si $u^{2},v^{2}>0$, $u^{2}+v^{2}>1$, luego $u^{2}+v^{2}$ es par, y como no pueden ser ambos pares, ambos son impares, lo cual implica que $u^{2}+v^{2}\equiv 2\pmod{4}$, luego $u^{2}+v^{2}=2\Rightarrow u=\pm 1, v=\pm 1$. Es fácil ver que 2 distintas soluciones se generan cuando $u,v$ tienen el mismo signo y cuando lo tienen distinto. Entonces, hay 4 soluciones para este caso.
Si $p\equiv 3\pmod{4}$, es un hecho conocido que $p\nmid a^{2}+b^{2}$ para cualesquiera enteros positivos primos relativos $(a,b)$. Entonces, es evidente que $(p^{2011},0),(-p^{2011},0),(0,p^{2011}),(0,-p^{2011})$ son posibles soluciones $(x,y)$. Supongamos ahora que $x,y\neq 0$. Entonces, por ternas pitagóricas $x=t(u^{2}-v^{2})$,$y=2tuv$, $p^{2011}=t(u^{2}+v^{2})$ con $(u,v)=1$, de donde $p=2^{k}$ y $u^{2}+v^{2}=p^{2011-k}$ para algún entero no negativo $k$ menor o igual que $2011$. Sin embargo, la última ecuación implica que $p\mid u^{2}+v^{2}$ o $p^{2011-k}=1$. Como la primera no es posible, $u^{2}+v^{2}=1$, de donde uno de ellos es $0$, pero esto es imposible pues de este modo $y=0$. Entonces, tenemos 4 soluciones en este caso, que incluye $p=3$ y $p=2011$.
Para el caso donde $p\equiv 1\pmod{4}$ tuve que revisar la fórmula que ya pusieron en soluciones anteriores, me dio el mismo resultado.

JulioC dijo...

Mis soluciones para el caso p=2 y p= 4k + 3, son basicamente ver que las soluciones satisfacen $x^{2}+y^{2}=p^{4022}$ y que si x,y alguno son 0 entonces son las 4 soluciones triviales en ambos casos. Ahora supongo que hay una solucion con x,y no cero, y elimino los factores comunes con p que deben ser p a una potencia par pues x y y estan al cuadrado, entonces la ecuacion nos queda:$x^{2}+y^{2}=p^{2k}$ con x,y primos relativos con p. En el caso p=2 me fijo q x^{2}, y^{2}son congruentes con 1 modulo 4 por ser primos relativos con 4, entonces $x^{2}+y^{2}=4k+2$. Lo cual no puede ser porq p^{2k} es multiplo de 4. Y para p= 4k + 3, veo que por la formula de gauss x y -x no pueden ser residuos cuadraticos modulo p al mismo tiempo entonces no hay solucion x,y. Por lo tanto el numero de puntos con coordenadas enteras están sobre la circunferencia para p= 2 y p= 4k + 3 son 4

Anónimo dijo...

Queremos encontrar los valores de $x,y\in\mathbb{Z}$ tales que $\sqrt{x^{2}+y^{2}}=p^{2011}$, pues si $(x,y)$ funciona, también funcionan $(\pm x,\pm y)$.

Para empezar, funcionan $(p^{2011},0)$ y $(0,p^{2011})$ (y sus reflecciones sobre los ejes $x$ y $y$ (en total son $4$ puntos). Si $p^{\alpha}||x$, y $p^

{\beta}||y$, suponiendo que son distintos y que sin pérdida de generalidad $2011\texttgreater\alpha\textgreater\beta$, entonces si dividimos ambos lados

entre $p^ {\beta}$, vemos que un lado es múltiplo de $p$ y el otro no lo es, pues $p|\frac{x}{p^{\beta}}$ y $p$ no divide a $\frac{y}{p^{\beta}}$ así que no

se puede $\therefore\alpha=\beta$. Ahora, sean $p^{\alpha}\cdot a=x$ y $p^{\alpha}\cdot b=y$, por lo que $a^{2}\equiv -b^{2}\pmod{p^{4022-2\alpha}$ y $(a,p)

=(b,p)=1$, por lo que usando símbolo de Legendre $\left(\frac{a^{2}}{p}\right)=1=\left(\frac{-b^{2}}{p}\right)$ por lo que $1=(-1)^{\frac{p-1}{2}}$ así que

si $p$ es de la forma $4k+3$ no hay más soluciones (sólo las cuatro mencionadas al inicio), al igual que si $p=2$ (pues son impares y módulo $4$, ambos son

$1$ así que su suma no es múltiplo de ningún exponente de dos más que $2$, y dado que se debe dar la congruencia para $p^{4022-2\alpha}$ dónde el exponente

es par (y evidentemente mayor a $0$), entonces es mayor a $1$ y eso no es posible).

Si $p$ es de la forma $4k+1$ entonces esto sí es posible. Si existe un primo $q$ tal que $q|a,b$, entonces $q|p\Rightarrow q=p$ lo que es una contradicción,

pues ya les habíamos quitado todos los factores $p$ a $a$ y a $b$, por lo que no existe tal primo y $(a,b)=1$. Ahora, sea $z$ un natural menor que $p^{4022-

2\alpha}$, tal que $z^{2}\equiv -1\pmod{p^{4022-2\alpha}}$, (que por lo mismo, no es divisible por $p$, o $p|1$ que es imposible). Ahora, veremos que siempre

es posible encontrar naturales $A,B\leq p^{2011-\alpha}$ tales que $Az\equiv\pm B\pmod{p^{4022-2\alpha}}$, para ver esto, basta ver que hay $p^{4022-2

\alpha}$ congruencias posibles para $Az-B$ módulo $p^{4022-2\alpha}$, y $A,B$ tienen (cada uno) $\sqrt{p^{2011-\alpha}}$ valores cada uno, así que hay $p^

{4022-2\alpha}$ valores de $Az-B$ (no necesariamente distintos), así que o está en ellos el $0$, o hay dos que dan la misma congruencia, digamos $A_{1},B_

{1}$ y $A_{2},B_{2}$ con $A_{1}>A_{2}$, así que tomamos a $A=A_{1}-A_{2}$ y $B=|B_{1}-B_{2}|$ y estos funcionan, de donde vemos que $A^{2}z^{2}\equiv B^{2}

\pmod{p^{4022-2\alpha}}$, por lo que $p^{4022-2\alpha}|A^{2}+B^{2}$, pero como cada uno de $A,B$ son menores o iguales a $p^{2011-\alpha}$, pero , lo más que

pueden sumar es $2p^{4022-2\alpha}$, sin embargo ese caso se da cuando ambos son el valor más alto, en cuyo caso, $z\equiv 1\pmod{p}$, por la congruencia que

cumplen $Az$ y $B$, sin embargo, $z^{2}\equiv 1\pmod{p}$ lo que es una contradicción a la definición de $z$, así que la suma es menor y por lo tanto $p^

{4022-2\alpha}\leq A^{2}+B^{2}\textless 2p^{4022-2\alpha}$ lo que implica la igualdad $p^{4022-2\alpha}=A^{2}+B^{2}$ así que hay al menos una solución para

cada caso.

Anónimo dijo...

Primero, claramente si $a,b\leq \frac{p^{2011-\alpha}}{2}$, entonces el doble de cada uno funciona como solución y no son coprimos, lo que es una

contradicción, así que eso nunca se puede dar. Veamos que si existen dos naturales quee cumplen con las condiciones de $a$, digamos, $a_{1},a_{2}$, entonces

eso significa que $a_{1}z,a_{2}z\in\{-p^{2011-\alpha}+1,\dots,p^{2011-\alpha}-1\}$ si consideramos únicamente sus residuos, módulo $p^{4022-2\alpha}$. Esto

de inmediato implica que (suponiendo sin pérdida de generalidad que $a_{2} \textless a_{1}$) $(a_{1}\pm a_{2})z, a_{1}\pm a_{2}\in\{1,2,\dots,p^{2011-

\alpha}-1\}$, así que si con un signo entra en ese conjunto, lo podremos considerar como otra solución $a_{3}$. En caso que el menos se cumpliera (ambos

deben tener el mismo signo), implica que son del mismo signo los $az$, pero entonces ya sea $|a_{3}z|$ o $|a_{2}z|$ es menor a la mitad de la cota $p^{2011-

\alpha}$, así que es contradicción. En caso de la suma, implica algo similar, pues $a_{3}z$ comparte signo con alguno de los otros dos (pues son de signos

diferentes) y entonces la resta se cumple para este y alguno de los otros dos. En cualquier otro caso significa que $(a_{1}-a_{2})z$ se pasa de la cota al igual que $a_{1}+a_{2}$, implicando que si tampoco se puede para $(b_{1},a_{1})$ y $(a_{2},b_{2})$ dónde las soluciones que estábamos usando eran $(a_{1},b_{1})$ y $(a_{2},b_{2})$ ordenadamente, a pesar de que al cambiarlos se volteen los signos de uno (por ejemplo, $az\equiv b\pmod{p^{4022-2\alpha}}$ se voltea a $bz\equiv -a\pmod{p^{4022-2\alpha}}$ multiplicando por $z$), entonces significa que la resta no funciona a pesar de tener el mismo signo porque son la misma solución, y si funcionara, sería contradicción, así que solo hay una solución (evitando el duplicado de tomar a $(a,b)$ como si fuera distinto de $(b,a)$) y siempre hay solución, así que para cada posible $\alpha$ hay una solución no ordenada, y hay $2011$ valores de $\alpha$ y por lo mismo hay (ahora si ordenados) $4*2*2011+4=16092$. (el cuadro rojo debería decir $a^{2}\equiv -b^{2}\pmod{p^{4022-2\alpha}}$)

José A. dijo...
Este comentario ha sido eliminado por el autor.
José A. dijo...
Este comentario ha sido eliminado por el autor.
José A. dijo...

Mostraré solo la solución del caso 2 y 3.
Lo que queremos encontrar es cuántos números $(x,y)$ cumplen que $2^{4022}=x^{2}+y^{2}$ Lo primero que decimos es que como la forma de las ternas pitagóricas es conocida, esto es equivalente a encontrar números $(m,n)$ que cumplan $2^{2011}=m^{2}+n^{2}$
Ahora, podemos ver que $(m^{2},n^{2})\equiv 0,1\pmod{4}\$ por lo que $m^{2}+n^{2}\equiv 0,1,2\pmod{4}\$. Sabemos que como la suma es divisible entre $4$, entonces $m, n$ son ambos múltiplos de $2$ y por lo tanto se pueden reescribir como $m^{2}=4(m_{1})^{2}$ y $n=4(n_{1})^{2}$. Sustituyendo y dividiendo entre $2$ tenemos que
$2^{2009}=(m_{1})^{2}+(n_{1})^{2}$.
Podemos repetir este proceso hasta que
$2^{1}=2=(m_{k})^{2}+(n_{k})^{2}$ Para algún $k$.
Las únicas soluciones enteras de eso son $(\pm1,\pm1)$. Esto, además de los 4 puntos de contacto con los ejes. Por lo tanto con radio $2^{2011}$ la respuesta son $8$ puntos.

En cuanto al caso $3$ vemos qué:
Lo que queremos encontrar es cuántos números $(x,y)$ cumplen que $3^{4022}=x^{2}+y^{2}$ Lo primero que decimos es que como la forma de las ternas pitagóricas es conocida, esto es equivalente a encontrar números $(m,n)$ que cumplan $3^{2011}=m^{2}+n^{2}$
Ahora, podemos ver que $(m^{2},n^{2})\equiv 0,1\pmod{3}\$ por lo que $m^{2}+n^{2}\equiv 0,1,2\pmod{3}\$. Sabemos que como la suma es divisible entre 3, entonces $m,n$ son ambos múltiplos de 3 y por lo tanto se pueden reescribir como $m^{2}=9{m_{1}}^{2}$ y $n=9(n_{1})^{2}$. Sustituyendo y dividiendo entre $3$ tenemos que
$3^{2009}=(m_{1})^{2}+(n_{1})^{2}$.
Podemos repetir este proceso hasta que
$3^{1}=3=(m_{k})^{2}+(n_{k})^{2}$ Para algún $k$.
Esta ecuación no tiene solución en los enteros distintos de cero. Teniendo que considerar los puntos de contacto del círculo con los ejes, veremos que hay solo 4 puntos.

El caso general, no lo he solucionado aún. Solo sé que el caso del primo $p=4k+3$ es imposible, pues al hacer las sustituciones de las ternas pitagóricas, tenemos que la suma de dos cuadrados es congruente a $3\pmod{4}\$ lo cual como vimos, es imposible.

Anónimo dijo...

también en una parte dice "sin pérdida de generalidad $2011\alpha\textgreater \beta$" y debería ser $2011\textgreater \alpha\textgreater \beta$

Publicar un comentario