MathDB
Least common multiple of steps of these progressions

Source: IMO Shortlist 2010, Combinatorics 7

July 17, 2011
number theorymodular arithmeticcombinatoricsarithmetic sequenceIMO ShortlistSequence

Problem Statement

Let P1,…,PsP_1, \ldots , P_s be arithmetic progressions of integers, the following conditions being satisfied:
(i) each integer belongs to at least one of them; (ii) each progression contains a number which does not belong to other progressions.
Denote by nn the least common multiple of the ratios of these progressions; let n=p1α1⋯pkαkn=p_1^{\alpha_1} \cdots p_k^{\alpha_k} its prime factorization.
Prove that s≥1+∑i=1kαi(pi−1).s \geq 1 + \sum^k_{i=1} \alpha_i (p_i - 1).
Proposed by Dierk Schleicher, Germany
Back to ProblemsView on AoPS