/sci/ - Science & Math

>>12533437
my solution for 2 is roughly:
after some thinking, it's enough to evaluate the sum [math]\sum_{i=0}^{p-1} \left( \frac{i}{p} \right) \left( \frac{i+1}{p} \right) [/math] mod p,
that's equal to [math]\sum_{i=0}^{p-1} (i^2 + i)^{(p-1)/2} [/math], we expand:
[eqn]\sum_{i=0}^{p-1} \sum_{j=0}^{(p-1)/2} {(p-1)/2 \choose j} i^{(p-1)/2 + j}[/eqn]
and the point is we can change the order of summation, and use 1^k + 2^k + ... + (p-1)^k = 0 if p-1 doesn't divide k, otherwise it's p-1.
for 3 residues, it would be enough to compute [math]\sum_{i=0}^{p-1} \left( 1 + \left( \frac{i}{p} \right)\right) \left( 1 + \left( \frac{i+1}{p} \right)\right)\left( 1 + \left( \frac{i+2}{p} \right)\right) [/math] and i think reusing the trick from the solution above will lead to a solution... but that's going to be long and ugly

Here's one more problem i like, although it's a bit less "math-olympiad-style":
3. find all rational numbers p/q such that [math]\cos( \pi p / q)[/math] is rational