# A not very obvious question about $\{h+tk\}$ sequence.

Let $$h$$ and $$k$$ be positive integers such that $$\gcd(h,k)=1$$. Let $$A(h,k)$$ be the sequence $$A(h,k)=\{h+kx|x=0,1,2,3,\cdots\}.$$ Let $$S$$ be a infinite subset of $$A(h,k)$$, prove that for each positive integer $$n$$, there is an integer in $$A(h,k)$$ that can be written as a product of more than $$n$$ different numbers from $$S$$.

I cannot have any insight for this question, so I use an example, $$h=2,k=3$$, then the sequence is $$2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,47,50,53,56,59,62,\cdots$$ Since numbers in $$S$$ are also in $$A(h,k)$$, I try to find a number in $$A(h,k)$$ that is the product of other numbers in $$A(h,k)$$ but I failed. How can we solve this problem?

Source: Apostol Analytic Number Theory (Chapter 7)

For any number $$y\in A(h,k)$$, we always have $$y\equiv h\pmod k.$$
By Fermat little theorem, raising up to $$\phi(k)$$ power we have $$y^{\phi(k)}\equiv 1\pmod k$$
Or more generally, raising up to $$m\phi(k)$$ power for any positive integer $$m$$ we have $$y^{m\phi(k)}\equiv 1\pmod k\implies y^{m\phi(k)+1}\equiv y\equiv h\pmod k$$ So for each positive integer $$n$$, let $$m$$ be a positive integer such that $$m\phi(k)+1>n$$, then we can choose $$m\phi(k)+1$$ different numbers from $$S$$, multiply them together, then the product write it as $$N$$, we have $$N\equiv y^{m\phi(k)+1}\equiv h\pmod k$$ Therefore there is positive integer $$t$$ such that $$N=h+tk\in A(h,k)$$ which completes the proof.