The greatest number for four digits which when divided by 3, 5, 7, 9 leave remainders 1, 3, 5, 7 respectively is

Options

A. 9763
B. 9764
C. 9766
D. 9765

Answer

To find the greatest four-digit number that, when divided by 3, 5, 7, and 9, leaves remainders of 1, 3, 5, and 7 respectively, we can follow these steps:

### Step 1: Set up the congruences
We can express the conditions given in the problem as a system of congruences:
- Let the number be \( x \).
- From the problem, we have:
- \( x \equiv 1 \mod 3 \)
- \( x \equiv 3 \mod 5 \)
- \( x \equiv 5 \mod 7 \)
- \( x \equiv 7 \mod 9 \)

### Step 2: Rewrite the congruences
To simplify our calculations, we can rewrite the congruences:
- \( x = 3k + 1 \) for some integer \( k \)
- \( x = 5m + 3 \) for some integer \( m \)
- \( x = 7n + 5 \) for some integer \( n \)
- \( x = 9p + 7 \) for some integer \( p \)

### Step 3: Find a common solution
We will solve these congruences step by step. Starting with the first two:
1. From \( x \equiv 1 \mod 3 \) and \( x \equiv 3 \mod 5 \):
- We can substitute \( x = 3k + 1 \) into the second equation:
- \( 3k + 1 \equiv 3 \mod 5 \)
- This simplifies to \( 3k \equiv 2 \mod 5 \).
- The multiplicative inverse of 3 modulo 5 is 2 (since \( 3 \times 2 \equiv 1 \mod 5 \)).
- Multiplying both sides by 2 gives \( k \equiv 4 \mod 5 \).
- Thus, \( k = 5j + 4 \) for some integer \( j \).
- Substituting back gives \( x = 3(5j + 4) + 1 = 15j + 13 \).

### Step 4: Continue solving with the next congruences
2. Now we have \( x \equiv 13 \mod 15 \) and we need to incorporate \( x \equiv 5 \mod 7 \):
- Substitute \( x = 15j + 13 \) into \( x \equiv 5 \mod 7 \):
- \( 15j + 13 \equiv 5 \mod 7 \).
- Reducing \( 15 \mod 7 \) gives \( 1 \), and \( 13 \mod 7 \) gives \( 6 \):
- Thus, \( j + 6 \equiv 5 \mod 7 \) simplifies to \( j \equiv -1 \mod 7 \) or \( j \equiv 6 \mod 7 \).
- Hence, \( j = 7m + 6 \) for some integer \( m \).
- Substituting back gives \( x = 15(7m + 6) + 13 = 105m + 103 \).

### Step 5: Incorporate the last congruence
3. Now we have \( x \equiv 103 \mod 105 \) and need to satisfy \( x \equiv 7 \mod 9 \):
- Substitute \( x = 105m + 103 \) into \( x \equiv 7 \mod 9 \):
- \( 105m + 103 \equiv 7 \mod 9 \).
- Reducing \( 105 \mod 9 \) gives \( 6 \) and \( 103 \mod 9 \) gives \( 4 \):
- Thus, \( 6m + 4 \equiv 7 \mod 9 \) simplifies to \( 6m \equiv 3 \mod 9 \).
- Dividing by 3 gives \( 2m \equiv 1 \mod 3 \), which has a solution \( m \equiv 2 \mod 3 \).
- Hence, \( m = 3n + 2 \) for some integer \( n \).
- Substituting back gives \( x = 105(3n + 2) + 103 = 315n + 313 \).

### Step 6: Find the greatest four-digit number
Now we need to find the largest four-digit number:
- The largest four-digit number is 9999.
- Set \( 315n + 313 \leq 9999 \):
- \( 315n \leq 9999 - 313 \)
- \( 315n \leq 9686 \)
- \( n \leq \frac{9686}{315} \approx 30.8 \).
- Therefore, the largest integer \( n \) is 30.

### Step 7: Calculate the final value of \( x \)
- Substitute \( n = 30 \) back into \( x \):
- \( x = 315(30) + 313 = 9450 + 313 = 9763 \).

Thus, the greatest four-digit number that satisfies all the given conditions is **9763**.