Baltic Way 1990 · Problem 12

Number Theory

Let $m$ and $n$ be positive integers. Prove that $25 m+3 n$ is divisible by 83 if and only if $3 m+7 n$ is divisible by 83 .

When you’re ready

Review material becomes available with the next Daily.

Review

GCD and LCM · Divisibility and factorization · Modular arithmetic

Solution

Solution:

Use the equality $2 \cdot (25 m + 3 n) + 11 \cdot (3 m + 7 n) = 83 m + 83 n$ .