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

Approach: Two remainder conditions at once \(-\) write the number to satisfy one of them automatically, then force the second. Start from the divisor-9 form because 9 is the larger modulus, so fewer candidates to scan.

Step 1: The conditions are \(N \equiv 4 \pmod{7}\) and \(N \equiv 5 \pmod{9}\). Write \(N = 9k + 5\), which already satisfies the second.

Step 2: Impose the first condition:
\[ 9k + 5 \equiv 4 \pmod{7}. \]
Since \(9 \equiv 2 \pmod 7\), this is \(2k + 5 \equiv 4\), i.e. \(2k \equiv -1 \equiv 6 \pmod 7\).

Step 3: Divide by 2 (allowed, since \(\gcd(2,7)=1\)): \(k \equiv 3 \pmod 7\), so \(k = 7j + 3\).

Step 4: Substitute back:
\[ N = 9(7j+3) + 5 = 63j + 32. \]
We need \(N > 100\): \(63j + 32 > 100 \implies 63j > 68 \implies j \ge 2\). The smallest is \(j = 2\):
\[ N = 63(2) + 32 = 158. \]
Check: \(158 = 7 \times 22 + 4\) and \(158 = 9 \times 17 + 5\). Both hold.

Final Answer: 158.

Answer 2

Direct listing method: Numbers leaving remainder 4 on division by 7 are \( 4, 11, 18, 25, 32, 39, 46, \ldots \) (each 7 more than the last). Checking each for a remainder of 5 on division by 9: \( 32 \) works (\( 32=3\times9+5 \)), but \( 32<100 \). Continuing the list past 100 and checking mod 9 each time, the next match is \( 158 \) (\( 158=17\times9+5 \)).

Since the pattern of remainders mod 9 realigns every \( 7\times9=63 \) steps, matches occur every 63 apart: \( 32, 95, 158, \ldots \) — confirming \( 158 \) is the first one exceeding 100.

\[ \boxed{158} \]