Set of divisors

Question

Let $a, b, c, d$ positive integer, every two relatively coprime. Then the set $\lbrace gcd( an +b, cn + d)| n \in \mathbb{N} \rbrace$ is the set of the divisors of an natural number. I saw that the set is finite, but I don't know how to characterize the conclusion.

Answer 1

If $k\ | \ an + b$ and $k \ | \ cn + d$, then $k \ | \ c(an+b) - a(cn+d) = bc - ad$. Therefore every element in your set must divide $\Delta = |bc - ad|$.

For the converse statement, you need to show that every positive divisor of $\Delta$ is in the set. Without loss of generality let $ad - bc > 0$.

On the Cartesian plane the vectors $(a, c)$ and $(b, d)$ form a parallelogram with area $\Delta$. As $a, b, c, d$ are pairwise relatively prime, the edges parallelogram does not have any integral points except for the vertices.

Fact 1: There are $\Delta - 1$ integral points lying in the parallelogram.

Fact 2: The $\Delta - 1$ integral points lying in the parallelogram have pairwise distinct distance to the segment $\overline{AC}$, where $C = (a, c)$.

Fact 2 is true because again $a, b, c, d$ are pairwise relatively prime.

Now we can label the interior integral points as $A_1, \cdots, A_{\Delta-1}$ based on the distance to the segment $\overline{AC}$ ($A_1$ is the closest). Denote the coordinate of $A_i = (x_i, y_i)$. Now, let $f \ | \ \Delta$.

Fact 3: $$ \frac{\Delta}{f} A_f = m_f (a, c) + (b,d) \quad\mbox{for some $m_f \in \mathbb N$}. $$

Therefore, if $\gcd(x_f, y_f) = 1$, we can immediately conclude that $\gcd(m_fa+b, m_fc+d) = \frac\Delta f$. If this is not the case, you need to "twist" $(x_f, y_f)$ into some $A_f' = (x_f, y_f) + m(a, c)$ for some $m$ so that the $x$ and $y$-coordinate are coprime. This is possible because $a$ and $c$ are coprime.

Example: We will illustrate this by an example $(a, b, c, d) = (5, 1, 3, 7)$. $\Delta = 32$, and the parallelogram is as follows:

$A_1 = (3,2)$ (the closest point to the segment $\overline{AC}$). So $32A_1 = (96, 64) = 19(5,3) + (1,7)$.

$A_2 = (1,1)$. So $16A_2 = (16,16) = 3(5,3) + (1,7)$.

$A_4 = (2,2)$. Since the coordinates are not coprime we twist it to $A_4' = A_4 + (5,3) = (7,5)$. So $8A_4' = (56,40) = 11(5,3) + (1,7)$.

$A_8 = (4,4)$. Since the coordinates are not coprime we twist it to $A_8' = A_8 + (5,3) = (9,7)$. So $4A_4' = (36,28) = 7(5,3) + (1,7)$.

$A_{16} = (3,5)$. So $2A_{16} = (6,10) = 1(5,3) + (1,7)$.

Remark: If you know some group theory, the black magic behind this is that $\Lambda = \mathbb Z(a,c) + \mathbb Z(b,d) \subseteq \mathbb Z^2$ defines a subgroup of $(\mathbb Z^2, +)$. The key fact is that while $a,b,c,d$ are pairwise relatively prime, The quotient group $\mathbb Z^2/\Lambda$ is cyclic of order $\Delta$. The point $A_1$ is merely a careful choice of the generator of the quotient subgroup.