2025 AMC 10A Problem 17

P16-20~4 minPrint

GCD & LCM Divisibility & Factors Bound the quantity above/below or estimate to pin it down Set up the equation/formula and compute; no special trick needed

Let $N$ be the unique positive integer such that dividing $273436$ by $N$ leaves a remainder of $16$ and dividing $272760$ by $N$ leaves a remainder of $15$ . What is the tens digit of $N$ ?

Show solution without answering

Key insight

Take away the remainders: N divides both 273420 and 272745, so it divides 45, their greatest common factor. A remainder of 16 forces N above 16, so N = 45.

Solution

Step 1: get rid of the remainders. "Dividing $273436$ by $N$ leaves remainder $16$ " means $273436$ is $16$ more than a multiple of $N$ . So subtract the remainder:

$273436 - 16 = 273420$ is a multiple of $N$ .
$272760 - 15 = 272745$ is a multiple of $N$ .

Step 2: subtract to get a small number. If two numbers are both multiples of $N$ , so is their difference:
$273420 - 272745 = 675.$
So $N$ divides $675 = 27 \cdot 25 = 3^3 \cdot 5^2$ .

Step 3: narrow it down with $273420$ . $N$ must also divide $273420$ . Check which parts of $675$ go into it:

Powers of $5$ : $273420$ ends in $20$ , so it is a multiple of $5$ but not of $25$ (multiples of $25$ end in $00$ , $25$ , $50$ or $75$ ). So $N$ has at most one factor of $5$ .
Powers of $3$ : the digit sum is $2+7+3+4+2+0 = 18$ , so $273420$ is a multiple of $9$ . Dividing, $273420 \div 9 = 30380$ , whose digit sum is $14$ , not a multiple of $3$ . So $273420$ is not a multiple of $27$ , and $N$ has at most two factors of $3$ .

So $N$ divides $9 \cdot 5 = 45$ . The choices for $N$ are $1, 3, 5, 9, 15, 45$ .

Step 4: use the size of the remainder. A remainder is always smaller than the number you divide by. The remainder $16$ means $N > 16$ . The only number on the list bigger than $16$ is
$N = 45.$

Step 5: check. $45 \cdot 6076 = 273420$ , so $273436 = 45 \cdot 6076 + 16$ . And $45 \cdot 6061 = 272745$ , so $272760 = 45 \cdot 6061 + 15$ . Both remainders are right.

The tens digit of $45$ is $4$ .

The answer is $\boxed{\textbf{(E)}\ 4}$ .

Why this works

A remainder problem becomes a divisibility problem as soon as you subtract the remainder. Then the difference of two multiples of $N$ is also a multiple of $N$ , which shrinks six-digit numbers down to something small you can factor. Finally, the fact that a remainder is less than the divisor is a free clue that picks out one answer from the short list.

Alternative approach

Find the greatest common factor of $273420$ and $272745$ by repeated division (the Euclidean algorithm).

Their difference is $675$ , so the greatest common factor of the two big numbers is the same as that of $272745$ and $675$ .
Divide: $675 \cdot 404 = 272700$ , leaving $272745 - 272700 = 45$ . So now it is the greatest common factor of $675$ and $45$ .
$675 = 45 \cdot 15$ , so $45$ divides $675$ evenly, and the greatest common factor is $45$ .

$N$ must divide $45$ and be bigger than $16$ , so $N = 45$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Remove the remainders first. The two conditions say exactly that
$N \mid 273436 - 16 = 273420 \qquad\text{and}\qquad N \mid 272760 - 15 = 272745.$
So $N$ divides any combination of these, in particular their difference:
$273420 - 272745 = 675.$

Now run the Euclidean algorithm on the pair:
$\gcd(273420,\,272745) = \gcd(272745,\,675).$
Since $675 \cdot 404 = 272700$ , the next remainder is $272745 - 272700 = 45$ , and $675 = 45 \cdot 15$ , so
$\gcd(273420,\,272745) = 45.$

Hence $N$ is a divisor of $45$ : one of $1, 3, 5, 9, 15, 45$ . A remainder of $16$ requires $N > 16$ , which leaves only
$N = 45.$

Check: $45 \cdot 6076 = 273420$ , so $273436 = 45 \cdot 6076 + 16$ ; and $45 \cdot 6061 = 272745$ , so $272760 = 45 \cdot 6061 + 15$ . Both conditions hold, and the tens digit of $45$ is $4$ .

The answer is $\boxed{\textbf{(E)}\ 4}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 3: Multiples and Divisors (§3.3, §3.4, §3.7)
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 4: Prime Factorization (§4.7)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)