CAT 2022 Slot 3 Quant Q16

  • Quantitative Aptitude
  • Number System › HCF/LCM
  • Medium
  • Type in the answer (TITA)
  • CAT_2022_SLOT3_QA_Q16

Question 16

A school has less than 50005000 students and if the students are divided equally into teams of either 99 or 1010 or 1212 or 2525 each, exactly 44 are always left out. However, if they are divided into teams of 1111 each, no one is left out. The maximum number of teams of 1212 each that can be formed out of the students in the school is

Type-in-the-answer (TITA) question: no options are given; enter the value.

Answer this question Opens in practice mode, free, no sign-in.

Show answer and solution

Answer:

150

Solution

  • N=lcm(9,10,12,25)k+4=900k+4N = \text{lcm}(9, 10, 12, 25)k + 4 = 900k + 4.

  • NN must be a multiple of 1111. We check values of kk:

    • k=1  ⟹  N=904k=1 \implies N=904 (not divisible by 1111)

    • k=2  ⟹  N=1804k=2 \implies N=1804 (divisible by 1111, 1804<50001804 < 5000)

    • k=3,4,5k=3, 4, 5 exceed 50005000 for the next valid kk.

  • Max teams of 1212: ⌊1804/12⌋=150\lfloor 1804 / 12 \rfloor = 150.

Detailed explanation

Concept: LCM and Divisibility Rules

  1. Let the total number of students be NN, where N<5000N < 5000.

  2. Given that dividing NN by 9,10,12,259, 10, 12, 25 leaves a remainder of 44, we have:

    • N≡4(modlcm(9,10,12,25))N \equiv 4 \pmod{\text{lcm}(9, 10, 12, 25)}
  3. Finding the LCM:

    • lcm(9,10,12,25)=lcm(32,2×5,22×3,52)=22×32×52=900\text{lcm}(9, 10, 12, 25) = \text{lcm}(3^2, 2 \times 5, 2^2 \times 3, 5^2) = 2^2 \times 3^2 \times 5^2 = 900.
  4. So, N=900k+4N = 900k + 4 for some integer kk.

  5. We are also given that NN is exactly divisible by 1111, so 900k+4≡0(mod11)900k + 4 \equiv 0 \pmod{11}.

  6. Simplify modulo 1111:

    • 900=11×81+9900 = 11 \times 81 + 9, so 900≡9(mod11)900 \equiv 9 \pmod{11}.

    • 9k+4≡0(mod11)  ⟹  9k≡7(mod11)9k + 4 \equiv 0 \pmod{11} \implies 9k \equiv 7 \pmod{11}.

  7. Multiply by 55 (since 5×9=45≡1(mod11)5 \times 9 = 45 \equiv 1 \pmod{11}):

    • k≡35≡2(mod11)k \equiv 35 \equiv 2 \pmod{11}.
  8. So kk can be 2,13,242, 13, 24, etc.

    • If k=2k = 2, N=900(2)+4=1804N = 900(2) + 4 = 1804.

    • If k=13k = 13, N=900(13)+4=11704N = 900(13) + 4 = 11704 (which exceeds the limit of 50005000).

  9. The only valid NN under 50005000 is 18041804.

  10. The maximum number of full teams of 1212 is ⌊1804/12⌋=150\lfloor 1804 / 12 \rfloor = 150.

Practise similar questions

Practice 1 CAT_2022_SLOT3_QA_Q16_SQ01

A sports academy has less than 30003000 athletes, and if the athletes are divided equally into teams of either 66 or 88 or 1515 or 2020 each, exactly 55 are always left out. However, if they are divided into teams of 77 each, no one is left out. The maximum number of teams of 1515 each that can be formed out of the athletes in the academy is

Type-in-the-answer (TITA) question: no options are given; enter the value.

Show answer and solution

Answer:

184

Solution

  • N−5N - 5 is a multiple of lcm(6,8,15,20)=120\text{lcm}(6, 8, 15, 20) = 120, so N=120k+5N = 120k + 5.

  • Condition N≡0(mod7)N \equiv 0 \pmod{7} means 120k+5≡k+5≡0(mod7)  ⟹  k≡2(mod7)120k + 5 \equiv k + 5 \equiv 0 \pmod{7} \implies k \equiv 2 \pmod{7}.

  • Under the constraint N<3000N < 3000, we have k≤24k \le 24.

  • The maximum valid integer is k=23k = 23, giving N=120(23)+5=2765N = 120(23) + 5 = 2765.

  • Maximum teams of 1515 is ⌊2765/15⌋=184\lfloor 2765 / 15 \rfloor = 184.

Practice 2 CAT_2022_SLOT3_QA_Q16_SQ02

A national conference has less than 40004000 delegates, and if the delegates are divided equally into workshop groups of either 88 or 1515 or 2020 or 2525 each, exactly 33 are always left out. However, if they are divided into groups of 1313 each, no one is left out. The maximum number of workshop groups of 2525 each that can be formed out of the delegates at the conference is

Type-in-the-answer (TITA) question: no options are given; enter the value.

Show answer and solution

Answer:

120

Solution

  • N−3N - 3 is a multiple of lcm(8,15,20,25)=600\text{lcm}(8, 15, 20, 25) = 600, so N=600k+3N = 600k + 3.

  • N≡0(mod13)  ⟹  2k+3≡0(mod13)  ⟹  2k≡10(mod13)  ⟹  k≡5(mod13)N \equiv 0 \pmod{13} \implies 2k + 3 \equiv 0 \pmod{13} \implies 2k \equiv 10 \pmod{13} \implies k \equiv 5 \pmod{13}.

  • Under the limit N<4000N < 4000, we require k≤6k \le 6, so the only valid value is k=5k = 5.

  • Total delegates N=600(5)+3=3003N = 600(5) + 3 = 3003.

  • Maximum groups of 2525 is ⌊3003/25⌋=120\lfloor 3003 / 25 \rfloor = 120.

HCF/LCM questions from other CAT papers

  1. CAT 2023 Slot 2 Quant Q2
    For any natural numbers m, n , and k , such that k divides both m+2 n and 3 m +4 n, k must be a common…

Practise this question with timing, notes and your mistake notebook.

Practise in PrepSoc