Четири наши момичета се върнаха с медали от Европейската олимпиада по математика

Ето една задача от олимпиадата за тези, които са любопитни:

Нека n , m са естествени числа, по-големи от 1, и нека a₁ , a₂ , ..., a_m - естествени числа, не надхвърлящи n^m . Докажете, че съществуват естествени числа b₁,b₂,...,b_m , не надхвърлящи n , такива, че НОД( a₁+b₁, a₂+b₂, ...,a_m+b_m )<n, където  НОД(x₁, x₂,...x_m) e най-големия общ делител на числата x₁, x₂,...x_m.