Show that $\sum_{k=1}^{p-1}f(k)=\sum_{k=1}^{p-1}f(qk)$

Question

I would appreciate if somebody could help me with the following problem

Q: Show taht $$\sum_{k=1}^{p-1}f(k)=\sum_{k=1}^{p-1}f(qk)$$ where $\gcd(p,q)=1, f(p+x)=f(x)$

Answer 1

The idea is to note that $$\psi(k)=qk\mod p=qk-p\lfloor kq/p\rfloor$$ is a bijection from $Z_p=\{0,1,2,\ldots,p-1\}$ onto itself.

To see this it is enough to note that $\psi$ is one to one, because $Z_p$ is a finite set. Indeed if $\psi(k)=\psi(l)$ then $p$ divides $q(k-l)$, and since $\gcd(p,q)=1$ this implies that $p$ divides $k-l\in\{1-p,\ldots,-1,0,1,\ldots,p-1\}$, so $k-l=0$ and $\psi$ is injective.

Now, $\psi(0)=0$ so $\psi$ defines a bijection on $Z_p\setminus\{0\}$. So $$ \sum_{k=1}^{p-1}f(k)=\sum_{k=1}^{p-1}f(\psi(k))=\sum_{k=1}^{p-1}f(qk) $$ where we used the $p$-periodicity of $f$ in the final step.$\qquad\square$

Answer 2

let $a$ and $b$ be distinct numbers in the range $1,...,p-1$

if $$ qa \equiv_p qb $$ then $p$ divides $q(a-b)$ - which cannot be since $(p,q)=1$ and $0 \lt |a-b| \lt p$

hence the $p-1$ numbers $qk$ taken $\mod p$ are exactly the same as the numbers $1,..p-1$,just in a different order. since the sum is finite, such a reordering has no effect on the sum.