Which is the smallest number that when divided by 15, 18 and 20 leaves a reminder of 13,
16 and 18 respectively?


We are asked to find the smallest number \( N \) such that:

\[
N \equiv 13 \ (\text{mod} \ 15)
\]
\[
N \equiv 16 \ (\text{mod} \ 18)
\]
\[
N \equiv 18 \ (\text{mod} \ 20)
\]

This is a problem of finding the smallest number satisfying these three simultaneous congruences. Let's solve it step by step using the Chinese Remainder Theorem (CRT).

### Step 1: Represent the congruences clearly

The number \( N \) can be written as:
\[
N = 15k + 13
\]
for some integer \( k \), because when divided by 15, \( N \) leaves a remainder of 13.

Similarly:
\[
N = 18m + 16
\]
\[
N = 20n + 18
\]
for some integers \( m \) and \( n \).

### Step 2: Solving two congruences at a time

Let's first focus on the congruences modulo 15 and 18.

1. From \( N = 15k + 13 \), substitute this into \( N \equiv 16 \ (\text{mod} \ 18) \):
\[
15k + 13 \equiv 16 \ (\text{mod} \ 18)
\]
Simplifying this:
\[
15k \equiv 3 \ (\text{mod} \ 18)
\]
Now, divide both sides by 3:
\[
5k \equiv 1 \ (\text{mod} \ 6)
\]
The inverse of 5 modulo 6 is 5 (since \( 5 \times 5 \equiv 25 \equiv 1 \ (\text{mod} \ 6) \)).
Thus, multiplying both sides of the equation by 5:
\[
k \equiv 5 \ (\text{mod} \ 6)
\]
So, \( k = 6p + 5 \) for some integer \( p \).

### Step 3: Substitute back into the first congruence

Now substitute \( k = 6p + 5 \) into \( N = 15k + 13 \):
\[
N = 15(6p + 5) + 13 = 90p + 75 + 13 = 90p + 88
\]
Thus, \( N = 90p + 88 \).

### Step 4: Solve with the third congruence

Now use \( N = 90p + 88 \) in the third congruence \( N \equiv 18 \ (\text{mod} \ 20) \):
\[
90p + 88 \equiv 18 \ (\text{mod} \ 20)
\]
Simplify:
\[
90p + 88 \equiv 18 \ (\text{mod} \ 20)
\]
\[
10p + 8 \equiv 18 \ (\text{mod} \ 20)
\]
\[
10p \equiv 10 \ (\text{mod} \ 20)
\]
Dividing both sides by 10:
\[
p \equiv 1 \ (\text{mod} \ 2)
\]
Thus, \( p = 2q + 1 \) for some integer \( q \).

### Step 5: Substitute back into the expression for \( N \)

Substitute \( p = 2q + 1 \) into \( N = 90p + 88 \):
\[
N = 90(2q + 1) + 88 = 180q + 90 + 88 = 180q + 178
\]
Thus, \( N = 180q + 178 \).

### Step 6: Find the smallest solution

The smallest solution occurs when \( q = 0 \), so the smallest \( N \) is:
\[
N = 178
\]

Thus, the smallest number that satisfies all the given conditions is \( N = 178 \).

Would you like more details, or do you have any questions?

Here are 5 related questions to deepen your understanding:
1. How does the Chinese Remainder Theorem apply to solving simultaneous congruences?
2. Can you find the general solution for all \( N \) in this problem?
3. How would the method change if we had more than three congruences?
4. What would happen if the moduli were not pairwise coprime?
5. How can we verify if the solution found is correct?

**Tip**: Always check that your solution satisfies all original congruences to ensure it's correct.

Which is the smallest number that when divided by 15, 18 and 20 leaves a reminder of 13, 16 and 18 respectively?

Learn how to find the smallest number that satisfies the given congruences: N ≡ 13 (mod 15), N ≡ 16 (mod 18), and N ≡ 18 (mod 20). This solution demonstrates the application of the Chinese Remainder Theorem, modular arithmetic, and step-by-step problem-solving techniques. Suitable for students in Grades 10-12.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation