Let $p=1601$. Prove that if \[\dfrac {1} {0^2+1}+\dfrac{1}{1^2+1}+\cdots+\dfrac{1}{(p-1)^2+1}=\dfrac{m} {n},\] where we only sum over terms with denominators not divisible by $p$ (and the fraction $\dfrac {m} {n}$ is in reduced terms) then $p \mid 2m+n$. Proposed by A. Golovanov
Problem
Source: Tuymaada 2012, Problem 4, Day 1, Juniors
Tags: quadratics, modular arithmetic, number theory, number theory proposed
mavropnevma
21.07.2012 15:22
Similar with Problem 4, Senior League; only that here $p=4k+1$ and $p\mid 2m + n$ (it is essential that $p=1601$ is a prime of this form). However, the proceedings are much simplified by the fact that now $-1$ is a quadratic residue modulo $p$, namely that there exist two elements $\pm \textrm{i} \in \mathbb{F}_p$ such that $\textrm{i}^2 = -1$.
By Wilson's theorem, we may even exhibit these two special elements. We have $(p-1)! \equiv -1 \pmod{p}$, but also
\[(p-1)! = \left (\prod_{\ell=1}^{(p-1)/2} \ell\right )\left (\prod_{\ell=1}^{(p-1)/2} (p-\ell)\right ) \equiv (-1)^{\frac {p-1} {2}}(((p-1)/2)!)^2 \pmod{p},\]
so $\textrm{i} = ((p-1)/2)!$.
In the case at hand, it is immediately visible that since $p=1601 = 40^2 + 1$ we will have $\textrm{i} = 40$ (although knowing the exact value is irrelevant in the sequel).
Let us notice now that $p$ does not divide any of the denominators $\ell^2+1$ for $\ell \neq \pm \textrm{i}$ (and it divides $\textrm{i}^2+1$ and $(-\textrm{i})^2+1$).
Denote the expression by $E$, so $\displaystyle E=\sum_{\ell\neq \pm \textrm{i}} \dfrac {1} {\ell^2 + 1}$; having $E = \dfrac {m} {n}$ yields $2E+1 = \dfrac {2m+n} {n}$, and the thesis now writes as needing to prove $2E + 1\equiv 0 \pmod{p}$.
But
\[E=\sum_{\ell\neq \pm \textrm{i}} \dfrac {1} {\ell^2 + 1} = \sum_{\ell\neq \pm \textrm{i}} \dfrac {1} {(\ell - \textrm{i})(\ell + \textrm{i})} = \dfrac {1} {2\textrm{i}} \sum_{\ell\neq \pm \textrm{i}} \left (\dfrac {1} {\ell - \textrm{i}} - \dfrac {1} {\ell + \textrm{i}}\right ).\]
The sum above telescopes to $\dfrac {1} {2\textrm{i}}\left (\dfrac {1} {2\textrm{i}} - \dfrac {1} {-2\textrm{i}}\right ) = \dfrac {1} {2\textrm{i}^2} = -\dfrac {1} {2}$.
Therefore we get $E \equiv -\dfrac {1} {2} \pmod{p}$, i.e. $2E + 1 \equiv 0 \pmod{p}$, as desired.
mavropnevma
24.07.2012 09:50
This link http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=490409 points to a unification with Problem 4, Day 1, Senior League.