\documentclass[11pt,leqno]{article}
\usepackage{amssymb, amsmath} 
\usepackage{latexsym} 
\usepackage{graphics} 
\usepackage[hyphens]{url}
%\def\UrlBreaks{\do\/\do-}
\expandafter\def\expandafter\UrlBreaks\expandafter{\UrlBreaks% save the current one
  \do\a\do\b\do\c\do\d\do\e\do\f\do\g\do\h\do\i\do\j%
  \do\k\do\l\do\m\do\n\do\o\do\p\do\q\do\r\do\s\do\t%
  \do\u\do\v\do\w\do\x\do\y\do\z\do\A\do\B\do\C\do\D%
  \do\E\do\F\do\G\do\H\do\I\do\J\do\K\do\L\do\M\do\N%
  \do\O\do\P\do\Q\do\R\do\S\do\T\do\U\do\V\do\W\do\X%
  \do\Y\do\Z\do\*\do\-\do\~\do\'\do\"\do\-}%

\usepackage{xcolor}
\usepackage{hyperref} 


%\usepackage[notcite,notref,color]{showkeys}


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	SPANISH
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	FORMAT
%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setlength{\textheight}{23.0cm}
\setlength{\textwidth}{15.75cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	COUNTERS
%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcounter{ejeno}
\setcounter{ejeno}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	MACROS
%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\R}{{\mathbb R}} 
\newcommand{\C}{{\mathbb C}} 
\newcommand{\N}{{\mathbb N}} 
\newcommand{\Z}{{\mathbb Z}} 
\newcommand{\Q}{{\mathbb Q}} 


\newcommand{\ejer}{\ \par\vspace{-7pt}{\bf\number\value{ejeno})\ }\addtocounter{ejeno}{1}}


\usepackage{listings}


\lstdefinelanguage{Sage}[]{Python}
{morekeywords={False,sage,True},sensitive=true}

\lstset{
  frame=none,
  showtabs=False,
%  showtabs=True,
  showspaces=False,
  showstringspaces=False,
%  showstringspaces=True,
  commentstyle={\ttfamily\color{green!30!black}},
  keywordstyle={\ttfamily\color{blue!30!black}\bfseries},
  stringstyle={\ttfamily\color{gray!30!black}\bfseries},
%  language=Sage,
%  basicstyle={\fontsize{10pt}{10pt}\ttfamily},
  basicstyle=\footnotesize,
%  basicstyle={\fontsize{10pt}{10pt}\rmfamily},
  aboveskip=0.6em,
  belowskip=0.5em,
%  numbers=left,
%  numberstyle=\footnotesize
  xleftmargin=25pt
}

%\lstset{framexleftmargin=5mm, frame=shadowbox, rulesepcolor=\color{blue}}




\begin{document}
\pagestyle{myheadings}
\markboth{}{\rm\textsf{\jobname}\qquad\hfill}

El tema principal de esta hoja es una aplicación de las sumas de Gauss a la teoría de números para demostrar lo que se llama la \emph{ley de reciprocidad cuadrática} que es un sorprendente resultado sobre congruencias que conjeturó Euler y demostró Gauss de varias formas distintas.

Esta ley establece una relación entre la solubilidad de 
$x^2\equiv p\ (q)$
y la de 
$x^2\equiv q\ (p)$ 
cuando $p,q>2$ son primos distintos,
lo cual es muy chocante porque, en principio, las congruencias módulos coprimos no tienen absolutamente nada que ver. Aquí y en lo sucesivo empleo la notación reducida de congruencias escribiendo $(p)$ en lugar de $(\text{mód } p)$.

Para suscitar tu curiosidad  te propongo que hagas primero un análisis experimental, con ordenador, como el que pudo hacer Euler a mano (aunque, en realidad, procedió calculando otras cantidades).
Para cada par de primos distintos $p,q>2$ diremos que las ecuaciones
$x^2\equiv p\ (q)$
y 
$x^2\equiv q\ (p)$ 
son incoherentes si una tiene solución y la otra no. Por ejemplo, para $p=3$, $p=7$ lo son pues $x\equiv 3\ (7)$ no tiene solución, mientras que $x\equiv 7\ (3)$ sí tiene solución, concretamente $x\equiv 1\ (3)$.  
En caso contrario, diremos que son coherentes. Esto es lo que ocurre para $p=5$, $q=7$ pues ni $x\equiv 5\ (7)$ ni $x\equiv 7\ (5)$ tienen solución. En principio, uno esperaría que la coherencia o incoherencia tuviera un comportamiento ``aleatorio''. La sorpresa es que puede determinarse  fácilmente simplemente examinando cierta paridad. Más sorprendente aún es que no exista una prueba realmente sencilla de ello. 

\ejer
Escribe un programa que considere los primos $2<p<q<100$ y 
elabore una tabla asignando a cada par de primos~$C$ o~$I$ dependiendo de si 
$x^2\equiv p\ (q)$
y 
$x^2\equiv q\ (p)$ 
son coherentes o incoherentes. Cruza esa tabla con otra que indique si $(p-1)(q-1)/4$ es par o impar y extrae un patrón que te lleve a una conjetura. 
\medskip 

Si vas a incluir líneas de código en tu trabajo y no sabes cómo hacerlo, revisa cómo uso el paquete \texttt{listings} en la fuente \LaTeX{} de este documento para escribir el siguiente ejemplo en \texttt{sagemath} que muestra en pantalla todos los pares de primos admisibles en el ejercicio anterior.
\lstset{language=Sage}
\begin{lstlisting}
for p in prime_range(3,100):
    for q in prime_range(p+1,100):
        print(p,q)
\end{lstlisting}
\medskip


Para $n\in\Z$ y $p$ primo $p\nmid n$ se define el \emph{símbolo de Legendre} como
\[
 \Big(\frac np\Big)=
 \begin{cases}
  1&\text{si } x^2\equiv n\ (p)\ \ \text{tiene solución},
  \\
  -1&\text{si } x^2\equiv n\ (p)\ \ \text{no tiene solución}.
 \end{cases}
\]
Se 
completa la definición con $0$ si $p\mid n$, pero es indiferente para esta hoja. 

Los tres ejercicios siguientes extienden lo que sabíamos sobre la evaluación de las sumas de Gauss cuando el denominador es primo. El primero de ellos es sencillo. 


\ejer
Si $\big(\frac qp\big)=1$ con $p$ primo y $q\in\Z$, $p\nmid q$, explica por qué 
$G(q,p)=G(1,p)$.

\ejer
Si $\big(\frac qp\big)=-1$  con $p>2$ primo y $q\in\Z$, $p\nmid q$,  prueba que 
\[
 q(\pm 1)^2,\,
 q(\pm 2)^2,\,
 \dots,\,
 q\Big(\pm \frac{p-1}{2}\Big)^2,\, 
 0,\,
 (\pm 1)^2,\,
 (\pm 2)^2,\,
 \dots,\,
 \Big(\pm \frac{p-1}{2}\Big)^2 
\]
dan todas las clases módulo $p$ sin repeticiones cuando se fija uno de los dos signos. Deduce de ello 
$2\sum_{k=0}^{p-1} e(k/p)=G(q,p)+G(1,p)$. 
\textsf{Indicación:} Una vez probado que las clases son distintas, necesariamente son todas porque $\frac{p-1}{2}+1+\frac{p-1}{2}=p$. 

\ejer
Deduce la fórmula 
\begin{equation}\label{gleg}
 G(q,p)=\Big(\frac qp\Big)G(1,p)
 \qquad\text{para $p>2$ primo y $q\in\Z$, $p\nmid q$}.
\end{equation}
En realidad, se puede incluir el caso $p=2$ para el que el resultado es trivial.
\medskip 


Con todo esto, lo que sabemos sobre evaluar sumas de Gauss es suficiente para obtener el resultado deseado. 


\ejer
Con la propiedad multiplicativa del penúltimo ejercicio de la hoja anterior, la evaluación de $G(1,pq)$ y \eqref{gleg}, concluye la ley de reciprocidad cuadrática en la forma 
\begin{equation}\label{qrl}
 \Big(\frac pq\Big)
 \Big(\frac qp\Big)=
 (-1)^{(p-1)(q-1)/4}.
 \qquad\text{para $p,q>2$ primos distintos}.
\end{equation}

Se suele preferir este enunciado simétrico, aunque quizá sea más informativa la siguiente traducción:
$\big(\frac{p}{q}\big)$ es  $-\big(\frac{q}{p}\big)$ si $4\mid p+1$ y $4\mid q+1$ y es $\big(\frac{q}{p}\big)$ en el resto de los casos.
\medskip 



Normalmente se añaden a la ley de reciprocidad cuadrática un par de evaluaciones de evaluaciones del sím\-bo\-lo de Legendre llamadas ``leyes suplementarias'', aunque no tienen ni mucho menos la misma profundidad. Son las siguientes:
\[
  \Big(\frac{-1}{p}\Big)
  =
  (-1)^{(p-1)/2}
 \qquad\text{y}\qquad
  \Big(\frac{2}{p}\Big)
  =
  (-1)^{(p^2-1)/8}
  \qquad\text{para $p>2$ primo}.
\]

\ejer
Utilizando que $G(-1,p)$ es el conjugado de $G(1,p)$, prueba la primera ley suplementaria. 
\medskip 

Aunque \eqref{gleg} es también válido para $p=2$, el hecho de que $G(1,2)=0$ invalida su uso. 

\ejer
Aplica \eqref{gleg} con $q=8$ y adapta la demostración que has dado de \eqref{qrl} para concluir la segunda ley suplementaria. 
{\sf Indicación}: ¿Por qué $G(8,p)=G(2,p)$?
\medskip



La definición del símbolo de Legendre se extiende a módulos compuestos. 
Concretamente, para $m>2$ impar cuya factorización en primos es $m=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$  se define el \emph{símbolo de Jacobi} como
\[
 \Big(\frac{n}{m}\Big)
 =
 \prod_{j=1}^k
 \Big(\frac{n}{p_j}\Big)^{\alpha_j}.
\]
Si $m$ no es primo,  la solubilidad de $x^2-n\equiv 0\ (m)$ no está asegurada porque valga uno. Esto está relacionado con 
el ``quadratic residuosity problem'' \cite{wiki_qrp} que es la base del criptosistema del último ejercicio. 


Esta definición permite extender \eqref{gleg} al caso compuesto. Veámoslo para potencias de primos.
%(dicho sea de paso, algo similar al próximo ejercicio se puede hacer reemplazando en las sumas de Gauss $n^2$ por otras potencias \cite[Lemma~4.4]{vaughan}).

\ejer
Justifica las siguientes igualdades para $p$ y $q$ como en \eqref{gleg} y $k\ge 2$ entero:
\[
 G(q,p^k)=
 \sum_{m=0}^{p-1}
 \sum_{\ell =0}^{p^{k-1}-1}
 e
 \Big(
 \frac{q(p^{k-1}m+\ell)^2}{p^k}
 \Big)
 =
 p
 \sum_{\ell =0,\, p\mid \ell}^{p^{k-1}-1}
 e
 \Big(
 \frac{q\ell^2}{p^k}
 \Big)
 =
 p\,G(q,p^{k-2}).
\]
Demuestra con ello que \eqref{gleg} es cierto reemplazando $p$ por $p^k$. 
\medskip 


Una pequeña sorpresa a este nivel es que el símbolo de Legendre es multiplicativo es su primer argumento, por tanto, el de Jacobi también. Aunque sea un poco retorcido, vamos a proceder usando las sumas de Gauss.

\ejer
Con variaciones de los dos ejercicios que llevaron a \eqref{gleg}, separando los casos 
$\big(\frac{q_2}{p}\big)=\pm 1$, muestra que para $q_1,q_2\in\Z$ y $p>2$ primo $p\nmid q_1q_2$ se tiene 
$G(q_1q_2,p)=
\big(\frac{q_2}{p}\big) G(q_1,p)$. Deduce que el símbolo de Jacobi es completamente  multiplicativo, esto es, 
\[
 \Big(\frac{q_1q_2}{m}\Big)
 =
 \Big(\frac{q_1}{m}\Big)
 \Big(\frac{q_2}{m}\Big)
 \qquad 
 \text{para $q_1,q_2\in\Z$ y $m\in\Z^+$ impar}.  
\]
{\sf Indicación}: ¿Por qué basta considerar el caso en que $m$ es primo?
\medskip

Una vez que sabemos que los símbolos de Jacobi son multiplicativos en ambos argumentos, se sigue una ley de reciprocidad cuadrática para los símbolos de Jacobi, esto es, una generalización de \eqref{qrl}. Vamos a descomponer la prueba en dos ejercicios. Si necesitas ayuda para el segundo, da un vistazo a la demostración (muy esquemática) que doy en \cite[Prop.\, 1.3.8]{ch_lrc} (también \cite[\S3.6]{hua} te puede resultar útil).
Además, se cumplen las leyes suplementarias. No nos meteremos en ello para no alargar más la hoja.

\ejer
Prueba que \eqref{qrl} también se verifica si se sustituyen $p$ y $q$ por $p^k$ y $q^\ell$ con $k,\ell\in\Z^+$.
{\sf Indicación}: Si $k$ y $\ell$ no son ambos impares, $(p^k-1)(q^\ell-1)/4$ es par y el resultado es bastante obvio. 


\ejer
Demuestra
 \[
  \Big(\frac{n}{m}\Big)
  \Big(\frac{m}{n}\Big)
  =(-1)^{(n-1)(m-1)/4}
  \qquad\text{para $n,m\in\Z^+$ impares y coprimos}.
 \]
\medskip


Empleando todo lo que has aprendido estamos en condiciones de obtener la evaluación completa de las sumas de Gauss generalizadas $G(a,b,q)$ cuando $q$ es impar.
A ver si consigues resolver el siguiente ejercicio sin indicaciones. 

\ejer 
Demuestra que para $q\in\Z^+$ (no necesariamente primo) se cumple 
\[
 G(a,b,q)=i^{(q-1)^2/4}
 \sqrt{q}
 \Big(\frac aq\Big)
 e\Big(-\frac{\overline{4a}b^2}{q}\Big)
\]
donde $\overline{4a}$ indica el inverso módulo $q$, esto es, $4a\overline{4a}\equiv 1\ (q)$. 
\medskip


La reciprocidad cuadrática de los símbolos de Jacobi permite elaborar un algoritmo eficiente para decidir si $x^2\equiv n\ (m)$ tiene solución o no para $n$ y $m$ de tamaño razonable \cite[\S3.6]{hua} (tal algoritmo se amplia a cualquier ecuación de segundo grado \cite{ch_lrc}).
Si  $n$ y $m$ son astronómicamente grandes, tal algoritmo, que requiere la factorización, colapsa con nuestros conocimientos y ordenadores actuales. Esta es la base del \emph{criptosistema de Goldwasser-Micali}. Hay que aclarar que en la práctica no es muy interesante porque otros criptosistemas lo superan. 

\ejer
Lee en \cite{wiki_GoMi} acerca del criptosistema de 
Goldwasser-Micali y escribe unas líneas sobre él. Si ves que no lo entiendes bien o estás corto de espacio, basta con que pongas una referencia. 


\



\begin{center}
\noindent\rule{0.95\textwidth}{1.1pt}
\end{center}


\paragraph{Tarea a entregar.}
Escribe un documento que combine las soluciones de los ejercicios anteriores.   La extensión recomendada es de 6 páginas con el formato de esta hoja o de la plantilla. Si te ves apurado, reduce al mínimo el último ejercicio y da solo una idea de la prueba de la reciprocidad cuadrática de los símbolos de Jacobi. El resultado conformará un segundo capítulo de tu TFG  llamado {\sl La ley de reciprocidad cuadrática} o algo parecido.

\begin{center}
\noindent\rule{0.95\textwidth}{1.1pt}
\end{center}



\bibliography{bibtfg24SL}
\bibliographystyle{plain}

\end{document}

