What is the least positive integer n that leaves a remainder of 3 when divided by 7, a rem… — GRE General Test

What is the least positive integer $n$ that leaves a remainder of $3$ when divided by $7$ , a remainder of $4$ when divided by $5$ , and is divisible by $9$ ?

Answer: 234

Answer

The least positive integer satisfying all three conditions is 234.

To find the least positive integer

n

that satisfies

n \equiv 3 \pmod{7}

n \equiv 4 \pmod{5}

, and

n \equiv 0 \pmod{9}

, we first find a general expression for integers meeting the first two conditions. Checking values of

5m + 4

modulo 7 gives

24

as the smallest positive integer matching both. The combined condition is

n \equiv 24 \pmod{35}

, or

n = 35k + 24

. Requiring

35k + 24

to be divisible by 9 gives

8k + 6 \equiv 0 \pmod{9}

, which simplifies to

k \equiv 6 \pmod{9}

. The smallest non-negative integer value for

k

6

, leading to

n = 35(6) + 24 = 234

Step-by-Step Solution

Set up system of modular congruences for the remainders

n \equiv 3 \pmod{7}

n \equiv 4 \pmod{5}

, and

n \equiv 0 \pmod{9}

Translates the remainder and divisibility conditions into mathematical equations.

Combine the first two congruences using the Chinese Remainder Theorem approach

n \equiv 24 \pmod{35}

, so

n = 35k + 24

for an integer

k \ge 0

Since

\text{lcm}(5, 7) = 35

, the solutions to the combined system repeat every 35 integer values.

Enforce the divisibility condition by 9 on

n = 35k + 24

35k + 24 \equiv 0 \pmod{9} \implies 8k + 6 \equiv 0 \pmod{9} \implies -k + 6 \equiv 0 \pmod{9} \implies k \equiv 6 \pmod{9}

Reduces coefficients modulo 9 to find the values of

k

that make

n

a multiple of 9.

Calculate the smallest positive integer

n

corresponding to

k = 6

n = 35(6) + 24 = 234

Choosing

k = 6

yields the smallest non-negative integer for

k

that satisfies all conditions.

Key Concept

Simultaneous congruences and divisibility constraints

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic