Let N = 75x38y2 be a seven-digit number that is completely divisible by 72, where x and y … — State PSC Exam

Let $N = 75x38y2$ be a seven-digit number that is completely divisible by $72$ , where $x$ and $y$ are single-digit natural numbers such that $x > y$ . What is the remainder when $2^{x \cdot y + 1}$ is divided by $13$ ?

$2$ Answer
B
$11$
C
$3$
D
$6$

Answer

The remainder when

2^{x \cdot y + 1}

is divided by

13

2

The seven-digit number

75x38y2

is divisible by

72

, which means it must satisfy divisibility by both

8

and

9

. The last three digits

8y2

are divisible by

8

only when

y = 3

y = 7

. The sum of digits

25 + x + y

is divisible by

9

when

x + y = 2

x + y = 11

. Testing

y = 3

gives

x = 8

, which satisfies

x > y

. Testing

y = 7

gives

x = 4

, which violates

x > y

. Thus,

x = 8

and

y = 3

, giving

x \cdot y + 1 = 25

. By Fermat's Little Theorem,

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

, so

2^{25} = (2^{12})^2 \cdot 2^1 \equiv 2 \pmod{13}

Step-by-Step Solution

Apply divisibility rule by 8 to find possible values of y

y

can be either

3

7

A number is divisible by

72

if it is divisible by both

8

and

9

. For divisibility by

8

, the last three digits

8y2

must be divisible by

8

. Testing single digits gives

832 / 8 = 104

and

872 / 8 = 109

Apply divisibility rule by 9 to find corresponding x values and enforce x > y

x = 8

and

y = 3

For divisibility by

9

, the sum of digits

(7 + 5 + x + 3 + 8 + y + 2 = 25 + x + y)

must be a multiple of

9

. If

y = 3

28 + x = 36 \implies x = 8

, satisfying

x > y

. If

y = 7

32 + x = 36 \implies x = 4

, which violates

x > y

Evaluate the exponent x * y + 1

Exponent = 25

Substituting

x = 8

and

y = 3

gives

8 \cdot 3 + 1 = 25

Calculate 2^25 mod 13 using Fermat's Little Theorem

Remainder is 2

Since

13

is prime, Fermat's Little Theorem states

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

. Therefore,

2^{25} = (2^{12})^2 \cdot 2^1 \equiv 1^2 \cdot 2 \equiv 2 \pmod{13}

Key Concept

Combining composite divisibility rules (8 and 9) with Fermat's Little Theorem for large power remainder evaluation.

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic