Competition problem — Number theory

Library / /13 of 101

Number theory Difficulty 5.4 AIME, harder Prove it Estonia

Non-negative integers $a$ , $b$ , $q$ , $r$ are all less than $5$ and satisfy conditions $q < a$ and $r < b \le a$ . Dividing $qb + r$ by $5$ gives a remainder of $a$ . Can we be certain that dividing $a$ by $b$ gives a remainder of $r$ ?

Solution

Solution 1: The numbers $a = b = 3$ and $q = r = 2$ satisfy the conditions of the problem, but dividing $3$ by $3$ gives a remainder of $0$ , not $2$ .

Solution 2: The numbers $a = b = 4$ , $q = 2$ and $r = 1$ satisfy the conditions of the problem, but dividing $4$ by $4$ gives a remainder of $0$ , not $1$ .

Solution 3: The numbers $a = 4$ , $b = 3$ , $q = 3$ and $r = 0$ satisfy the conditions of the problem, but dividing $4$ by $3$ gives a remainder of $1$ , not $0$ .

Solution 4: The numbers $a = b = 4$ , $q = 3$ and $r = 2$ satisfy the conditions of the problem, but dividing $4$ by $4$ gives a remainder of $0$ , not $2$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.