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)


Sorry everyone, I have just figured out the proof: It is because the sequence I write didn't have sufficiently much terms to make me realize the question's statement can be true.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.