Consider the largest three-digit natural number N which, when successively divided by 6, 7… — State PSC Exam

Consider the largest three-digit natural number $N$ which, when successively divided by $6$ , $7$ , and $8$ , leaves remainders of $4$ , $3$ , and $5$ respectively. What is the true positive remainder when the mathematical expression $E = 42^{63} - N$ is divided by $13$ ?

A
3
7Answer
C
8
D
6

Answer

The correct remainder is 7.

The correct answer is derived by first reconstructing the number through successive division logic to find

N = 904

. Next, applying Fermat's Little Theorem simplifies

42^{63} \pmod{13}

1

. The expression becomes

1 - 7 = -6 \pmod{13}

, which correctly maps to a true positive remainder of

7

Step-by-Step Solution

Determine the algebraic form of the number

N

based on the successive division conditions.

N = 336 \cdot Q_3 + 232

By working backward from the final quotient

Q_3

, we construct the relations:

Q_2 = 8 \cdot Q_3 + 5

Q_1 = 7 \cdot Q_2 + 3

, and

N = 6 \cdot Q_1 + 4

. Substituting these yields the general form for

N

Find the largest three-digit natural number

N

N = 904

Substitute increasing integer values for

Q_3

. For

Q_3 = 0

N = 232

. For

Q_3 = 1

N = 568

. For

Q_3 = 2

N = 904

. For

Q_3 = 3

N = 1240

(which is four digits). Thus,

904

is the largest valid three-digit number.

Calculate the remainder of

42^{63}

divided by

13

42^{63} \equiv 1 \pmod{13}

Since

42 = 13 \times 3 + 3

42 \equiv 3 \pmod{13}

. By Fermat's Little Theorem,

3^{12} \equiv 1 \pmod{13}

. Breaking down the exponent:

63 = 12 \times 5 + 3

. Thus,

3^{63} \equiv (3^{12})^5 \cdot 3^3 \equiv 1^5 \cdot 27 \equiv 27 \pmod{13}

. Finally,

27 \pmod{13} = 1

Calculate the remainder of

N

divided by

13

and evaluate the full expression

E

E \equiv 7 \pmod{13}

904 = 13 \times 69 + 7

, so

N \equiv 7 \pmod{13}

. Substituting the remainders into the expression:

E \equiv 1 - 7 = -6 \pmod{13}

. To find the true positive remainder, add the divisor:

-6 + 13 = 7

Key Concept

Combining Successive Division modeling with Modular Exponentiation and Negative Remainder conversion.

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic