How many positive integers n less than 1,000 are divisible by 12, leave a remainder of 4 w… — GRE General Test

How many positive integers $n$ less than $1,000$ are divisible by $12$ , leave a remainder of $4$ when divided by $5$ , and are not divisible by $9$ ?

A
11
12Cevap
C
13
D
15
E
17

Cevap

The problem asks for positive integers

n < 1,000

that satisfy three conditions:

n = 12k

n \equiv 4 \pmod 5

, and

9 \nmid n

. Expressing

n = 12k

and substituting into the modular equation yields

2k \equiv 4 \pmod 5

, which simplifies to

k \equiv 2 \pmod 5

. For

k \le 83

, setting

k = 5m + 2

yields

17

values for

m \in \{0, 1, \dots, 16\}

. Furthermore,

12k

is divisible by

9

if and only if

k

is a multiple of

3

, which corresponds to

m \equiv 2 \pmod 3

. The values

m = 2, 5, 8, 11, 14

(

5

values) must be excluded. Subtracting

5

from

17

leaves exactly

12

valid integers.

Adım Adım Çözüm

Express

n

in terms of its divisibility by

12

and set the upper bound.

n = 12k

for a positive integer

k

. Since

n < 1,000

, we have

12k < 1,000

, which implies

k \le 83

Any positive integer divisible by

12

must be a positive integer multiple of

12

Apply the modular remainder condition modulo

5

12k \equiv 4 \pmod 5 \implies 2k \equiv 4 \pmod 5 \implies k \equiv 2 \pmod 5

Since

12 \equiv 2 \pmod 5

, simplifying the congruence gives

k \equiv 2 \pmod 5

Determine the candidate set of values for

k

k

can be written as

k = 5m + 2

. For

1 \le k \le 83

, the non-negative integer

m

ranges from

0

16

inclusive, yielding

17

possible values.

The maximum value

5m + 2 \le 83

gives

5m \le 81 \implies m \le 16

Apply the condition that

n

is not divisible by

9

12k = 3 \times 4 \times k

is divisible by

9

if and only if

k

is divisible by

3

5m + 2 \equiv 2m + 2 \pmod 3

, so

2m + 2 \equiv 0 \pmod 3 \implies m \equiv 2 \pmod 3

Since

12

already contains one factor of

3

12k

needs

k

to supply another factor of

3

to be divisible by

9

Filter out the excluded values of

m

and calculate the final count.

Values of

m \in \{0, 1, \dots, 16\}

with

m \equiv 2 \pmod 3

are

m \in \{2, 5, 8, 11, 14\}

(

5

values). The number of valid integers is

17 - 5 = 12

Subtracting the excluded multiples of

9

from the candidate set leaves the exact number of valid integers.

Anahtar Kavram

Modular arithmetic, linear congruences, and counting integer multiples with divisibility constraints

Tahmini Süre:2m 0s

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Konular

Bu konudan daha fazla soru