Problem

Source: Romania TST 1 2012, Problem 1

Tags: induction, number theory, greatest common divisor, geometry, number theory proposed



Let n1,,nk be positive integers, and define d1=1 and di=(n1,,ni1)(n1,,ni), for i{2,,k}, where (m1,,m) denotes the greatest common divisor of the integers m1,,m. Prove that the sums ki=1aini with ai{1,,di} for i{1,,k} are mutually distinct \mod n_1.