For $n \in \mathbb{Z}^+$, $x \in \mathbb{Z}$, $k \in \mathbb{Z}$, $F(n)=\min(|n^2-17x|)$ must be $0$ or $2^k$

Question

I've difficult to understand the question that was given to me yesterday:

Prove that for $n \in \mathbb{Z}^+$, $x \in \mathbb{Z}$, $k \in \mathbb{Z}$, $F(n)=\min(|n^2-17x|)$ must be $0$ or $2^k$

I've divided into two cases: if $n = 2i+1$ (odd) and $n = 2i$ (even), but I'm stuck at this point.

Any hints? I do not understand the || in this context.

Thanks

Answer 1

You should instead divide into $17$ cases. The quantity $F(n)$ is entirely determined by the remainder of $n$ when divided by $17$. To prove this, show that if $n$ and $m$ have the same remainder upon division by $17$, then so do $n^2$ and $m^2$, and realize that the remainders of $n^2$ and $m^2$ determine their distance to the nearest multiple of $17$.

So you only need look at $n=1,2,\dots,17$, and note that for each, $F(n)=0,1,2,4$ or $8$.