For what $k$ are the numbers $4n+1, kn+1$ coprime?

Question

Already knowing the answer gives me sort of a hint ($k=\pm2^m+4 : m \in \mathbb{N} \cup \{0\}$), but I can't really find a way through it.

Bonus question: how about a generalisation of this problem? When we are given any natural number m instead of 4?

Answer 1

The two facts that you need to know:

1. $\gcd(a, b) = \gcd(a, b + ac)$.
2. If $\gcd(a, b) = 1$, then $\gcd(a, bc) = \gcd(a, c)$.

Combining these, we have: $$\gcd(4n + 1, kn + 1) = \gcd(4n + 1, (k - 4)n) = \gcd(4n + 1, k - 4).$$ The first equality comes from 1, the second from 2 and the fact that $\gcd(n, 4n + 1) = \gcd(n, 1) = 1$, which again comes from 1.

The rest should be quite clear. You may also work out your generalized problem along the same lines.