Question

A number when divided by 7 leaves a remainder 4 and when divided by 9 leaves a remainder 5. What is the smallest such number greater than 100?

Hint:

For remainder problems, check if adding or subtracting a small number from N results in a common multiple. Here, N+3 gives remainder 0 with 7 (\(N=7k+4 \implies N+3=7k+7\)) but not with 9 (\(N=9m+5 \implies N+3=9m+8\)). If it works for both, the solution is faster.

Answer 1

Correct Answer: 158

Step 1: Understanding the Question:
We are looking for a number 'N' that satisfies two conditions simultaneously, which can be expressed using modular arithmetic:
1. \(N \equiv 4 \pmod{7}\)
2. \(N \equiv 5 \pmod{9}\)
We need to find the smallest integer solution for N that is greater than 100.
Step 2: Key Formula or Approach:
This is a classic problem that can be solved using the Chinese Remainder Theorem or by substitution. We will use the substitution method.
1. Express N in terms of one of the conditions (e.g., \(N = 9k + 5\)).
2. Substitute this expression into the other congruence and solve for the parameter 'k'.
3. This will give a general formula for N.
Step 3: Detailed Explanation:
From the second condition, we can write the number N as:
\[ N = 9k + 5 \quad \text{for some integer } k \geq 0 \] Now, we apply the first condition to this expression:
\[ N \equiv 4 \pmod{7} \] \[ 9k + 5 \equiv 4 \pmod{7} \] We can reduce the coefficients modulo 7: \(9 \equiv 2\).
\[ 2k + 5 \equiv 4 \pmod{7} \] Subtract 5 from both sides:
\[ 2k \equiv -1 \pmod{7} \] Since \(-1 \equiv 6 \pmod{7}\), we have:
\[ 2k \equiv 6 \pmod{7} \] Dividing by 2 (which is valid as gcd(2, 7) = 1):
\[ k \equiv 3 \pmod{7} \] This means 'k' must be of the form \(k = 7j + 3\) for some integer \(j \geq 0\).
Now substitute this form of 'k' back into our expression for N to find the general solution:
\[ N = 9(7j + 3) + 5 \] \[ N = 63j + 27 + 5 \] \[ N = 63j + 32 \] This formula gives all numbers that satisfy both conditions. Now we need to find the smallest one greater than 100.
\[ 63j + 32>100 \] \[ 63j>68 \] \[ j>\frac{68}{63} \approx 1.079 \] Since 'j' must be an integer, the smallest possible value for j is 2.
Substitute \(j=2\) into the general formula for N:
\[ N = 63(2) + 32 = 126 + 32 = 158 \] Step 4: Final Answer:
The smallest such number greater than 100 is 158.