Let p=1601. Prove that if 102+1+112+1+⋯+1(p−1)2+1=mn, where we only sum over terms with denominators not divisible by p (and the fraction mn is in reduced terms) then p∣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∣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 ±i∈Fp such that i2=−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.