Find all integers k such that : gcd(4*M +1, k*M+1) = 1 for every integer value of M.

After playing with this a little, the pattern becomes clear.

Let M = 2. Then we need gcd(9,2k+1) = 1. k cannot be 4, or 4 + 3n where n is any integer

Let M = 1. Then we need gcd(5,k+1) = 1. k cannot be 4, or 4 + 5n where n is any integer

Let M = 5. Then we need gcd(21,5k+1) = 1. k cannot be 4 + 7n where n is any integer (or 4 + 3n, but we knew that already)

Let M = 8. Then we need gcd(33,8k+1) = .1 k cannot be 4, or 4+ 11n where n is any integer (or 4 + 3n, but we knew that already).

In fact, k cannot be 4 + ab where a is odd and n is any integer

So, k can only be 4 +/- 2^n where n is any non-negative integer

Possible values include

n = 0 k = 4 +/- 1 = 3 or 5

n = 1 k = 4 +/- 2 = 2 or 6

n = 2 k = 4 +/- 4 = 0 or 8

n = 3 k = 4 +/- 8 = -4 or 12

n = 4 k = 4 +/- 16 = -12 or 20

n = 5 k = 4 +/- 32 = -28 or 36

etc.

possible values therefore include

... -28, -12, -4, 0, 2, 3, 5, 6, 8, 12, 20, 36 ...