First note that elements of $S$ a all must divide $c(an+b)-a(cn+d) = bc - ad \neq 0$. Next, we show $S$ is closed downwards. Claim: Suppose $k \in S$ and the prime $p$ divides $k$. Then $k/p \in S$ as well. Consequently, all divisors of $k$ are in $S$. Proof. Let $p \mid k = \gcd(an+b,cn+d)$; it follows $p \nmid \gcd(a,c)$ (since otherwise $p \mid \gcd(a,b,c,d)$ too). So WLOG $a \not\equiv 0 \pmod p$. Let $e = \nu_p(k)$ and construct $n'$ (by Chinese theorem) such that \begin{align*} n' &\equiv n + p^{e-1} \pmod{p^e} \\ \text{and} \quad n' &\equiv n \pmod{q} \end{align*}for any prime power $q$ dividing $bc-ad$. We contend $\gcd(an'+b, cn'+d) = k/p$. Indeed $\nu_p(an'+b) = e-1$ and $\nu_p(cn'+d) \ge e-1$. So the exponent of $p$ in $\gcd(an'+b,cn'+d)$ is correct. Moreover, since $n' \equiv n \pmod{q}$, the exponents of any other primes do not change. $\blacksquare$ Next, we prove $S$ is closed under LCM's. Claim: Suppose $k_1, k_2 \in S$. Then $\operatorname{lcm}(k_1, k_2) \in S$. Proof. By the previous claim it suffices to show some multiple of $\operatorname{lcm}(k_1, k_2)$ is in $S$. If $k_1 = \gcd(an_1+b, cn_1+d)$ and $k_2 = \gcd(an_2+b, cn_2+d)$. We choose $n$ such that: for each prime $p \mid ad-bc$, if $q = p^{\nu_p(bc-ad)}$ then \[ n \equiv \begin{cases} n_1 \pmod q & \nu_p(k_1) \ge \nu_p(k_2)\\ n_2 \pmod q & \text{otherwise}. \end{cases} \]Then $\nu_p(\gcd(an+b, cn+d)) \ge \max(\nu_p(k_1), \nu_p(k_2))$ for each $p$ as desired. $\blacksquare$ Thus if $m = \max S < \infty$ then $S$ consists of exactly the divisors of $m$. Remark: One can also proceed by using the Euclidean algorithm. Indeed, $\gcd(an+b,cn+d) = \gcd( (a-c)n+(b-d), cn+d )$, and if $(a,b,c,d)$ satisfies the problem conditions then so does $(a-c,b-d,c,d)$. By repeating this we find it suffices to consider the case $a=0$, which can be done essentially by hand.

Probably the best problem of RMM this year imho...

This problem was proposed by Raul Alcántara, Peru.

rkm0959 wrote: Does anyone know of a closed form for M? Nvm RMM official solution kinda gives it away. A close form of $M$ could be the greater positive divisor of $ab-cd$ which has not common prime divisors with $gcd(a,c)$

Strangely, it seems to be harder than #5 and #6 (or maybe I am weird) My solution (along with how it was motivated, just for storage): It is clear that $S$ is finite, as the mentioned $\gcd$ divides $c(an+b)-a(cn+d) = bc - ad$. Consider the maximum element of the set $S$. The idea is to decrease the exponent of any prime in the prime factorisation of a number in the set $S$ by exactly one. Suppose $x$ is in the set, and the corresponding $n$ is $n$. We need to decrease the exponent of a particular prime $p$ dividing $x$ by exactly one, while letting the other primes untouched. So we need to add the prime power just smaller than the one that fully divides $x$. So if we have $\nu_p(x) = v$, then consider the number $m$ such that $m \equiv n + p^{v-1} \pmod{p^v}$ and $m \equiv b \pmod{\frac{bc-ad}{p^{\nu_p(bc-ad)}}}$. This clearly works because $p$ is coprime to the gcd of $a,c$. So atleast one of $am+b, cm+d$ have the highest power of $p$ dividing them as $v-1$, which decreases the power of $p$ in the prime factorisation by exactly one. By performing this procedure for all prime factors of the maximum element of $S$ and repeating it, we are done, after noting that for every pair of elements in $S$, their lcm is in $S$ too ($v_p$ arguments).

On the test I proved that $S=lcm(ad-bc,b_a,d_c)$, where $x_y = \prod_{v_p(y)<v_p(x), p: prime}^{} p^{v_p(x)-v_p(y)} gcd(x,y)$. What do you guys think?

@ v_Enhance, WizardMath -- Maybe I'm missing the point of the argument but don't we also need that there is no attainable gcd $x$ such that $x \nmid m$ where $m = \max S$?

OOPS. You are right. I think you can fix it more simply by just showing the l.c.m. of two elements of $S$ is in $S$ (you do not have to do it at the level of individual primes). I'll edit my post to something hopefully right.

Wow! That addition is way more elegant than what I did. Cool!

The following problem was proposed by Iurie Boreico for Mathematical Reflections 2006 Issue 6. Let $a, b, c, d $ be integers such that $gcd(a, b, c, d) = 1 $ and $ad-bc\neq 0$. Prove that the greatest possible value of $gcd(ax + by, cx + dy)$ over all pairs $(x, y)$ of relatively prime is $|ad - bc|.$

I think we can potentially clean the write-up (avoiding use of $\operatorname{lcm}(k_1,k_2) \in S$) by taking $M=\prod_{p} p^{k_p}$ where $k_p \le v_p(ad-bc)$ is the maximum exponent of any prime $p$ in the factorisation of elements of $(\gcd(an+b,cn+d))_n$. Now like rkm's solution, we can pick $n$ such that for any $0 \le s_p \le k_p$ $v_p(\gcd(an+b, cn+d)=s_p$ by a simple Hensel's lemma deconstruction on the $n$ that attains maximum $v_p$. Applying CRT for all such primes will produce an $n$ that has the exact $v_p$ sequence as any divisor of $M$ would.

v_Enhance wrote: Remark: One can also proceed by using the Euclidean algorithm. Basically just writing out this solution fully.

Consider a fixed prime $p$. Let $x=\nu_p(\gcd(an+b, cn+d))$, so we can rewrite $x$ as $x=\min(\nu_p(an+b), \nu_p(cn+d))$. I claim the set of all values $x$ can take is $[0, m]$ for some $m$. To prove this, first note that at least one of $\nu_p(a), \nu_p(b), \nu_p(c), \nu_p(d)$ is $0$. Next, we split the problem into three cases. Case 1) $\nu_p(a)>\nu_p(b), \nu_p(c)>\nu_p(d)$. Note $\nu_p(an+b)=\nu_p(b), \nu_p(cn+d)=\nu_p(d)$, so $x=\min(\nu_p(b), \nu_p(d))=0$. Case 2) $\nu_p(a)\le \nu_p(b), \nu_p(c)> \nu_p(d)$. Then, since $\nu_p(cn+d)=\nu_p(d)$, we have $x=\min(\nu_p(an+b), \nu_p(d))$, so $x\le \nu_p(d)$. Now I claim $x$ can take on any integer from $0$ through $\nu_p(d)$. To see this, note that for any $k\ge \nu_p(a)$, we can get $\nu_p(an+b)=k$ by setting $n\equiv (\frac{a}{\nu_p(a)})^{-1} (p^{k-\nu_p(a)}-\frac{b}{\nu_p(a)})\pmod{p^{k+1-\nu_p(a)}}$. Thus, $x$ can take on any value from $\min(\nu_p(a), \nu_p(d))=0$ through $\nu_p(d)$. The $\nu_p(a)>\nu_p(b), \nu_p(c)\le \nu_p(d)$ case is symmetric to this one. Case 3) $\nu_p(a)\le \nu_p(b), \nu_p(c)\le \nu_p(d)$. First assume $\nu_p(a)=0$; the $\nu_p(c)=0$ case is symmetric. Next, note that $\gcd(an+b, cn+d)|a(cn+d)-c(an+b)=ad-bc$, meaning that $x\le \nu_p(ad-bc)$. Now I claim $x$ can take on any integer from $0$ through $\nu_p(ad-bc)$. To see this, choose any $k\in [0, \nu_p(ad-bc)]$, and set $n\equiv \frac{p^k-b}{a}\pmod{p^{k+1}}$; then, we have $\nu_p(an+b)=k$, so $an+b\equiv 0\pmod{p^k}$, and thus $acn+bc\equiv 0\pmod{p^k}$. But we also have $ad-bc\equiv 0\pmod{p^k}$, so adding gives $acn+ad\equiv 0\pmod{p^k}$, meaning $cn+d\equiv 0\pmod{p^k}$ and thus $\nu_p(cn+d)\ge p^k$, so $x=k$. Hence, $x$ can take any value from $0$ through $\nu_p(ad-bc)$. Hence, we have proven that for all primes $p$, the set of values $\nu_p(\gcd(an+b, cn+d))$ can take on is any integer in $[0, m_p]$, for integer $m_p$. Additionally, we have also shown that for $k\in [0, m]$, $\nu_p(\gcd(an+b, cn+d))$ takes on $k$ when a particular congruence of the form $n\equiv r\pmod{p^j}$ holds (for instance, in case 3, $j=k+1$ and $r$ is $(p^k-b)a^{-1} \pmod{p^{k+1}}$), so by CRT we are done.

The following problem has appeared in All-Ukrainian MO 2017: Arithmetic Progressions $\{a_i\},\{b_i\}$ and positive integers $d,m$ are given such that $d \mid m$ assuming there exists indices $i,j,l,k$ satisfying $$gcd(a_i,b_j)=1, gcd(a_k,b_l)=m,$$prove that there exists indices $m,n$ such that $gcd(a_m, b_n)=d$.

First note that $\text{gcd} (an+b,cn+d)$ is a divisor of $c(an+b)-a(cn+d) = bc-ad \neq 0$, so it only attains a finite number of values over all $n$. Let the maximum value of $\nu_p(\text{gcd} (an+b,cn+d))$ be $M_p$ for every prime $p$; then we will show that $S$ is the set of all divisors of $N=2^{M_2}3^{M_3}5^{M_5} \cdots$. Obviously every element of $S$ must divide $N$; thus it suffices to show that every divisor of $N$ is in $S$. Claim: For every prime $p$ (with $M_p>0$) and integer $0 \leq k \leq M_p$, there exists an integer $n$ such that $\nu_p (\text{gcd} (an+b,cn+d)) = k$. Proof: We induct downwards from $k=M_p$. The base case follows from the definition of $M_p$; now let just assume that the claim is true for $k=\ell$ and we will prove it for $k=\ell-1$. Let $m$ be an integer such that $\nu_p(\text{gcd}(am+b,cm+d))=\ell$, and WLOG let $\nu_p(a) \geq \nu_p(c) = f$. Note that we must have $f < M_p$; otherwise, if $f \geq M_p$, in order to have $\nu_p(\text{gcd}(an+b,cn+d))=M_p$ we must have that $b,d$ are divisible by $p$, which violates the condition $\text{gcd}(a,b,c,d)=1$. Thus the number $x=m+p^{M_p-1-f}$ is an integer; note $$\nu_p(ax+b) \geq \text{min} (\nu_p(am+b),\nu_p(ap^{\ell-1-f})) \geq \ell-1$$$$\nu_p(cx+d) = \text{min}(\nu_p(cm+d), \nu_p(cp^{\ell-1-f})) = \ell-1$$so $\nu_p(\text{gcd}(ax+b,cx+d)) = \ell-1$, completing the induction. Now note that if $n$ satisfies $\nu_p(\text{gcd}(an+b,cn+d))=k$, then the number $m=n+p^{M_p}$ also satisfies $\nu_p(\text{gcd}(am+b,cm+d))=k$. Thus for every prime $p$ and integer $k \leq M_p$, we can find in infinite arithmetic progression with common difference $p^{M_p}$ such that every term $x$ in the progression satisfies $\nu_p(\text{gcd}(ax+b,cx+d))=k$. This implies by the chinese remainder theorem that for any sequence $a_2, a_3, a_5, a_7, \dots$ with $0 \leq a_i \leq M_i$. we can find some $n$ such that $\text{gcd}(an+b,cn+d)=2^{a_2}3^{a_3}5^{a_5} \cdots$, so every divisor of $N$ is in $S$ as desired.

Notice that if we let $k = \gcd(an + b, cn + d)$ we can write $kx = an + b$ and $ky = cn+d$ for relatively prime $x, y$ and this gives $ad - bc = k(ay - cx)$ hence $k \mid |ad - bc|$. Therefore the set of possible values of the gcd $k$, say $S$, as $n$ ranges across all positive integers is finite. For any specific prime $p$, let the maximum possible value of $v_p(an + b, cn + d)$ as $n$ ranges be $e_p$. We know by previous steps that the number of positive $e_p$ is finite. Let $M = 2^{e_2}3^{e_3}5^{e_5}\ldots$. I claim that all factors of $M$ can be hit by $k$ for some $n$. We will prove this by inducting down. The base case is trivial; by definition, $M$ is achievable. For the inductive hypothesis suppose that some $M' \in S$ is achievable by some $n$. We wish to show that for all primes $p \mid M'$, we can find $n$ that achieves $\frac{M'}{p}$. First, write down $\gcd(an + b, cn + d) = M'$ and pick some prime $p \mid M'$ that we are looking to divide by. Clearly $p \nmid \gcd(a, c)$ or else $p \mid b, d$ contradicting $\gcd(a, b, c, d) = 1$. Let $v_p(M') = e$. Consider $n'$ such that\[n' \equiv n + p^{e - 1} \pmod{p^e}\]\[n' \equiv n \pmod Q\]where $Q$ is some super large prime power of a prime dividing $M$. We check that indeed $v_p(\gcd(an' + b, cn' + d)) = e-1$ and that due to $n' \equiv n \pmod Q$ the exponents of the other primes do not change, completing our inductive step. Hence all factors of $M$ are achievable by $k$ for some value $n$, as desired. $\blacksquare$ Blargh

Note that $ad-bc = -c(an+b)+a(cn+d)$ is a linear combination of $an+b$ and $cn+d$ hence the $\gcd$ divides it. Thus $S$ has a maximum. Now consider a prime $p$, and let $e_p$ be the maximum value of $\nu_p(an+b, cn+d)$. First we show that if there is $n$ where $k = \nu_p(\gcd(an+b, cn+d))$, then we can get $k-1$ as well. WLOG $\nu_p(a) \ge \nu_p(c)$. Then by taking $n' = n+\frac{p^{k-1}}{\gcd(c, p)}$ we end up with $\nu_p(cn'+d) = \nu_p(cn+d+\frac{cp^{k-1}}{\gcd(c, p)}) = k-1$ because $cn+d$ is a $k$th power of $p$ and $\nu_p(\frac{cp^{k-1}}{\gcd(c, p)}) = k-1$. Additionally $\nu_p(an'+b) = \nu_p(an+b+\frac{ap^{k-1}}{\gcd(c, p)}) \ge k-1$ because $\nu_p(a) \ge \nu_p(c)$ (hence $\nu_p(\frac{ap^{k-1}}{\gcd(c, p)}) \ge k-1$). Thus $\nu_p(\gcd(an'+b, cn'+d)) = k-1$. Using this iteratively says that all $0 \le k \le e_p$ are reachable. Finally we want to combine prime powers together. We need only show that the sequence $\nu_p(an+b, cn+d)$ is periodic (and that the period is different for each $p$), because we can then use CRT to finish. Note that $\nu_p(\gcd(an+b, cn+d)) = \nu_p(\gcd(a(n+p^{e_p})+b, c(n+p^{e_p})+d))$ so the periodicity is evident (and the periods are relatively prime so no issue there). Thus $S$ contains the divisors of $2^{e_2}3^{e_3}\cdots$. $\blacksquare$

I'm not sure if this works. Let $M=\frac{|bc-ad|}{\gcd(a,c)}$. I claim that $S$ is the set of divisors of $M$. Firstly, note that \[\gcd(an+b,cn+d)\mid \frac{c}{\gcd(a,c)}(an+b)-\frac{a}{\gcd(a,c)}(cn+d) = \frac{bc-ad}{\gcd(a,c)}\]Thus, all $x_n=\gcd(an+b,cn+d)$ satisfy $x_n\mid M$. We will only consider $0\leq n \leq M-1$. Claim 1: I claim that for prime powers $q\mid M$, there are exactly $\frac{M}{q}$ solutions to $q\mid x_n$. Firstly, note that there exists some smallest solution $n_1 \pmod{q}$ to \[an+b\equiv 0 \pmod{q}\]because $\gcd(a,q)\mid \gcd(a,M)=1$. Next, note that \[\frac{c}{\gcd(a,c)}(an+b)\equiv \frac{a}{\gcd(a,c)}(cn+d) \pmod{q}\]Thus, if $an+b\equiv 0$, then we also have $cn_d\equiv 0$. Thus $n_1$ is the only residue mod $q$ that can work, and it does work. Then,we can take $n_1+kq$ which will also work, so there are exactly $\frac{M}{q}$ solutions and we are done. Using this claim, for any $k\leq v_p(M)$, we can always find some $n$ such that $v_p(x_n)=k$. This $x_n$ is determined by $\pmod{p^k}$. Thus, for any $d\mid M$, by CRT we can construct a $n$ such that for all $p^k=q\mid d$, we have that $v_p(x_n)=v_p(d)$. Thus, this clearly shows that all divisors of $M$ appear and we are done.

double posted oops. it was the exact same as my previous post (#20)

AwesomeYRY wrote: Let $M=\frac{|bc-ad|}{\gcd(a,c)}$. I claim that $S$ is the set of divisors of $M$. Correct value is actually $M = \frac{|ad-bc|}{\gcd(ad-bc, a^\infty, c^\infty)}$, I believe.

Another setup problem.

Quite a cool rigid problem and a problem where one can predict the structure of the final proof.

Any suggestions on writeup improvements (or possible flaws) in this proof are greatly appreciated! First we will show that if for some $p$, if $p^k$ can be attained, then all powers of $p$ less than $p^k$ can be attained. Case 1. $\gcd(a, p) = 1$ and $\gcd(c, p) = 1$. Then the set of all $n$ such that $p^k$ divides $an+b$ is $i \pmod {p^k}$ for some positive integer $i$, and for $cn+d$ we can define $j \pmod {p^k}$ similarly. There will only exist $n$ such that the gcd is a multiple of $p^k$ if and only if $i=j$. However, this implies that the ``cycles" of $an+b$ and $cn+d$ coincide. In fact $i \equiv j \pmod {p^r}$ for $r \leq k$ must also be true, and since the cycle lengths of $an+b$ and $cn+d$ cycle every $p^r$, they will always coincide after this $i, j$ for all $r \leq k$ as required. Case 2. $\gcd(a, p) \neq 1$. This implies $p \mid a$. If $p \nmid b$, then none of $an+b$ for any $n$ will be a multiple of $p$. If $p \mid b$, then all $an+b$ will be a multiple of $p$. Thus we can reduce this to $$\frac bp + \frac{an}p.$$If $\frac bp$ and $\frac ap$ are still both multiples of $p$, repeat. If only $p \mid a$, then there are no more factors of $p$. Otherwise, we can move to case 1. (Notice that under these circumstances, we force $\gcd(c, p) = 1$; because $p$ cannot divide all four of $a, b, c, d$. This means that we can always attain the $\nu_p(an+b) = 1, 2, 3, \cdots$ in case 1 in the $cn+d$ side, and thus smaller values of $p^r$ are attainable.) Next we will show that for relatively prime $m, n$ that are relatively prime, if $x$ and $y$ are elements of $\mathcal S$, then so is $xy$. This is because if the ``cycle" of remainders mod $x$ line up, and the ``cycle" of remainders mod $y$ lines up, then the necessary and sufficient conditions of both are $$n \equiv i \pmod x, n \equiv j \pmod y$$for some $i, j$. Then we can find a unique $n \pmod {xy}$ -- in this case, the GCD will equal $xy$ as required. Note that the converse also holds; we can ``reduce" the condition in the following sense: if for some $x, y$ relatively prime, $xy$ is an element of $\mathcal S$, then there exists some $n$ such that the GCD is $xy$, and the cycles of $an+b, cn+d$ line up mod $x$ and $y$. Therefore, in between the $xy$ terms, we can always find an $n$ such that the GCD is equal to exactly $x$ or exactly $y$. Next we will show that the set of gcd's is indeed bounded. We will show that for large enough $N$, $N$ cannot be a possible gcd. Notice that if $N$ is a valid gcd, then there exist $k_1, k_2$ such that \begin{align*} an+b &= k_1N \\ cn+d &= k_2N. \end{align*}Equating for $n$ yields $$\frac{k_1N-b}a = \frac{k_2N-d}c \iff N(ck_1-ak_2) = bc-ad.$$The RHS must be a multiple of $N$, but since $bc-ad \neq 0$ and $N$ is sufficiently large, contradiction! Thus proven.

First note that $gcd(an+b;cn+d)|c(an+b)-a(cn+d)=bc-ad$,so the gcd is bounded. By the Euclidean algorithm we know that for positive integers $x\geq y$ we have $gcd(x;y)=gcd(y;x-y)$, so after applying this enough times (when $xn+y\geq zn+t$ if $x\geq z$) we are going to reach a place in which (WLOG $a\geq c$) $$gcd(an+b;cn+d)=gcd(cn+d;(a-c)n + b-d)=\cdots = gcd(xn+y;a)$$for some integers $x;y$ and $a$. Here we have $x>1$ and $a\neq 0$ since we already got that the gcd's are bounded. We have $gcd(x,y,a)=1$ since otherwise after going back the steps we are going to get that $gcd(a,b,c,d)>1$, which isn't true. Now let $t$ be the largest divisor of $a$ such that $gcd(t,x)=1$. If $q$ is a prime such that $q|gcd(a,x)$, then $q$ doesn't divide $y$ thus it doesn't divide $gcd(xn+y;a)$. So we always have that $gcd(xn+y;a)|t$. Also since $xn$, and thus $xn+y$, goes trough all residues $(mod t)$ when $n$ varies we get that $gcd(xn+y,a)$ can take all the divisors $mod$ $t$ when $n$ varies and we're done!

v_Enhance wrote: Claim: Suppose $k_1, k_2 \in S$. Then $\operatorname{lcm}(k_1, k_2) \in S$. Proof. By the previous claim it suffices to show some multiple of $\operatorname{lcm}(k_1, k_2)$ is in $S$. If $k_1 = \gcd(an_1+b, cn_1+d)$ and $k_2 = \gcd(an_2+b, cn_2+d)$. We choose $n$ such that: for each prime $p \mid ad-bc$, if $q = p^{\nu_p(bc-ad)}$ then \[ n \equiv \begin{cases} n_1 \pmod q & \nu_p(k_1) \ge \nu_p(k_2)\\ n_2 \pmod q & \text{otherwise}. \end{cases} \]Then $\nu_p(\gcd(an+b, cn+d)) \ge \max(\nu_p(k_1), \nu_p(k_2))$ for each $p$ as desired. $\blacksquare$ Here's a different (brute force) way to prove the Claim (though, the above proof seems nicer); By previous Claim, it suffices to show $k_1,k_2 \mid f(n)$ for some $n \in \mathbb N$. With $m = \gcd(a,c)$, it is enough to have $$k_1 \mid m(n - n_1) ~~,~~ k_2 \mid m(n-n_2)$$Let $p_1 = k_1 \div \gcd(k_1,m)$ and $p_2 = k_2 \div \gcd(k_2,m)$. We want $$p_1 \mid n - n_1 ~~,~~ p_2 \mid n - n_2$$Which is further equivalent to $$\gcd(p_1,p_2) \mid n_1 - n_2$$Let $l = \gcd(p_1,p_2)$. Then $$l \mid an_1 + b , cn_1 + d,an_2 + b,cn_2 + d$$Which gives $$l \mid a(n_1 - n_2), c(n_1 - n_2) \implies l \mid m(n_1 - n_2)$$As $\gcd(m,p_1) = \gcd(m,p_2) = 1$ (just by definition of $p_1,p_2$), so $\gcd(l,k) = 1$. Thus $l \mid n_1 - n_2$, as desired.

Claim: $|S|$ is bounded Proof: $$(an+b,cn+d) \leq gcd(an+b,anc+ad)$$$$=gcd(an+b, anc+ad-anc-bc)$$$$=gcd(an+b,ad-bc)$$ This means that all the terms in $S$ must divide $ad-bc$ Therefore, the size of $S$ is clearly bounded Subclaim:If $x$ is in $S$, all the factors of $x$ are also in $S$ Proof: Suppose some prime $p$ divides $x$ and $V_p(x)=k$, set a new number $x'$ such that $$x' \equiv p^{k-1} (\mod p^k)$$$$x' \equiv x ( \mod j^{V_j(ab-cd)})$$ for all prime $j$ dividing $ab-cd$ , where $j$ and $p$ are distinct Now, observe that by CRT, such an $x'$ must exist Claim: If $x_1$ and $x_2$ are in $S$, then $LCM(x_1,x_2)$ is in $S$ Proof: Let $x_1=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$ $x_2=p_1^{b_1}p_2^{b_2}...p_n^{b_n}$ For some prime $p_i$, if $a_i>b_i$ take $k$ such that $$k \equiv x_1(\mod p_i^{a_i})$$ Similarly, do this for all the $i$ By CRT, we can construct such a $k$ Observer that $LCM (x_1,x_2) |k$ Which means that there must exist some multiple of $LCM(x_1,x_2)$ in $S$ But using our subclaim, we know that all the factors of the multiple of the $LCM(x_1,x_2)$ are in $S$, this includes $LCM(x_1,x_2)$. Therefore, our claim is true . Claim: All the terms in $S$ are exactly all the divisors of $\max {S}$ Proof: By our first claim , we know that a maximum number exists in $S$ Let the largest term in $S$ be $m$ By our claim 2, the $LCM$ of $m$ and any other term in $S$ must exist within $S$. But note that the $LCM \geq m$, but by definition we know that there cannot exist a term larger than $m$ within $S$ Therefore, all the $LCM$ including $m$ must exactly be $m$. Hence, every other term in $S$ must be a factor of $m$. Combining this together with our earlier subclaim, we can conclude that all the terms in $S$ are exactly all the divisors of $m$

(Just a sketch) By the euclidean algorithm we have \[ \gcd(an+b,cn+d) = \gcd(an+b,(a-b)n+(c-d) = \cdots = \gcd(\ell(n),M) \]For some linear function $\ell$ and a positive integer $M$. Notice that this implies $S$ is bounded since any element in $S$ must divide $M$. Now, assume that $\gcd(\ell(n),M)$ obtains maximum value an an integer with prime factorization $p_1^{\alpha_1} \cdots p_k^{\alpha_k}$. By CRT we can choose $\ell$ so that $\nu_{p_i}(\ell(n)) = \beta_i$ for any sequence of non-negative integers $\beta_1,\beta_2, \ldots, \beta_k$ obeying $\beta_i \leq \alpha_i$. Notice that these are also the only possible values that $\gcd(\ell(n),M)$ by maximality. So, $S$ is exactly the set of divisors of $p_1^{\alpha_1} \cdots p_k^{\alpha_k}$. $\blacksquare$

Different solution, I think?

no latex sol Note that gcd(an+b,cn+d)|c(an+b)-a(cn+d)=bc-ad, so S is bounded; by suitably using euclidean algorithm we can get a linear gcd(an+b,cn+d)=gcd(cn+d,(a-c)n + b-d)=...=gcd(mn+x,y), with $y\ne 0$, and if m=0, we're done since there's only one number, while if m=1, this runs over all divisors of a, so henceforth assume m>1, and assume gcd(m,x,y)=1 (otherwise divide by this suitably since it's always there). Taking l as the largest divisor of y with gcd(m,l)=1, and a prime power p|gcd(m,y), p doesn't divide gcd(mn+x,y) implies gcd(mn+x,y)|l|y (since any other prime power factors of y are relatively prime to the gcd); since m is relatively prime to l, varying n goes over all residues mod l, so the set S goes over all divisors of l!

Note that $\gcd(an + b, cn + d) \mid c(an + b) - a(cn + d) = bc - ad$, so $S$ is finite. Let $M$ be maximum element in $S$, and let $M = p_1^{\alpha_1}p_2^{\alpha_2} \dots p_k^{\alpha_k}$. Fix arbitrary $0 \le \beta_{i} \le \alpha_{i}$ and we'll prove that there exists $n$ such that $\nu_{p_i}(\gcd(an + b, cn + d)) = \beta_i$ for all $i$. Since $\gcd(a, b, c, d) = 1$, so WLOG we can assume $\nu_{p_i}(a) = 0$ or $\nu_{p_i}(b) = 0$. If $\nu_{p_i}(b) = 0$ and $\nu_{p_i}(a) > 0$, then $\nu_{p_i}(an + b) = 0$, so $\nu_{p_i}(M) = 0$, a contradiction. Thus we can assume $\nu_{p_i}(a) = 0$. Now taking $n \equiv \frac{p_i^{\beta_i} - b}{a} (p_i^{\beta_i})$ by CRT, we have $an + b \equiv p_i^{\beta_i} (p_i^{\beta_i + 1})$ for all $i$ and it's not hard to see that $p_i^{\beta_i} \mid cn + d$. So $\gcd(an + b, cn + d) = p_1^{\beta_1}p_2^{\beta_2} \dots p_k^{\beta_k}$. $\blacksquare$

We operate on the matrix $M_0 = \begin{bmatrix} a & c \\ b & d \end{bmatrix}$ using the transforms \[ T_1 = \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix} \]\[ T_2 = \begin{bmatrix} 1 & 1 \\ -1 & 0 \end{bmatrix} \]\[ T_3 = \begin{bmatrix} 1 & 1 \\ 0 & -1 \end{bmatrix} \]\[ T_4 = \begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} \]all of which have determinant $\pm 1$. Thus, upon application of these transforms, $|ad-bc|$ is invariant. Moreover, $\gcd(an+b,cn+d)$ is also preserved for fixed $n$ by the Euclidean algorithm, so $S$ is preserved as well. Apply these transformations to bring $a$ to $0$ by following the Euclidean algorithm. Then it suffices to prove the result when $a=0$. We need to show that if $\gcd(b, c, d)=1$ for integers $b$, $c$, and $d$ with $bc \neq d$, then the set of all possible values of $\gcd(b, cn+d)$ over all positive integers $n$ is the set of positive integer divisors of some positive integer. WLOG $\gcd(c, d)=1$ by scaling. By Bezout's identity, it is easy to see that $S$ is a subset of the divisors of \[ m := \frac{b}{\gcd(b, c^{\infty})}. \]By CRT, it can be shown that all divisors of $m$ can be constructed, and we conclude.

not sure if this works.. but if it does its a cool sol Strong induct on $\max (a,c)$. The base of $a = c = 1$ is obviously true. For the inductive hypothesis, WLOG let $a \geq c$, consider $\gcd(an + b, cn + d) = \gcd(cn + d, (a -c)n + (b - d)) $. We divide into two cases. Case 1: $a = c$. Then we get the desired expression as $\gcd(cn + d, b - d)$. For all primes $p$, we show that the set of $\nu_p(\gcd(cn +d, b-d))$ is of the form $0 \cdots x_p$, and then use CRT to conclude the expression ranges over all divisors of some number $\prod p^{x_p}$. Consider any prime $p$ dividing $b - d$, then we consider $\nu_p(b - d), \nu_p(d), \nu_p(c)$. Observe that $\gcd(b,c,d) = 1$, so if both $c,d$ divide some prime, then $b$ cannot and thus it cannot be part of the $gcd$ since it won't divide $b - d$. Otherwise, if $c$ doesn't divide the prime, we can also have $\nu_p(cn + d)$ as unbounded, so $\nu_p(\gcd(cn + d, b - d))$ can range anywhere from $0$ to $\nu_p(b-d)$. If $c$ does divide the prime, then $d$ can't and we are actually forced that $\nu_p(cn + d) = 0$. Case 2: $a \neq c$. Then it remains to show that we can apply the inductive hypothesis on $\gcd(cn + d, (a -c)n + (b - d)) $. To do this, we must show $c(b - d) \neq d(a - c)$, which is trivial since it reduces to $ad \neq bc$, and we must show $\gcd (c, d, a - c, b - d) = 1$, which is also trivial since $\gcd(c,d, a- c, b -d ) = \gcd(\gcd(c , a - c), \gcd (d, b -d)) = \gcd(\gcd(a,c) , \gcd(b, d)) = \gcd(a,b,c,d) =1$.

RMM 2018 Nice problem, Here is a sketch: Firstly we have that. $$gcd(an+b,bn+c)| bc-ad$$Hence we get that $S$ is finite, now we show all divisors are in $S$. Let $N=p_1^{a_1} \dots p_k^{a_k}$, be the maximal element of $S$. Then we show that $\nu_{p_i}(\gcd(an + b, cn + d)) = a_i$. We can see that $\nu_{p_i}(a)$ and $\nu_{p_i}(b)$ both equal $0$ then this implies that both $\nu_{p_i}(d)$ and $\nu_{p_i}(c)$ more than $0$. We give the construction $$n = \frac{p_i^{a_i} - b}{a} (p_i^{a_i})$$hence all divisors are in $S$

Let $a=gr,c=gs$ where $\gcd(r,s)=1$. Then, perform Euclidean algorithm on the matrix $$\begin{bmatrix} gr & b\\ gs & d \end{bmatrix}$$to get $$\begin{bmatrix} g & u\\ 0 & v \end{bmatrix}.$$Thus $\gcd(grn+b,gsn+d)=\gcd(gn+u,v)$. Note that $\gcd(u,v)=\gcd(b,d)$ as well. Since the determinant of the matrix didn't change, $gv=ad-bc$, so $v\neq 0$ as $ad-bc\neq 0$. Clearly, the gcd divides $v$. Consider any maximal prime power $p^k\mid v$ for $k\geq 1$. If $p\nmid g$, then $gn+u$ will cycle through all residues mod $p^k$, so the exponent of $p$ in $gn+u$ will hit every possible value from $0$ up to $k$. Call this a Category 1 prime. If $p\mid g$, then we claim that $p\nmid u$. Suppose FTOSC that $p\mid u$ as well. Then, $p$ would divide both $u$ and $v$, but because $\gcd(b,d)=\gcd(u,v)$, $p$ would divide both $b$ and $d$ as well. Since $p$ already divides both $a$ and $c$, this contradicts $\gcd(a,b,c,d)=1$. Thus, in this situation, as $p\mid g$ but $p\nmid u$, $gn+u$ is never divisible by $p$ at all. Call this a Category 2 prime. By Chinese Remainder Theorem, this means that the possible values of $\gcd(gn+u,v)$ are exactly divisors of $v$ that consist of only Category 1 prime divisors, as we know any prime exponent up to the maximum is possible, and by CRT we can select any combination of them.