Why is $f(x)\equiv f(x+2k)\pmod k$ for$ f(x)=x(x+1)/2 + c.$

83 Views Asked by At

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

1

There are 1 best solutions below

0
On

$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$