tjhance wrote:

I think the right answer is $ 4\pm 2^n, n \in \mathbb{N}U\{0\}$. - If $ k > 4$ then $ gcd(4n + 1, kn + 1) = gcd(4n, k - 4)$; if $ p > 2$ prime s.t. $ p|k - 4$ and $ p = 4t + 1$ then we can choose $ n = t$, and if $ p = 4t + 3$ then $ 3p = 12t + 9 = 4(3t + 2) + 1$. so $ k = 4 + 2^n$ - If $ 0\le k \le 4$ then the only solutions are in the set $ \{0,2,3\}$ (by hand ) - If $ k < 0$, let $ K = - k > 0$ so $ gcd(4n + 1,kn + 1) =$ $ gcd(4n + 1,Kn - 1) = gcd(4n + 1,n(K + 4)) =$ $ gcd(4n + 1,K + 4)$, so $ K = - k = 2^n - 4, n \in \mathbb{N}$, so we are done.

It is a well known fact that Lema1 $ \gcd (a,a - b) = 1 \rightarrow \gcd(a,b) = 1$ So we only have to check for what $ k$ $ \gcd(4n + 1,4 - k) = 1$ Lema2 For some $ n \in \mathbb{Z}$ it is true that $ 4n \equiv - 1 (\mod p)$ for every prime $ p\neq2$ Proof: Since $ p\neq2$, $ p$ is odd Case1 if $ p \equiv 3 (\mod 4)$ then the number $ 2p + p - 1 \equiv - 1 (\mod p)$ and also $ 2p + p - 1 \equiv 0 (\mod 4)$ Case2 if $ p \equiv 1 (\mod 4)$ then the number $ 4p + p - 1 \equiv - 1 (\mod p)$ and also $ 4p + p - 1 \equiv 0 (\mod 4)$ $ \blacksquare$ So if we want $ \gcd(4n + 1,4 - k) = 1$ then $ 4 - k$ must be a power of two.It is easy to see that if $ 4 - k$ is a power of two it is also true $ \gcd(4n + 1,4 - k) = 1$ So $ k$ is $ \pm 2^n + 4$ for some $ n \in \mathbb{N}_0$