Examkin

Question

Difficulty: HardProperties of Integers and Divisibility

How many positive integers nn less than 1,0001,000 are divisible by 1212, leave a remainder of 44 when divided by 55, and are not divisible by 99?

  1. A
    11
  2. 12Answer
  3. C
    13
  4. D
    15
  5. E
    17

Answer

12
The problem asks for positive integers n<1,000n < 1,000 that satisfy three conditions: n=12kn = 12k, n≡4(mod5)n \equiv 4 \pmod 5, and 9∤n9 \nmid n. Expressing n=12kn = 12k and substituting into the modular equation yields 2k≡4(mod5)2k \equiv 4 \pmod 5, which simplifies to k≡2(mod5)k \equiv 2 \pmod 5. For k≤83k \le 83, setting k=5m+2k = 5m + 2 yields 1717 values for m∈{0,1,…,16}m \in \{0, 1, \dots, 16\}. Furthermore, 12k12k is divisible by 99 if and only if kk is a multiple of 33, which corresponds to m≡2(mod3)m \equiv 2 \pmod 3. The values m=2,5,8,11,14m = 2, 5, 8, 11, 14 (55 values) must be excluded. Subtracting 55 from 1717 leaves exactly 1212 valid integers.

Step-by-Step Solution

1
Express nn in terms of its divisibility by 1212 and set the upper bound.
n=12kn = 12k for a positive integer kk. Since n<1,000n < 1,000, we have 12k<1,00012k < 1,000, which implies k≤83k \le 83.
Any positive integer divisible by 1212 must be a positive integer multiple of 1212.
2
Apply the modular remainder condition modulo 55.
12k≡4(mod5)  ⟹  2k≡4(mod5)  ⟹  k≡2(mod5)12k \equiv 4 \pmod 5 \implies 2k \equiv 4 \pmod 5 \implies k \equiv 2 \pmod 5.
Since 12≡2(mod5)12 \equiv 2 \pmod 5, simplifying the congruence gives k≡2(mod5)k \equiv 2 \pmod 5.
3
Determine the candidate set of values for kk.
kk can be written as k=5m+2k = 5m + 2. For 1≤k≤831 \le k \le 83, the non-negative integer mm ranges from 00 to 1616 inclusive, yielding 1717 possible values.
The maximum value 5m+2≤835m + 2 \le 83 gives 5m≤81  ⟹  m≤165m \le 81 \implies m \le 16.
4
Apply the condition that nn is not divisible by 99.
12k=3×4×k12k = 3 \times 4 \times k is divisible by 99 if and only if kk is divisible by 33. 5m+2≡2m+2(mod3)5m + 2 \equiv 2m + 2 \pmod 3, so 2m+2≡0(mod3)  ⟹  m≡2(mod3)2m + 2 \equiv 0 \pmod 3 \implies m \equiv 2 \pmod 3.
Since 1212 already contains one factor of 33, 12k12k needs kk to supply another factor of 33 to be divisible by 99.
5
Filter out the excluded values of mm and calculate the final count.
Values of m∈{0,1,…,16}m \in \{0, 1, \dots, 16\} with m≡2(mod3)m \equiv 2 \pmod 3 are m∈{2,5,8,11,14}m \in \{2, 5, 8, 11, 14\} (55 values). The number of valid integers is 17−5=1217 - 5 = 12.
Subtracting the excluded multiples of 99 from the candidate set leaves the exact number of valid integers.

Key Concept

Modular arithmetic, linear congruences, and counting integer multiples with divisibility constraints
Estimated Time:2m 0s
Rate this question

Topics

Properties of Integers and Divisibility

More questions from this topic