2025 AMC 10A Problem 17

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:

1. 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$.
2. 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}$.

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.

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

1. Their difference is $675$, so the greatest common factor of the two big numbers is the same as that of $272745$ and $675$.
2. Divide: $675 \cdot 404 = 272700$, leaving $272745 - 272700 = 45$. So now it is the greatest common factor of $675$ and $45$.
3. $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$.

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}$.