number theorygreatest common divisorDivisibilityProductIMO Shortlist
Problem Statement
(a) Let gcd(m,k)=1. Prove that there exist integers a1,a2,...,am and b1,b2,...,bk such that each product aibj (i=1,2,⋯,m;j=1,2,⋯,k) gives a different residue when divided by mk.(b) Let gcd(m,k)>1. Prove that for any integers a1,a2,...,am and b1,b2,...,bk there must be two products aibj and asbt ((i,j)=(s,t)) that give the same residue when divided by mk.Proposed by Hungary.