Different solution, I think?

Solution

We strong induct on $a+c$ .

Our base case is $a+ c = 2$ , i.e. $a = c = 1$ . Then, note that $d = ad \neq bc = b$ . WLOG suppose $b < d$ . Then, $\gcd(an+b, cn+d) = \gcd(n+b, n+d) = \gcd(n+b, d-b),$ which divides $d-b$ , and can hit any divisor $k$ of $d-b$ by setting $n+b \equiv k\pmod{d-b}$ , i.e. $n\equiv k-b\pmod{d-b}$ (there exists a positive integer solution to this since you can just add $d-b$ to make it positive), and such a solution would have $n+b = (d-b)r + k$ for some integer $r$ , so $\gcd(n+b, d-b) = \gcd((d-b)r + k, d-b) = \gcd(k, d-b) = k$ , as $k \mid d-b$ . Thus, our base case is established.

Now, we move on to the inductive step. Assume that for some $N\geq 3$ , the statement is true for all $a, b, c, d$ satisfying the conditions of the problem, and satisfying $2\leq a+c \leq N-1$ . We will prove that the statement is true for all $a, b, c, d$ satisfying the conditions of the problem with $a+c = N$ .

We have two cases -- $a \neq c$ and $a = c$ .

If $a \neq c$ , then WLOG suppose $a > c$ , since we can swap $(a, b, c, d)$ with $(c, d, b, a)$ and the problem remains unchanged. Now, note that $\gcd(an+b, cn+d) \mid |c(an+b)-a(cn+d)| = |bad-bc|,$ and $|ad-bc| > 0$ since we are given that $ad\neq bc$ . This implies that $\gcd(an + b, cn+d) = \gcd(a(n + |ad-bc|)+b, c(n+|ad-bc|) + d),$ since if $x\mid \gcd(an+b, cn+d)$ , then $x \mid |ad-bc|$ , and $x \mid an+b$ , $x\mid cn+d$ , and so $x\mid a(n+|ad-bc|) + b$ , $x\mid c(n + |ad-bc|) + d,$ so $x \mid \gcd(a(n+|ad-bc|) + b, c(n+|ad-bc|) + d)$ , and if $y \mid \gcd(a(n+|ad-bc|)+b, c(n+|ad-bc|) + d)$ , then $y \mid |ad-bc|$ (note that $\gcd(a(n+|ad-bc|)+b, c(n+|ad-bc|) + d) = \gcd(am+b, cm+d) \mid |ad-bc|$ , where $m = n+|ad-bc|$ ), $y \mid a(n+|ad-bc|) + b$ , and $y \mid c(n+|ad-bc|)+d$ , so $y \mid an+b$ , $y \mid cn+d$ , so $y \mid \gcd(an+b, cn+d)$ , and so the two gcd's are equal (by taking $x = \gcd(an+b, cn+d)$ and $y = \gcd(a(n+|ad-bc|)+b, c(n+|ad-bc|)+d)$ . The relevancy of this is that $S = S_r := \{\gcd(an+b, cn+d) \mid n \geq r\}$ for any positive integer $r$ , since clearly $S_r\subseteq S$ , and if $x\in S$ , then $x = \gcd(an+b, cn+d)$ for some positive integer $n$ , so we can take a positive integer $k$ for which $n + k|ad-bc| > r$ and then $x = \gcd(an+b, cn+d) = \gcd(a(n+k|ad-bc|) + b, c(n+k|ad-bc|)+d),$ and $n+k|ad-bc| > r$ , so $x\in S_r$ , and so $S\subseteq S_r$ , so they are both subsets of each other and so $S_r = S$ .

Now, note that $\gcd(an+b, cn+d) = \gcd((a-c)n+(b-d), cn+d).$ Take some positive integer $k$ with $(a-c)k + (b-d) > 0$ . Then, note that $\{\gcd((a-c)n+(b-d), cn+d) \mid n\geq k \} = \{ \gcd(an+b, cn+d) \mid n \geq k\} = S_k = S,$ so $S$ is the set of all values of $\gcd((a-c)n + (b-d), cn+d)$ for $n > k$ . If $n = k + m$ , then $m$ is a positive integer, so $S$ is the set of all values of $\gcd((a-c)(m+k) + (b-d), c(m+k) + d) = \gcd((a-c)m + [(a-c)k+(b-d)], cm + [ck+d])$ for all positive integers $m$ . Now, note that by our choice of $k$ , and since $a > c$ , we have that $a-c, (a-c)k + (b-d), c, ck+d$ are positive integers, $\gcd(a-c, (a-c)k+(b-d), c, ck+d) = 1$ , since if a prime $p$ divided the gcd, it would divide all the individual entries, so $p\mid c$ , $p\mid a-c$ , so $p\mid a$ , and $p\mid ck+d$ , so $p\mid d$ . Then, $p\mid (a-c)k + (b-d)$ , so $p\mid b$ , so $p\mid \gcd(a, b, c, d) = 1$ , a contradiction. Also, $(a-c)(ck+d) = c(a-c)k - cd + ad \neq c(a-c)k - cd + bc = [(a-c)k+(b-d)]c,$ since $ad \neq bc$ . Also, $2 \leq (a-c) + c < a+c = N$ , both bounds being due to the fact that $a, c$ are positive integers and $a - c$ is as well since $a > c$ , so $2\leq (a-c) + c \leq N-1$ . Thus, by the inductive hypothesis, $S$ is the set of all divisors of some positive integer, as desired.

If $a = c$ , then WLOG suppose $b < d$ , since we know that $bc\neq ad = dc$ , so $b \neq d$ , and we can swap $(a, b, c, d)$ with $(c, d, a, b)$ and the problem remains unchanged. Then, note that $\gcd(an+b, cn+d) = \gcd(an+b, an+d) = \gcd(an+b, d-b).$ Now, let $X = \frac{d-b}{\prod_{p \mid \gcd(a, d-b)}p^{\nu_p(d-b)}}.$ (If $\gcd(a, d-b) = 1$ , then the product is $1$ by convention.) I claim that $S$ is the set of divisors of $X$ . To prove this, write $\gcd(an + b, d-b) = \gcd(an+b, X \prod_{p\mid \gcd(a, d-b)}p^{\nu_p(d-b)}).$ Note that $\gcd(an+b, \prod_{p\mid \gcd(a, d-b)}p^{\nu_p(d-b)}) = 1,$ since if a prime $q$ divided the gcd, then $q \mid an+b$ , and $q \mid \prod_{p \mid \gcd(a, d-b)}p^{\nu_p(d-b)}$ , so since $q$ divides the product, it follows that $q \mid \gcd(a, d-b)$ , since the primes that appear in the product are precisely the ones that divide $\gcd(a, d-b)$ . Then, $q \mid a$ and $q \mid d-b$ , however $q$ cannot divide $b$ , since if $q\mid b$ , then $q \mid d$ , and so $q \mid \gcd(a, b, d) = \gcd(a, b, a, d) = \gcd(a, b, c, d) = 1$ , absurd. Thus, $q\mid a$ and $q\nmid b$ , so $q\nmid an+b$ , a contradiction (since $q\mid an+b$ ). Thus, we have that $\gcd(an+b, X\prod_{p\mid \gcd(a, d-b)}p^{\nu_p(d-b)}) = \gcd(an+b, X).$ Now, note that $\gcd(a, X) = 1$ , since if a prime $p \mid a$ and $p \mid X$ , then since $p \mid X$ , $p\mid d-b$ , so $p \mid \gcd(a, d-b)$ . Then, note that $\nu_p(X) = \nu_p\left(\frac{d-b}{\prod_{p\mid \gcd(a, d-b)}p^{\nu_p(d-b)}}\right) = \nu_p(d-b) - \nu_p(d-b) = 0,$ so $p\nmid X$ , a contradiction. Thus, $\gcd(a, X) = 1$ . Now, it is clear that $\gcd(an+b, X)$ has to be a divisor of $X$ . Now, let $d$ be a divisor of $X$ . Then, choose a positive integer $n$ for which $n \equiv \frac{d-b}{a} \pmod{X},$ such an $n$ exists since $\gcd(a, X) = 1$ . Then, $an + b \equiv d\pmod{X},$ so if $an+b = Xk+d$ for some integer $k$ , then $\gcd(an+b, X) = \gcd(Xk+d, X) = \gcd(d, X) = d,$ as $d\mid X$ . Thus, $S$ is the set of all divisors of some positive integer (namely, $X$ ), as desired.

Thus, our inductive step is complete and so we're done. $\blacksquare$