Track / Stage 5 / 103 of 400 #703 of 2000

Problem 703

AIME late

Number theory Difficulty 5.3 Find the answer

Let $a$ and $b$ be positive integers that are relatively prime, and let $A=8a+3b$ and $B=3a+2b$ . The greatest common divisor of $A$ and $B$ is not 1. What is the greatest common divisor of $A$ and $B$ ?

Your answer

Official solution

Solution. Let $d$ be the greatest common divisor of $A$ and $B$ . If $d \mid A$ and $d \mid B$ , then $d \mid 8B - 3A = 7b$ , and $d \mid 2A - 3B = 7a$ .

We have found that $d$ is a common divisor of $7a$ and $7b$ . Considering that $a$ and $b$ are coprime, the greatest common divisor of $7a$ and $7b$ is 7. (This follows from the fundamental theorem of arithmetic, which states that every natural number can be uniquely expressed as a product of prime numbers, disregarding the order of the factors.)

Accordingly, $d$ is a divisor of 7, so $d=1$ or $d=7$ . We know that $A$ and $B$ are not coprime, i.e., $(A; B) \neq 1$ , from which it follows that $(A; B)=7$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.