
I-4 Find all integers $k$ such that for every integer $n$, the numbers $4 n+1$ and $k n+1$ are relatively prime.


Solution. Since $4 n+1$ is odd, the identity $k-4=k(4 n+1)-4(k n+1)$ shows that $4 n+1$ and $k n+1$ are relatively prime if $k-4$ has not any odd divisor $p>1$, i.e. if $k-4= \pm 2^{k}$ with any nonnegative integer $k$.

On the other hand, if $k-4$ has got an odd divisor $p>1$, then we can easily find a multiple of $p$ of the form $4 n+1$ (for example, the number $p^{2}$ or simply one of the numbers $p, 3 p$ ). For any number $4 n+1$ being a multiple of $p$, the above identity implies that $p \mid k n+1$, hence $4 n+1$ and $k n+1$ are not relatively prime.

Answer: $k=4 \pm 2^{k}$, where $k=0,1,2, \ldots$


[^0]:    ${ }^{1}$ Remove two white 2-diagonals of one direction and two white $(n-1)$-diagonals of the other direction; the remaining white squares form the same diagonals as white squares of the chessboard $(n-2) \times(n-2)$.

    2 Remove one black $n$-diagonal; the remaining black squares form the same diagonals as the white squares of the chessboard $(n-1) \times(n-1)$.

