I came across this in a programming contest:
f(x)%k = f(x+2k)%k for f(x)=x(x+1)/2 + c
I first thought that this is a property of Harmonic numbers only but after trying a few things, I found out that
f(x)%k = f(x+k*a*b)%k for f(x)= x/a + x^2/b + c
My question is how can this be derived intuitively?
Which branch of Mathematics does this fall into ? I have a hint that this is number theories, but is there a particular concepts/topic that programming contests assume that contesters should know as basics/foundation?
Is there a more general form of this theorem? Beyond quadratic? (and if it has a name, what it is called? )
Domain: a, b, c, k and x are Positive integers
$f(x+2k)\equiv \frac{(x+2k)(x+2k+1)}{2}+c \pmod k$
$\equiv \frac{x^2+2kx+x+2kx+4k^2+2k}{2}+c \pmod k$
$\equiv k(2x+2k+1)+\frac{x^2+x}{2}+c \pmod k$
$\equiv \frac{x(x+1)}{2}+c \pmod k$
$\equiv f(x) \pmod k$