A decentralized network consists of 13 primary verification nodes. A smart contract genera… — State PSC Exam

A decentralized network consists of $13$ primary verification nodes. A smart contract generates a total of $37^{105}$ encrypted tokens that must be distributed equally among these $13$ nodes. The leftover tokens that cannot be distributed equally are sent to a burn address. How many tokens will be sent to the burn address?

Answer: 8 tokens

Answer

The correct remainder when

37^{105}

is divided by

13

8

. This is found by reducing the base

37

-2

modulo

13

, applying Fermat's Little Theorem to reduce the exponent

105

9

modulo

12

, and computing

(-2)^9 \pmod{13} = -18 \equiv 8 \pmod{13}

Step-by-Step Solution

Formulate the problem using modular arithmetic.

Evaluate

37^{105} \pmod{13}

Since tokens are distributed equally among 13 nodes, the tokens sent to the burn address represent the remainder when the total is divided by 13.

Simplify the base of the exponent.

37 = 13 \times 2 + 11

. Using a negative remainder,

11 \equiv -2 \pmod{13}

Working with a smaller absolute base value like -2 makes successive exponentiation much easier than working with 11 or 37.

Apply Fermat's Little Theorem.

Since 13 is prime,

(-2)^{12} \equiv 1 \pmod{13}

This theorem allows us to significantly reduce large exponents by finding their remainder when divided by

p-1

Reduce the exponent using the theorem.

105 = 12 \times 8 + 9

. Thus,

(-2)^{105} = ((-2)^{12})^8 \times (-2)^9 \equiv 1^8 \times (-2)^9 \equiv (-2)^9 \pmod{13}

The multiples of 12 in the exponent evaluate to 1 modulo 13, leaving only the remainder of the exponent.

Calculate the final reduced power.

(-2)^4 = 16 \equiv 3 \pmod{13}

. Therefore,

(-2)^8 = 3^2 = 9 \pmod{13}

. Finally,

(-2)^9 = 9 \times (-2) = -18 \pmod{13}

Breaking the calculation into smaller powers prevents the need to calculate very large numbers directly.

Convert the negative result to a positive remainder.

-18 = 13 \times (-2) + 8

. The positive remainder is

8

Physical quantities, such as the number of leftover tokens, must be represented by a positive remainder.

Key Concept

Modular arithmetic, Fermat's Little Theorem, and negative remainders

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic