TheCATExam
Sign in

CAT 2022 Slot 1 — QA Question 9

Remainders BasicsEasy

Let A be the largest positive integer that divides all the numbers of the form 3k + 4k + 5k and B be the largest positive integer that divides all the numbesr of the form 4k + 3(4k) + 4k+2, where k is any positive integer. Then (A + B) equals

Answer & solution

Answer: 82

Solution

Easy

For each "largest integer that divides all numbers of a form", plug in small kk to bound the answer, then prove it always holds. The second form factors instantly, which hands you BB for free.

1

Find AA for 3k+4k+5k3^k+4^k+5^k. Test the first two values of kk and take their common divisor:

k=1: 3+4+5=12k=2: 9+16+25=50gcd⁡(12,50)=2\begin{aligned} &k=1:\ 3+4+5=12\\ &k=2:\ 9+16+25=50\\ &\gcd(12,50)=2 \end{aligned}
2

Confirm 22 always divides it. Among 3k,4k,5k3^k,4^k,5^k, the terms 3k3^k and 5k5^k are both odd and 4k4^k is even:

odd+even+odd=even ⇒ 2∣3k+4k+5k\text{odd}+\text{even}+\text{odd}=\text{even}\ \Rightarrow\ 2\mid 3^k+4^k+5^k

Since gcd⁡(12,50)=2\gcd(12,50)=2 rules out anything larger, A=2A=2.

3

Find BB for 4k+3⋅4k+4k+24^k+3\cdot4^k+4^{k+2}. Factor out 4k4^k:

4k+3⋅4k+4k+2=4k(1+3+42)=4k⋅20\begin{aligned} 4^k+3\cdot4^k+4^{k+2}&=4^k\left(1+3+4^2\right)\\ &=4^k\cdot 20 \end{aligned}
4

Largest divisor for all k≥1k\ge 1. The smallest such number is at k=1k=1, giving 4⋅20=804\cdot20=80, and every larger kk keeps the factor 8080:

B=80B=80
A+B=2+80=82A+B=2+80=\mathbf{82}
CAT 2022 Slot 1 QA Q9: Let A be the largest positive integer that divides all the numbers of the form 3 k + 4 k + 5 k and B be the la — Solution | TheCATExam