Olympiad Maths Prep

Track / Stage 5 / 147 of 400 #747 of 2000

Problem 747

AIME late
Number theory Difficulty 5.4 Find the answer

4. Find the largest even three-digit number xx that gives a remainder of 2 when divided by 5 and satisfies the condition GCD(30,GCD(x,15))=3\operatorname{GCD}(30, \operatorname{GCD}(x, 15))=3.

Official solution

Solution. From the condition, we get that there exist such a,bNa, b \in \mathbb{N} that 3a=303a=30, GCD (x,15)=3b(x, 15)=3b, and GCD (a,b)=1(a, b)=1.

Consider the equality GCD (x,15)=3b(x, 15)=3b. This means that c,dN\exists c, d \in \mathbb{N} such that x=3bcx=3bc and 15=3bd15=3bd, and GCD (c,d)=1(c, d)=1.

From the equality 15=3bd15=3bd it follows that bd=5bd=5, i.e., [b=1,d=5b=5,d=1\left[\begin{array}{l}b=1, d=5 \\ b=5, d=1\end{array}\right..

Let b=1,d=5b=1, d=5. Then x=3cx=3c. Considering that xx is even, we get x=6mx=6m. From the condition GCD (c,d)=1(c, d)=1 it follows that cc does not divide 5, which means that 6m6m does not divide 5, i.e., xx can be any of the following numbers: 30l+6,30l+12,30l+18,30l+2430l+6, 30l+12, 30l+18, 30l+24, where ll is any natural number. Considering that xx when divided by 5 gives a remainder of 2,
only 30l+1230l+12 fits.

Let b=5,d=1b=5, d=1. Then x=15cx=15c, i.e., x=30tx=30t, but then GCD (x,15)=(x, 15)= 15 and GCD (30(30, GCD (x,15))=15(x, 15))=15- contradiction.

Therefore, the problem has been reduced to finding the largest three-digit number of the form 30l+1230l+12. This is 972.

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