3
$\begingroup$

Suppose we are considering the residue class of all numbers $\equiv a \pmod b$, where $(a,b)=1$. Is there an elementary (and relatively simple) way to see that there is a subsequence that consists entirely of elements that are mutually coprime?

Of course, this must be a true statement, as it follows immediately by Dirichlet's Theorem. But this statement is a bit weaker, so is there perhaps a way to construct a sequence of mutually coprime integers all in the same residue class? I was thinking something like a Fermat construction (i.e. $F_n=1+\prod_1^{n-1}F_i $) would work, but I cannot see how to see this method through. Anyway, there might not even be an elementary solution, and I may be approaching my original problem in the wrong way.

$\endgroup$
  • 1
    $\begingroup$ Wouldn't $a + b^k $ be such a sequence? $\endgroup$ – fleablood Feb 10 '17 at 6:28
  • 1
    $\begingroup$ @fleablood Are all numbers of the form $1+2^k$ mutually coprime? Nope. $\endgroup$ – Erick Wong Feb 10 '17 at 6:38
2
$\begingroup$

Let $u_1=a$, $u_2=b+a$, $v_k=u_2\times u_3\times\cdots\times u_k$ for $k=2,3,\dots$, $u_{k+1}=bv_k+a$ for $k=2,3,4,\dots$.

E.g., for $a=2$, $b=5$, we get $u_1=2$, $u_2=7$, $u_3=5\times7+2=37$, $u_4=5\times7\times37+2=1297$, $u_5=5\times7\times37\times1297+2$, and so on.

$\endgroup$

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.