×

# Divisibility Chains Generalization

Based on this problem.

Define two positive integer sequences $$\{a_n\}$$ and $$\{b_n\}$$ be defined as $$a_1\ne b_1$$, $$a_{n+1}=a_n+k$$ and $$b_{n+1}=b_n+k$$. These two sequences form an Order $$k$$ Divisibility Chain of length $$n$$ if $$a_i\mid b_i$$ for $$i=1\to n$$.

Prove that no matter what $$n$$ and $$k$$ you choose, there always exists an infinite number of sequences $$\{a_n\}$$ and $$\{b_n\}$$ that form an Order $$k$$ Divisibility Chain of length $$n$$.

Please only post hints, do not post the solution. If you do, it will give away the solution for the problem I based this on. Thanks.

Note by Daniel Liu
2 years, 10 months ago

Sort by:

Take $$a_1=k, b_1=k+k\times n!$$. This gives an example of a single such sequence for any n,k. Should not be hard to generalize this to produce infinitely many such sequences, · 2 years, 10 months ago

Hint: Consider the sequence in modulo $$lcm(a_1,a_2,...,a_n)$$. From there rest will be pretty easy.

@Daniel Liu : Am I being too obvious? · 2 years, 10 months ago

No, you're not being too obvious as far as I can tell.

Now to think about it, I should have posted this problem for the Proofathon Sequences and Series competition. Dang! · 2 years, 10 months ago

Hint: $$a_1 = b_1$$

(Which, by the way, is why I reported the problem.) · 2 years, 10 months ago

I can't believe I didn't realize that any $$a_1=b_1$$ works. Edited the problem and this note to show that $$a_1\ne b_1$$. · 2 years, 10 months ago