MathDB

8

Part of 1987 IMO Shortlist

Problems(1)

a_i . b_j mod mk (IMO SL 1987-P8)

Source:

8/19/2010
(a) Let gcd⁡(m,k)=1\gcd(m, k) = 1. Prove that there exist integers a1,a2,...,ama_1, a_2, . . . , a_m and b1,b2,...,bkb_1, b_2, . . . , b_k such that each product aibja_ib_j (i=1,2,⋯ ,m; j=1,2,⋯ ,ki = 1, 2, \cdots ,m; \ j = 1, 2, \cdots, k) gives a different residue when divided by mk.mk.
(b) Let gcd⁡(m,k)>1\gcd(m, k) > 1. Prove that for any integers a1,a2,...,ama_1, a_2, . . . , a_m and b1,b2,...,bkb_1, b_2, . . . , b_k there must be two products aibja_ib_j and asbta_sb_t ((i,j)≠(s,t)(i, j) \neq (s, t)) that give the same residue when divided by mk.mk.
Proposed by Hungary.
number theorygreatest common divisorDivisibilityProductIMO Shortlist