Does anyone know how to solve this challenging problem? Thank you very much!

Yes, here's a solution. This is pretty intuitive I feel. Let $g = \gcd(a, b)$, and say $g = \prod_{i = 1}^m p_i^{e_i}$, where $m \ge 2, e_i > 0$ for all $i$. Let $a = ga', b = gb'$. Now we deal with a few cases: Case 1: $\gcd(b', g) > 1$. Proof:This is the easy case in fact. Let $p_i | b'$ and $p_i | g$. Since $\gcd(a', b') = 1$, $p_i \not| a$. Therefore, for any $x$, $v_{p_i} (bx+a) = v_{p_i} (g) + v_{p_i}(b'x+a') = v_{p_i} (g)$. In particular, since $g$ divides all elements of $S$, if $bx+a$ is not irreducible, then $g^2 | bx+a$, contradicting the fact that $v_{p_i} (bx+a) = v_{p_i} (g)$. Case 2: $\gcd(p_i, b') = 1$. Proof: This case is slightly trickier. Call a residue $ x \pmod{b'}$ for $\gcd(x, b') = 1$ good if there exist exponents $f_i > v_{p_i} (g)$ such that $x \cdot \prod_{i = 1}^m p_i^{f_i} \equiv a \pmod{b}$. Let $X$ be the set of residues $\pmod{b}$ that $\prod_{i = 1}^m p_i^{f_i}$ can achieve over all large exponents $f_i$. It is clear that $X$ is closed under multiplication, i.e. $X \cdot X = X$. For a good integer $x$, let $f(x)$ be the smallest integer of the form $\prod_{i = 1}^m p_i^{y_i}$ such that $x \cdot f(x) \equiv a \pmod{b}$. ($f_i > v_{p_i} (g)$ above) Of course by Euler's Theorem we can assume that $f_i \le \phi(b') + v_{p_i}(g)$. Also, $a^{\phi(b')+1} = a \pmod{b}$ clearly. Now set $t = 100 \cdot \phi(b') \cdot (\phi(b') + \sum v_{p_i}(g) )$. (In other words, something pretty large) Now let $bx+a = k \cdot \prod_{i=1}^m p_i^{f_i}$ where $\gcd(k, p_i) = 1$ for all $i$. By definition $k$ is good. So say that $k \cdot \prod_{i = 1}^m p_i^{j_i} \equiv a \pmod{b}$ where $v_{p_i}(g) \le j_i < \phi(b') + v_{p_i}(g)$. If $f_i < t$, then clearly it can be reduced into at most $t$ irreducible elements of $S$, since $g$ divides all things in $S$. So assume that $f_i \ge t$ for all $i$. If we can't write $k$ as the product of at least $\phi(b')+1$ good integers, then $bx+a$ must be irreducible clearly. (Since all good parts of the things that would multiply to $bx+a$ multiply to $k$) So write $k = k_1k_2k_3 \dots k_n$ where $k_1, k_2, \dots, k_n$ are all good, $n > 1$. I will show that there exists a constant $C$ such that we can always choose $n < C$. Assume that $n > \phi(b') + 1 = n'$. hen there are integers $x_1, x_2, \dots, x_{n'}$ such that $x_i \cdot k_i \equiv a \pmod{b}$. But then multiplying all these, you get $\prod_{i = 1}^{n'} x_i \cdot (k_1k_2 \dots k_{n'}) \equiv a^{\phi(b')+1} \equiv a \pmod{b}$. Since $\prod_{i = 1}^{n'} x_i \in X$, $(k_1k_2 \dots k_{n'})$ is good. So we can reduce $n$. So the $C$ exists. Now write it in the way such that $n > 1$ but minimal. Now write \[ bx+a = \left( k_{n-1} \cdot p_i^{d \cdot \phi(b')} \cdot f(k_{n-1}) \right) \cdot r \cdot \prod_{i = 1}^{n-2} \left( k_i \cdot f(k_i) \right) \] where $d$ in the first term is chosen so that $v_{p_1} (r) > v_{p_1} (g)$ but $r$ is as small as possible (so $r < \phi(b') + v_{p_1}(g)$ in particular). $r \equiv a \pmod{b}$ because of how $k = k_1k_2 \dots k_n$. Since $g$ divides all elements of $S$, let's see how much further we can reduce each guy in the above expression. Each of the $n-2$ terms in the product can be reduced into at most $\phi(b') + \max{ v_{p_i}(g) }$ terms because the exponents of primes are small. $r$ has a small $v_{p_1} (r)$, so it can reduced into at most $\phi(b') + v_{p_1} (g)$ more terms. The term with $k_{n-1}$ can be reduced also into at most $\phi(b') + \max{ v_{p_i}(g) }$ because the exponent of $p_2$ is small. In all, everything is finite.

Mathocean97, what is the motivation for amazing solution? Thank you very much and congratulations on solving this problem!

My solution is significantly simpler than mathocean97's. Can anyone check whether I screwed up? (Note that $p,q,r$ always denote primes.) Let $g=\gcd(a,b)$, $a=ga'$ and $b=gb'$. If $\gcd(b',g) > 1$ then let $p\mid b'$, $p\mid g$. Then $p\nmid a'$ so $\nu_p(a) = \nu_p(g) < \nu_p(b)$. Thus any $x\in S$ have $\nu_p(x) = \nu_p(a)$ so $x$ is always irreducible. Hence this case is trivial. Otherwise, $\gcd(b',g)=1$. Let $p,q$ be two prime divisors of $g$ and let $x\in S$. If $x$ is already irreducible, we are done. Otherwise, write $x=uv$ for some $u,v\in S$. The key idea is we will use transformation $(u,v)$ to another pair $\left(p^{\varphi(b')}u, \tfrac{v}{p^{\varphi(b')}}\right)$ of $S$ whenever $\nu_p(v) > \varphi(b')+\nu_p(g)$. To see why this works, note that it will not change residue $\pmod{b'}$. Moreover, it makes exponent of any prime factor $r$ of $g$ greater than $\nu_r(g)$ so it will not change remainder $\pmod{b}$. Hence this transformation is valid. So we can perform this operation until $\nu_p(v) \leqslant\varphi(b') + \nu_p(g)$. Similarly, using another prime $q$, we can perform an analogous operation until $\nu_q(u)\leqslant\varphi(b') + \nu_q(g)$. Since any further decomposition of $u,v$ require each factor to divides $p^{\nu_p(g)}$ and $q^{\nu_q(g)}$. This makes $uv$ can be expressed to at most $$\frac{(\varphi(b') + \nu_p(g))}{\nu_p(g)} + \frac{(\varphi(b') + \nu_q(g))}{\nu_q(g)}$$factors, which is finite so we are done.

What's wrong with the following? Must be wrong somewhere, but I can't find it. Take $a=6,b=30$ and note that the product of any number of elements of $S$ must still be in $S$ because it must still be congruent to 6 modulo 30. Thus there are elements of S that can be expressed as the product of arbitrarily large number of elements S, thus the problem statement is false??!

There will be multiple ways to write an element of $S$ as a product of irreducible elements and so having products of arbitrary many irreducible elements need not lead to a contradiction. You can view this phenomena as some sort of failure of unique factorization happening in $a$ $(\text{mod }b)$.

Thanks for pointing out

Let $d=\gcd (a,b)$ and $a=dp,b=dq$. Note that $\gcd (p,q)=1$. Let $r$ and $s$ be two distinct primes that divide $d$; let $d=r^us^vd_0$ where $\gcd (d_0,rs)=1$ and $u,v\in \mathbb{Z}^+$. First we investigate when does $d(p+nq)$ reducible, i.e., when does there exists $a_1,a_2,\dotsc ,a_{\ell }\in \mathbb{Z}^+,\ell >1$ that $$d(p+nq)=\prod_{i=1}^{\ell}{ \left( d(p+a_iq)\right) }\implies p+nq=d^{\ell -1}\prod_{i=1}^{\ell}{ (p+a_iq) }$$where $d(p+a_iq)$ are irreducible for all $i$. Clearly, we must have $d^{\ell -1}\mid p+nq$ (this will subsequently be a crucial part). Also, modulo $q$ gives us $p\equiv d^{\ell -1}p^{\ell}\pmod{q}\implies \gcd (q,d)=1$. Now, say we have a reducible $d(p+nq)\in S$ that can be factor as $$d(p+nq)=\prod_{i=1}^{N}{\left( d(p+a_iq)\right) }$$where $d(p+a_iq)$ are irreducible for all $i$ and when $N>2q$. By our choices of $N$, there exist $w\geqslant 2$ and $0\leqslant z<q-1$ that $N-2=w(q-1)+z$. For each $i$, let $u_i=\nu_r(p+a_iq)$ and $v_i=\nu_s (p+a_iq)$. For $1\leqslant x\leqslant y\leqslant N$, define $U_{x,y}=\sum_{i=x}^{y}{u_i}$ and $V_{x,y}=\sum_{i=x}^{y}{v_i}$. Also, for any integer $k$, let $\overline{k}$ be the unique integer that $\overline{k}\in \{ 1,2,\dotsc ,q-1\}$ and $k\equiv \overline{k} \pmod{q-1}$. We now have the following \begin{align*} & \prod_{i=1}^{w(q-1)+2}{\left( d(p+a_iq)\right) } \\ & = d^{w(q-1)+2}r^{U_{1,w(q-1)+2}}s^{V_{1,w(q-1)+2}}\prod_{i=1}^{w(q-1)+2}{\frac{p+a_iq}{r^{u_i}s^{v_i}}}\\ & = \underbrace{d^{w(q-1)} r^{U_{1,w(q-1)+2}-\overline{U_{1,(w-1)(q-1)+1}} - \overline{U_{(w-1)(q-1)+2,w(q-1)+2}}} s^{V_{1,w(q-1)+2}-\overline{V_{1,(w-1)(q-1)+1}} - \overline{V_{(w-1)(q-1)+2,w(q-1)+2}}} }_{T_0}\\ & \times \underbrace{ \left( dr^{\overline{U_{1,(w-1)(q-1)+1}}}s^{\overline{V_{1,(w-1)(q-1)+1}}}\prod_{k=1}^{(w-1)(q-1)+1}{ \frac{p+a_iq}{r^{u_i}s^{v_i}}} \right) }_{T_1} \\ & \times \underbrace{ \left( dr^{\overline{U_{(w-1)(q-1)+2,w(q-1)+2}}}s^{\overline{V_{(w-1)(q-1)+2,w(q-1)+2}}}\prod_{k=(w-1)(q-1)+2}^{w(q-1)+2}{ \frac{p+a_iq}{r^{u_i}s^{v_i}}} \right) }_{T_2} \end{align*}Note that for $j\in \{ 1,2\}$, $T_j/d \equiv p\pmod{q}\implies T_j\in S.$ Moreover, $\nu_r (T_j/d)\leqslant q-1$ and $\nu_s (T_j/d)\leqslant q-1$. Both inequalities (independently) imply that $T_j$ can be factored into at most $M:=\max \left\{ 1+\frac{q-1}{u},1+\frac{q-1}{v}\right\}$ irreducible terms (using the crucial part I noted at the beginning). Now we'll deal with $T_0$. Easy to see that $\nu_r (T_0),\nu_s (T_0) \geqslant 0$ and $\nu_r (T_0),\nu_s (T_0)\equiv 0\pmod{q-1}$. So, we multiply all the power of $r$ and also $d_0^{w(q-1)}$ to $T_1$ and multiply all the power of $s$ to $T_2$. We get that $T_1/d,T_2/d$ remain constant modulo $q$ and also maintain $\nu_s (T_1/d),\nu_r (T_2/d)\leqslant q-1$. Thus, so far we've proved that we can factor $\prod_{i=1}^{w(q-1)+2}{\left( d(p+a_iq)\right) } $ into at most $2M$ irreducible terms. We simply add the remaining $z$ terms and conclude that we can factor $d(p+nq)$ into at most $q-1+2M$ terms. Hence, for any $d(p+nq)\in S$ that can be factored into $N>2q$ terms, there exists factorisation that use only $q-1+2M$ terms. So, $t=\max \{ 2q,q-1+2M\}$ work and we are done. $\quad \blacksquare$

Note that if there is no N>1 such that a^N=a hence all is irredicible thus t=1. Hence exist such smallest N, now consider bk+a=(bk1+a)...(bkM+a) with M>N. Notice (bk1+a)..(bkN+a)=bs+a in S too, this expression reduce N irreducible elements. Repeatedly, bk+a expression have at most N-1 irreducible factors, which is finite, thus conclusion

Posting for storage.