MathDB
Primes and Arithmetic Progressions

Source: China TST 2004 Quiz

February 1, 2009
number theory unsolvednumber theory

Problem Statement

The largest one of numbers p1α1,p2α2,,ptαt p_1^{\alpha_1}, p_2^{\alpha_2}, \cdots, p_t^{\alpha_t} is called a <spanclass=latexbold>GoodNumber</span> <span class='latex-bold'>Good Number</span> of positive integer n n, if \displaystyle n\equal{} p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_t^{\alpha_t}, where p1 p_1, p2 p_2, \cdots, pt p_t are pairwisely different primes and α1,α2,,αt \alpha_1, \alpha_2, \cdots, \alpha_t are positive integers. Let n1,n2,,n10000 n_1, n_2, \cdots, n_{10000} be 10000 10000 distinct positive integers such that the <spanclass=latexbold>GoodNumbers</span> <span class='latex-bold'>Good Numbers</span> of n1,n2,,n10000 n_1, n_2, \cdots, n_{10000} are all equal. Prove that there exist integers a1,a2,,a10000 a_1, a_2, \cdots, a_{10000} such that any two of the following 10000 10000 arithmetical progressions \{ a_i, a_i \plus{} n_i, a_i \plus{} 2n_i, a_i \plus{} 3n_i, \cdots \}( i\equal{}1,2, \cdots 10000) have no common terms.