Math Problem Statement

MBA Nexus - CAT & OMETS 2024, [19-10-2024 08:49] Q3 A 4-digit number when successively divided by 9, 8 & 6 leaves remainder of 4, 3, & 2 respectively. What could be the remainder when the number is divided by 20?

MBA Nexus - CAT & OMETS 2024, [19-10-2024 08:50] [ Poll : Ans ]

  • 19
  • 11
  • 15
  • All of the above

Solution

We are tasked with finding a 4-digit number that, when successively divided by 9, 8, and 6, leaves remainders 4, 3, and 2, respectively. Ultimately, we want to determine the remainder when this number is divided by 20.

Step-by-step solution:

Let's denote the number by NN. We are given the following conditions:

  1. N4 (mod 9)N \equiv 4 \ (\text{mod} \ 9)
  2. N3 (mod 8)N \equiv 3 \ (\text{mod} \ 8)
  3. N2 (mod 6)N \equiv 2 \ (\text{mod} \ 6)

We will solve this system using the Chinese Remainder Theorem.

Step 1: Solve the first two congruences

We have: N4 (mod 9)N \equiv 4 \ (\text{mod} \ 9) N3 (mod 8)N \equiv 3 \ (\text{mod} \ 8)

Let's assume N=9k+4N = 9k + 4 for some integer kk (from N4 (mod 9)N \equiv 4 \ (\text{mod} \ 9)). Substituting this into the second congruence:

9k+43 (mod 8)9k + 4 \equiv 3 \ (\text{mod} \ 8) Simplifying: 9k17 (mod 8)9k \equiv -1 \equiv 7 \ (\text{mod} \ 8) Since 91 (mod 8)9 \equiv 1 \ (\text{mod} \ 8), we have: k7 (mod 8)k \equiv 7 \ (\text{mod} \ 8) Thus, k=8m+7k = 8m + 7 for some integer mm.

Step 2: Substitute back into the equation for NN

Now substitute k=8m+7k = 8m + 7 into N=9k+4N = 9k + 4: N=9(8m+7)+4=72m+63+4=72m+67N = 9(8m + 7) + 4 = 72m + 63 + 4 = 72m + 67 Thus: N67 (mod 72)N \equiv 67 \ (\text{mod} \ 72)

Step 3: Solve the third congruence

We now incorporate the third condition: N2 (mod 6)N \equiv 2 \ (\text{mod} \ 6) Substitute N=72m+67N = 72m + 67 into this congruence: 72m+672 (mod 6)72m + 67 \equiv 2 \ (\text{mod} \ 6) Since 720 (mod 6)72 \equiv 0 \ (\text{mod} \ 6) and 671 (mod 6)67 \equiv 1 \ (\text{mod} \ 6), we have: 12 (mod 6)1 \equiv 2 \ (\text{mod} \ 6) This is clearly false, so let's correct the third modulus condition. Instead, we handle the modulus 6 step by looking for compatible simultaneous conditions.

Ask a new question for Free

By Image

Drop file here or Click Here to upload

Math Problem Analysis

Mathematical Concepts

Number Theory
Modular Arithmetic
Chinese Remainder Theorem

Formulas

N ≡ r (mod m)
Chinese Remainder Theorem conditions

Theorems

Chinese Remainder Theorem

Suitable Grade Level

College/University Level