Divisibility Rules and Remainder Theorem Practice Questions — State PSC Exam

Question 1Question →

In a sequence of arithmetic operations, a candidate calculates a value of $-82$ . If this integer is then divided by $9$ , determine the least non-negative remainder.

Show answer & explanation

Answer: 8

Answer

8

Applying the division algorithm,

-82

can be expressed in the form

dq + r

as

9 \times (-10) + 8

. Since the remainder

r

must be greater than or equal to

0

and strictly less than the divisor

9

, the least non-negative remainder is

8

.

Step-by-Step Solution

1

Identify the dividend and the divisor.

Dividend is

-82

, divisor is

9

.

To apply the formal mathematical definition of division with remainders.

2

Find the largest integer multiple of

9

that is less than or equal to

-82

.

The correct multiple is

-90

(since

-90 \leq -82

).

The remainder must be a strictly non-negative value, meaning the multiple we subtract from the dividend must not exceed the dividend.

3

Calculate the difference between the dividend and this multiple to find the remainder.

-82 - (-90) = 8

.

This difference represents the least non-negative remainder required by the problem.

Key Concept

Remainder Theorem and Negative Dividends

Question 2Question →

Determine the positive remainder when the value of $36^{43}$ is divided by $37$ .

Show answer & explanation

Answer: 36

Answer

36

By the properties of modular arithmetic,

36

is congruent to

-1

modulo

37

. When we raise both sides to the power of

43

, we obtain

36^{43} \equiv (-1)^{43} \pmod{37}

. Since an odd power of

-1

is still

-1

, the expression leaves a remainder of

-1

. To find the standard positive remainder, we simply add the divisor to this result:

-1 + 37 = 36

.

Step-by-Step Solution

1

Express the base as a negative remainder modulo the divisor.

When

36

is divided by

37

, the remainder can be expressed as

-1

because

36 = 37 \times 1 - 1

. Therefore, we can state that

36 \equiv -1 \pmod{37}

.

Using a negative remainder with an absolute value of

1

makes calculating large exponentiations trivial.

2

Apply the exponent to the negative remainder and convert back to a positive value.

Calculate

(-1)^{43}

. Since

43

is an odd number,

(-1)^{43} = -1

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

-1 + 37 = 36

.

The rules of modular arithmetic allow us to raise the remainder to the given power. However, the final answer must always be a non-negative integer strictly less than the divisor.

Key Concept

Negative Remainders for Large Powers

Alternative Method

You can use Fermat's Little Theorem, which states

a^{p-1} \equiv 1 \pmod p

for any prime

p

(as long as

a

is not divisible by

p

). Here,

p = 37

, so

36^{36} \equiv 1 \pmod{37}

. We can split the expression:

36^{43} = 36^{36} \times 36^7 \equiv 1 \times 36^7 \pmod{37}

. Using the negative remainder trick for the remaining part gives

(-1)^7 = -1

. Adding

37

yields the positive remainder of

36

.

Estimated Time:30s

Question 3Question →

Let $N$ be the smallest positive integer that leaves a remainder of $3$ when divided by $11$ , a remainder of $5$ when divided by $13$ , and is exactly divisible by $7$ . What is the remainder when $N^4 + N^2 + 1$ is divided by $17$ ?

Show answer & explanation

Answer: 3

Answer

The remainder when

N^4 + N^2 + 1

is divided by

17

is 3.

Using the Chinese Remainder Theorem, the smallest integer meeting all divisibility constraints is determined to be

N = 707

. Reducing

707

modulo

17

gives

10

. Substituting

10

into the expression

N^4 + N^2 + 1

modulo

17

yields

(10^4 + 10^2 + 1) \pmod{17} = (4 + 15 + 1) \pmod{17} = 20 \pmod{17} = 3

.

Step-by-Step Solution

1

Express the given conditions as a system of linear congruences

N \equiv 3 \pmod{11}

,

N \equiv 5 \pmod{13}

, and

N \equiv 0 \pmod{7}

.

Translates the problem statement into standard modular arithmetic notation.

2

Solve the simultaneous congruences for modulo 11 and modulo 13

Let

N = 11k + 3

. Substituting into

11k + 3 \equiv 5 \pmod{13}

gives

11k \equiv 2 \pmod{13} \implies -2k \equiv 2 \pmod{13} \implies k \equiv 12 \pmod{13}

. Thus,

N = 11(13m + 12) + 3 = 143m + 135

.

Combines two modular constraints into a single general expression using the Chinese Remainder Theorem principle.

3

Apply the divisibility condition for 7 to determine the smallest value of

N

143m + 135 \equiv 0 \pmod{7} \implies 3m + 2 \equiv 0 \pmod{7} \implies 3m \equiv 5 \pmod{7} \implies m \equiv 4 \pmod{7}

. For the smallest positive integer, set

m = 4

, so

N = 143(4) + 135 = 707

.

Finds the specific smallest integer

N

that satisfies all three divisor requirements.

4

Reduce

N

modulo 17

707 = 17 \times 41 + 10 \implies N \equiv 10 \pmod{17}

.

Simplifies the base before evaluating higher powers.

5

Calculate the polynomial expression

(N^4 + N^2 + 1) \pmod{17}

N^2 \equiv 10^2 = 100 \equiv 15 \equiv -2 \pmod{17}

, and

N^4 \equiv (-2)^2 = 4 \pmod{17}

. Therefore,

N^4 + N^2 + 1 \equiv 4 + 15 + 1 = 20 \equiv 3 \pmod{17}

.

Uses modular exponentiation properties to efficiently evaluate the final remainder.

Key Concept

Chinese Remainder Theorem and Modular Exponentiation

Question 4Question →

What is the remainder when the expression $15^{100} + 19^{100}$ is divided by $17$ ?

15

2

1

3

Show answer & explanation

Answer: 15

Answer

The remainder when

15^{100} + 19^{100}

is divided by

17

is

15

.

Reducing the bases modulo 17 gives

15 \equiv -2

and

19 \equiv 2

. Since

100

is even,

(-2)^{100} + 2^{100} = 2 \cdot 2^{100} = 2^{101}

. By Fermat's Little Theorem (

2^{16} \equiv 1 \pmod{17}

),

2^{101} \equiv 2^5 = 32 \equiv 15 \pmod{17}

. Thus, the correct remainder is 15.

Step-by-Step Solution

1

Reduce the base numbers modulo 17

15 \equiv -2 \pmod{17}

and

19 \equiv 2 \pmod{17}

Using negative remainders simplifies power calculations.

2

Rewrite the expression using modular congruence

15^{100} + 19^{100} \equiv (-2)^{100} + 2^{100} = 2^{100} + 2^{100} = 2 \times 2^{100} = 2^{101} \pmod{17}

Since the exponent

100

is even,

(-2)^{100} = 2^{100}

.

3

Apply Fermat's Little Theorem to simplify the exponent

2^{16} \equiv 1 \pmod{17}

17 is prime and

\gcd(2, 17) = 1

.

4

Divide the exponent 101 by 16 to find the remaining power

101 = 16 \times 6 + 5 \implies 2^{101} \equiv (2^{16})^6 \times 2^5 \equiv 1^6 \times 32 \equiv 32 \pmod{17}

Any integer power of 1 is 1 under modular arithmetic.

5

Compute the final positive remainder

32 = 17 \times 1 + 15 \implies 32 \equiv 15 \pmod{17}

(or

-2 + 17 = 15

)

Remainders must be non-negative integers strictly less than the divisor.

Key Concept

Fermat's Little Theorem and Negative Remainders in Modular Arithmetic

Question 5Question →

A positive integer $N$ when successively divided by $4$ , $5$ , and $6$ leaves remainders of $2$ , $3$ , and $4$ , respectively. What is the sum of the remainders obtained when the smallest such number $N$ is successively divided by $6$ , $5$ , and $4$ , in that order?

Show answer & explanation

Answer: 7

Answer

The sum of the remainders obtained when the smallest such number is successively divided by 6, 5, and 4 is 7.

The smallest positive integer

N

satisfying the given successive division conditions is 94. Successively dividing 94 by 6, 5, and 4 yields quotients of 15, 3, and 0 with remainders 4, 0, and 3, respectively. The sum of these remainders is

4 + 0 + 3 = 7

.

Step-by-Step Solution

1

Formulate the algebraic equations for successive division and calculate the smallest positive value of

N

.

N = 94

By definition of successive division,

N = 4q_1 + 2

,

q_1 = 5q_2 + 3

, and

q_2 = 6q_3 + 4

. Setting the non-negative integer quotient

q_3 = 0

yields

q_2 = 4

,

q_1 = 23

, and

N = 94

.

2

Perform successive division of 94 by the divisors 6, 5, and 4 in sequence.

The sequence of remainders is

4

,

0

, and

3

.

First stage:

94 \div 6 = 15

remainder

4

. Second stage:

15 \div 5 = 3

remainder

0

. Third stage:

3 \div 4 = 0

remainder

3

.

3

Calculate the sum of the three remainders.

4 + 0 + 3 = 7

Adding the individual remainders obtained from each stage of the reverse order division.

Key Concept

Successive Division and Remainder Property

Question 6Question →

What is the remainder when the mathematical expression $14 \times 47^{55} - 63$ is divided by $48$ ?

29

16

19

1

Show answer & explanation

Answer: 19

Answer

The correct remainder is 19.

The correct answer is found by applying modular arithmetic properties. First, simplify the base:

47 \equiv -1 \pmod{48}

. Raising this to an odd power gives

47^{55} \equiv (-1)^{55} = -1 \pmod{48}

. Substituting this back into the expression yields

14 \times (-1) - 63

. We can also simplify

63 \pmod{48}

to

15

. The expression then becomes

-14 - 15 = -29 \pmod{48}

. Because standard remainders cannot be negative, we add the divisor (48) to find the true positive remainder:

-29 + 48 = 19

.

Step-by-Step Solution

1

Simplify the base of the exponent modulo 48.

47 \equiv -1 \pmod{48}

Using negative remainders makes calculating large powers manageable.

2

Evaluate the exponentiated term modulo 48.

(-1)^{55} = -1

An odd power of -1 remains -1.

3

Simplify the constant term modulo 48.

63 \equiv 15 \pmod{48}

To keep all terms within the modulo base before finalizing the expression.

4

Substitute the simplified values back into the expression.

14 \times (-1) - 15 = -14 - 15 = -29

To find the overall remainder of the expression, which currently results in a negative value.

5

Convert the negative remainder to a valid positive remainder.

-29 + 48 = 19

Remainders must be strictly positive integers less than the divisor.

Key Concept

Divisibility Rules and Remainder Theorem

Question 7Question →

If the number $11^{2025}$ is decreased by $16^{2025}$ , and the resulting difference is divided by $9$ , what is the remainder?

7

2

4

0

Show answer & explanation

Answer: 7

Answer

7

To find the remainder of

11^{2025} - 16^{2025}

divided by

9

, we first simplify the bases using modular arithmetic:

11 \equiv 2 \pmod 9

and

16 \equiv -2 \pmod 9

. Next, we evaluate the powers. We know

2^3 = 8 \equiv -1 \pmod 9

. By rewriting the exponent,

2^{2025} = (2^3)^{675} \equiv (-1)^{675} = -1 \pmod 9

. For the second term,

(-2)^{2025} = - (2^{2025}) \equiv -(-1) = 1 \pmod 9

. Subtracting the two terms yields

-1 - 1 = -2

. Because a remainder must be positive, we add the divisor to the negative result:

-2 + 9 = 7

.

Step-by-Step Solution

1

Reduce the base numbers modulo 9.

11 \equiv 2 \pmod 9

and

16 \equiv 7 \equiv -2 \pmod 9

.

Reducing the bases simplifies the expression to

2^{2025} - (-2)^{2025} \pmod 9

.

2

Determine the cyclicity pattern for powers of 2 modulo 9.

2^1=2

,

2^2=4

,

2^3=8 \equiv -1 \pmod 9

.

Finding a power that leaves a remainder of

1

or

-1

allows us to easily compute extremely large exponents.

3

Evaluate the first term

2^{2025} \pmod 9

.

2^{2025} = (2^3)^{675} \equiv (-1)^{675} = -1 \pmod 9

.

Breaking the exponent

2025

into

3 \times 675

utilizes the known value of

2^3 \pmod 9

.

4

Evaluate the second term

(-2)^{2025} \pmod 9

.

(-2)^{2025} = - (2^{2025}) \equiv -(-1) = 1 \pmod 9

.

An odd power preserves the negative sign, allowing substitution of the result from the previous step.

5

Subtract the remainders and map to a positive equivalent.

(-1) - 1 = -2

. To make it positive, add

9

:

-2 + 9 = 7

.

Remainders must be strictly positive and less than the divisor. Adding the divisor to a negative modular result finds its positive equivalent.

Key Concept

Modular Arithmetic Cyclicity and Negative Remainders

Question 8Question →

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?

Show answer & explanation

Answer: 8

Answer

8

The correct remainder when

37^{105}

is divided by

13

is

8

. This is found by reducing the base

37

to

-2

modulo

13

, applying Fermat's Little Theorem to reduce the exponent

105

to

9

modulo

12

, and computing

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

.

Step-by-Step Solution

1

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.

2

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.

3

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

.

4

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.

5

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.

6

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 9Question →

What is the remainder when $3^{53}$ is divided by $7$ ?

5

2

1

4

Show answer & explanation

Answer: $5$

Answer

The remainder when

3^{53}

is divided by

7

is

5

.

By applying modular arithmetic rules,

3^3 = 27 \equiv -1 \pmod{7}

. Expanding

3^{53}

gives

(3^3)^{17} \times 3^2 \equiv (-1)^{17} \times 2 = -2 \pmod{7}

. Adding

7

to the negative remainder yields the standard positive remainder of

5

.

Step-by-Step Solution

1

Express the base

3

in terms of powers close to a multiple of

7

3^3 = 27 = 7 \times 4 - 1 \equiv -1 \pmod{7}

Finding a power that yields

\pm 1 \pmod{7}

simplifies modular exponentiation.

2

Rewrite

3^{53}

using

3^3

3^{53} = (3^3)^{17} \times 3^2

Break down the exponent

53

as

3 \times 17 + 2

using laws of indices.

3

Evaluate the expression modulo

7

3^{53} \equiv (-1)^{17} \times 9 \equiv -1 \times 2 = -2 \pmod{7}

Since

(-1)

raised to an odd power is

-1

, and

9 \equiv 2 \pmod{7}

.

4

Convert negative remainder to positive equivalent

-2 + 7 = 5

Remainders in standard arithmetic must be non-negative integers in the range

[0, \text{divisor}-1]

.

Key Concept

Remainder Theorem and Modular Arithmetic

Question 10Question →

In a digital encryption protocol, a security key is generated based on a master integer $N$ . When $N$ is successively divided by $6$ , $8$ , and $9$ , the resulting remainders are $4$ , $3$ , and $7$ , respectively. If $N$ is the smallest possible positive integer that satisfies these conditions, what is the remainder when $N$ is divided by $19$ ?

Show answer & explanation

Answer: 16

Answer

16

By applying the rules of successive division and working backwards from a final quotient of 0, the smallest possible integer

N

is found to be 358. Dividing 358 by 19 yields a quotient of 18 and a remainder of 16.

Step-by-Step Solution

1

Set up equations based on the definition of successive division.

N = 6q_1 + 4

,

q_1 = 8q_2 + 3

, and

q_2 = 9q_3 + 7

Successive division means each division is performed on the quotient of the previous step.

2

Determine the value of the final quotient

q_3

to minimize

N

.

q_3 = 0

The smallest possible positive initial number

N

is obtained when the final successive quotient is zero.

3

Solve for intermediate quotient

q_2

.

q_2 = 9(0) + 7 = 7

Substitute

q_3 = 0

into the equation

q_2 = 9q_3 + 7

.

4

Solve for intermediate quotient

q_1

.

q_1 = 8(7) + 3 = 59

Substitute

q_2 = 7

into the equation

q_1 = 8q_2 + 3

.

5

Calculate the smallest positive integer

N

.

N = 6(59) + 4 = 358

Substitute

q_1 = 59

into the first equation.

6

Divide

N

by

19

to find the final remainder.

358 = 19 \times 18 + 16

. The remainder is

16

.

The problem asks for the remainder when the resulting

N

is divided by

19

.

Key Concept

Successive Division and Remainder Theorem

Estimated Time:1m 30s

Question 11Question →

Consider the integer $N = 4 - 2 \times 2^{68} + 7 \times 14^{85}$ . If $N$ is divided by $13$ , which of the following represents the correct remainder?

6

7

5

9

Show answer & explanation

Answer: 6

Answer

The correct remainder is 6.

By applying Fermat's Little Theorem,

2^{68} \equiv 2^8 \equiv 9 \pmod{13}

, and clearly

14^{85} \equiv 1^{85} \equiv 1 \pmod{13}

. Substituting these values gives the expression

4 - 2(9) + 7(1) = 4 - 18 + 7 = -7

. To find the valid positive remainder, we add the divisor 13 to the negative result, yielding

-7 + 13 = 6

.

Step-by-Step Solution

1

Simplify the term

14^{85} \pmod{13}

1

Since

14 \equiv 1 \pmod{13}

, any power of 14 will also be congruent to

1^{85} = 1

.

2

Simplify the term

2^{68} \pmod{13}

using Fermat's Little Theorem

9

Fermat's theorem states

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

. Dividing 68 by 12 gives a quotient of 5 and a remainder of 8. Thus,

2^{68} \equiv 2^8 \pmod{13}

. Since

2^8 = 256

, and

256 = 13 \times 19 + 9

, the value is 9.

3

Substitute the simplified modulo values back into the original expression

4 - 2(9) + 7(1) \pmod{13}

Replacing the large exponent terms with their modulo 13 equivalents allows for simple arithmetic evaluation.

4

Evaluate the simplified arithmetic expression from left to right

-7

Following the correct order of operations:

4 - 18 + 7 = -14 + 7 = -7

.

5

Convert the negative result into a valid positive remainder

6

Remainders must be non-negative. Add the divisor (13) to the negative result:

-7 + 13 = 6

.

Key Concept

Modular Arithmetic, Fermat's Little Theorem, and Negative Remainders

Question 12Question →

Consider a sequence of integers generated by the mathematical formula $T_n = 17^n - 40$ . What is the positive remainder obtained when the $123^{\text{rd}}$ term of this sequence is divided by $9$ ?

4

5

6

3

Show answer & explanation

Answer: 4

Answer

4

Applying the rules of modular arithmetic, we first reduce the base

17

modulo

9

, giving

-1

. Raising

-1

to the odd power of

123

yields

-1

. The expression then simplifies to

-1 - 40 = -41

. Because remainders must be non-negative, we add the next largest multiple of

9

(which is

45

) to

-41

, resulting in a final positive remainder of

4

.

Step-by-Step Solution

1

Set up the expression for the

123^{\text{rd}}

term modulo

9

.

T_{123} \equiv (17^{123} - 40) \pmod 9

We need to find the remainder of the specific sequence term when divided by

9

.

2

Reduce the base of the exponent modulo

9

.

17 \equiv -1 \pmod 9

Using a base of

-1

simplifies the calculation of large powers.

3

Evaluate the exponent part using the reduced base.

(-1)^{123} = -1

Raising a negative number to an odd power retains the negative sign.

4

Substitute back into the expression and compute the intermediate remainder.

-1 - 40 = -41

Combining the evaluated power with the rest of the sequence formula.

5

Convert the negative value into a valid positive remainder modulo

9

.

-41 = 9 \times (-5) + 4 \implies \text{Remainder is } 4

A true remainder must be a positive integer strictly less than the divisor. We achieve this by adding multiples of

9

until the value is positive.

Key Concept

Modular arithmetic reduction, exponent parity rules, and conversion of negative remainders.

Question 13Question →

An integer $P$ is given by the mathematical expression $P = 4 \cdot 36^{2033} - 6 \cdot 58^{2033} - 2 \cdot 89^{2033}$ . Determine the positive remainder when $P$ is divided by $17$ .

Show answer & explanation

Answer: 9

Answer

9

The correct answer is derived by first reducing the bases modulo 17, giving 2, 7, and 4 respectively. Then, utilizing Fermat's Little Theorem (

a^{16} \equiv 1 \pmod{17}

), the exponent 2033 is reduced to

2033 \pmod{16} = 1

. Substituting these simplified values back into the expression yields

4(2) - 6(7) - 2(4) = -42

. Because a remainder must be positive, adding the next highest multiple of 17 (which is

17 \times 3 = 51

) to -42 gives the final valid remainder of 9.

Step-by-Step Solution

1

Find the remainder of each base when divided by 17.

36 \equiv 2 \pmod{17}

,

58 \equiv 7 \pmod{17}

, and

89 \equiv 4 \pmod{17}

.

Reducing bases before dealing with large exponents simplifies the modular arithmetic calculation.

2

Apply Fermat's Little Theorem to simplify the exponent.

Since 17 is a prime number,

a^{16} \equiv 1 \pmod{17}

. The exponent is

2033 = 16 \times 127 + 1

, meaning

a^{2033} \equiv a^1 \pmod{17}

.

Fermat's Little Theorem allows us to reduce massive exponents by dividing them by

(p-1)

and keeping only the remainder.

3

Substitute the reduced bases and exponents into the original expression.

P \equiv 4(2^1) - 6(7^1) - 2(4^1) \pmod{17}

, which evaluates to

8 - 42 - 8 = -42

.

This step calculates the combined overall remainder before adjusting for the strict definition of a positive modulo.

4

Convert the negative result to a valid positive remainder.

-42 \equiv -42 + 51 = 9 \pmod{17}

.

A remainder must be a non-negative integer strictly less than the divisor (17). Adding the next highest multiple of 17 (which is 51) provides the correct positive remainder.

Key Concept

Divisibility Rules and Remainder Theorem

Question 14Question →

In a centralized database architecture, data records are distributed across $17$ server nodes numbered from $0$ to $16$ . A record with a numerical key $K$ is assigned to a node using the hash function $H(K) = K \pmod{17}$ , which always yields a positive remainder. If a specific batch of records is assigned a master key given by the expression $K = 2^{200} - 75$ , which server node will process this batch?

Show answer & explanation

Answer: 11

Answer

The batch of records will be processed by server node 11.

By applying modular arithmetic rules, the expression

(2^{200} - 75) \pmod{17}

simplifies individually to

(1 - 7) = -6

. Because node numbers in this system must be positive, adding the divisor 17 to -6 provides the correct positive remainder, which is 11.

Step-by-Step Solution

1

Identify the mathematical goal of the problem.

Calculate

(2^{200} - 75) \pmod{17}

and ensure the final result is a positive integer between 0 and 16.

The server nodes are assigned strictly based on the positive remainder when the key is divided by 17.

2

Find the remainder of the exponential term

2^{200}

divided by 17.

2^4 = 16 \equiv -1 \pmod{17}

. Raising this to the 50th power gives

(2^4)^{50} \equiv (-1)^{50} = 1 \pmod{17}

.

Finding a power of the base that is 1 or -1 modulo the divisor simplifies extremely large exponent calculations.

3

Find the remainder of the constant term 75 divided by 17.

75 = 17 \times 4 + 7

, so

75 \equiv 7 \pmod{17}

.

Each term in a modular arithmetic expression can and should be reduced individually.

4

Combine the reduced terms to find the overall remainder.

1 - 7 = -6 \pmod{17}

.

Substitute the individual reduced remainders back into the original expression

K = 2^{200} - 75

.

5

Convert the negative remainder into a valid positive node number.

-6 + 17 = 11

.

A remainder of -6 indicates the value is 6 units short of a full multiple of 17. The equivalent positive remainder is found by adding the divisor.

Key Concept

Modular arithmetic with large exponents and handling negative remainders appropriately.

Estimated Time:1m 30s

Question 15Question →

Calculate the remainder when the integer value of $11 \times 17^{73}$ is divided by $19$ .

Show answer & explanation

Answer: 16

Answer

16

The correct remainder is found by applying Fermat's Little Theorem to reduce the large exponent, yielding an intermediate calculation of -22. Converting this negative value to a proper positive remainder modulo 19 gives exactly 16.

Step-by-Step Solution

1

Simplify the base of the exponent modulo 19.

17 \equiv -2 \pmod{19}

Working with a smaller absolute value simplifies subsequent exponentiation steps.

2

Apply Fermat's Little Theorem to identify the cyclicity.

a^{18} \equiv 1 \pmod{19}

for any integer

a

not divisible by 19.

Since 19 is a prime number, the remainders of powers will repeat in cycles of 18.

3

Reduce the large exponent

73

using the identified cyclicity.

73 = 18 \times 4 + 1

, which means

(-2)^{73} \equiv (-2)^1 \pmod{19}

Because the powers cycle every 18, only the remainder of the exponent divided by 18 affects the final result.

4

Multiply the reduced exponential term by the leading coefficient.

11 \times (-2) = -22

The original mathematical expression contains a coefficient of 11.

5

Convert the negative intermediate result to a valid positive remainder.

-22 \equiv -22 + 2 \times 19 = -22 + 38 = 16 \pmod{19}

By standard definition, a remainder must be a positive integer strictly less than the divisor.

Key Concept

Modular Arithmetic and Fermat's Little Theorem

Question 16Question →

Evaluate the remainder when the numeric expression $47^{101} + 111^{101} - 25$ is divided by $16$ .

Show answer & explanation

Answer: 5

Answer

5

By applying the properties of modular arithmetic, we determine that

47 \equiv -1 \pmod{16}

and

111 \equiv -1 \pmod{16}

. Raising these to the 101st power yields

-1

and

-1

. Subtracting 25 gives a total of

-27

. To find the positive remainder, we add the next highest multiple of 16 (which is 32) to -27, yielding a final valid positive remainder of 5.

Step-by-Step Solution

1

Find the remainder of the bases when divided by 16.

47 \equiv -1 \pmod{16}

and

111 \equiv -1 \pmod{16}

.

Using negative remainders (since

47 = 16 \times 3 - 1

and

111 = 16 \times 7 - 1

) significantly simplifies the calculation of large powers.

2

Substitute the simplified bases into the original expression.

(47)^{101} + (111)^{101} - 25 \equiv (-1)^{101} + (-1)^{101} - 25 \pmod{16}

.

The properties of modular arithmetic allow replacing bases with their congruent values modulo the divisor.

3

Evaluate the exponents and the constant term.

(-1) + (-1) - 25 = -27

.

An odd power of a negative number remains negative, so

(-1)^{101} = -1

.

4

Find the equivalent positive remainder for -27 modulo 16.

-27 \equiv 5 \pmod{16}

.

Adding multiples of 16 (in this case,

16 \times 2 = 32

) to

-27

yields a positive remainder in the valid range of

0

to

15

. Calculating

-27 + 32 = 5

gives the final remainder.

Key Concept

Modular arithmetic with large powers using negative remainders

Alternative Method

Instead of converting the bases to -1, one could convert them to positive 15. The expression becomes

15^{101} + 15^{101} - 25

. However, evaluating this requires recognizing that

15 \equiv -1 \pmod{16}

to easily compute the large exponents, which ultimately merges back into the primary solution path.

Estimated Time:1m 30s

Question 17Question →

A computer algorithm processes a data block and assigns it a routing ID based on modular arithmetic. This ID corresponds to the strictly positive remainder left after dividing the value of $56^{103} - 45$ by $13$ .

Find the value of this routing ID.

Show answer & explanation

Answer: 11

Answer

11

By reducing each component of the expression modulo 13,

56^{103}

reduces to

4^{103}

, which simplifies to

4

because

4^3 \equiv -1 \pmod{13}

. Subtracting

45 \pmod{13}

, which is

6

, yields

-2

. Adding the divisor 13 to

-2

gives the strictly positive remainder of 11.

Step-by-Step Solution

1

Reduce the base 56 modulo 13.

56 \equiv 4 \pmod{13}

Modular arithmetic allows simplifying the base before exponentiation.

2

Find a pattern to easily evaluate

4^{103} \pmod{13}

.

4^3 = 64 \equiv -1 \pmod{13}

Finding a small power that is congruent to 1 or -1 simplifies large exponents significantly.

3

Evaluate

4^{103} \pmod{13}

using the established pattern.

4^{103} = (4^3)^{34} \times 4^1 \equiv (-1)^{34} \times 4 = 4 \pmod{13}

Exponent rules allow breaking down 103 into

3 \times 34 + 1

.

4

Reduce the subtracted constant 45 modulo 13.

45 = 13 \times 3 + 6 \equiv 6 \pmod{13}

All terms in the expression must be evaluated under the same modulus.

5

Subtract the reduced values.

4 - 6 = -2

Substitute the individual modulo results back into the original expression structure.

6

Convert the negative remainder into a positive remainder.

-2 + 13 = 11

The question asks for a strictly positive remainder, which is standard in modular division contexts.

Key Concept

Modular Arithmetic and Negative Remainders

Question 18Question →

What is the remainder when $4^{15}$ is divided by $5$ ?

4

-1

1

0

Show answer & explanation

Answer: $4$

Answer

The remainder when

4^{15}

is divided by

5

is

4

.

Since

4 \equiv -1 \pmod 5

, raising to the 15th power gives

(-1)^{15} = -1 \pmod 5

. Adding the divisor

5

converts the negative remainder

-1

into the valid positive remainder

4

.

Step-by-Step Solution

1

Express the base number in modular form relative to the divisor.

4 = 5 - 1

, which means

4 \equiv -1 \pmod 5

.

Expressing the base as

-1

modulo

5

simplifies exponent calculation.

2

Raise the modular congruence to the power of 15.

4^{15} \equiv (-1)^{15} \pmod 5 = -1 \pmod 5

.

An odd power of

-1

evaluates to

-1

.

3

Convert the negative remainder into a positive remainder.

-1 + 5 = 4

.

Standard remainders in integer division must be non-negative integers less than the divisor.

Key Concept

Remainder Theorem and Negative Remainder Conversion

Question 19Question →

If the six-digit number $45231x$ is completely divisible by $9$ , what is the value of the digit $x$ ?

Show answer & explanation

Answer: 3

Answer

3

According to the divisibility rule for 9, a number is divisible by 9 if the sum of its digits is a multiple of 9. For the number

45231x

, the sum of the digits is

4 + 5 + 2 + 3 + 1 + x = 15 + x

. The smallest multiple of 9 that is greater than or equal to 15 is 18. Setting

15 + x = 18

gives

x = 3

.

Step-by-Step Solution

1

Find the sum of the known digits in the given number.

4 + 5 + 2 + 3 + 1 = 15

The divisibility rule for 9 requires analyzing the sum of all digits.

2

Formulate the condition for divisibility by 9.

15 + x

must be a multiple of 9.

Including the unknown unit digit

x

, the total digit sum is

15 + x

.

3

Solve for the single-digit integer

x

where

0 \le x \le 9

.

x = 3

The smallest multiple of 9 greater than or equal to 15 is 18, giving

15 + x = 18

, so

x = 3

.

Key Concept

Divisibility Rule for 9

Alternative Method

Dividing 452,310 by 9 yields 50,256 with a remainder of 6. To make the number divisible by 9, the remaining amount needed is

9 - 6 = 3

, so the unit digit

x

must be 3.

Estimated Time:45s

Question 20Question →

An arithmetic expression is formulated as $7 + 10 \times 28^{67}$ . When this entire value is divided by $29$ , what is the resulting positive remainder?

3

12

17

26

Show answer & explanation

Answer: 26

Answer

26

By applying the property of modular arithmetic, we know that

28 \equiv -1 \pmod{29}

. Substituting this into the expression simplifies the exponent:

28^{67} \equiv (-1)^{67} \pmod{29}

. Because 67 is an odd integer,

(-1)^{67} = -1

. The expression becomes

7 + 10 \times (-1)

. Following the order of operations, the multiplication is resolved first to yield

-10

, and then the addition gives

7 - 10 = -3

. Finally, to find the equivalent positive remainder modulo 29, the divisor is added to the negative result:

29 - 3 = 26

.

Step-by-Step Solution

1

Express the base

28

in terms of modulo

29

.

28 \equiv -1 \pmod{29}

Converting to a small negative base drastically simplifies the calculation of large exponents.

2

Evaluate the exponent term modulo

29

.

28^{67} \equiv (-1)^{67} = -1 \pmod{29}

An odd power of

-1

evaluates to

-1

.

3

Apply the standard order of operations (BODMAS) to the expression.

7 + 10 \times (-1) = 7 - 10 = -3 \pmod{29}

Multiplication must be performed before addition.

4

Convert the negative remainder into a valid positive remainder.

29 + (-3) = 26

Standard positive remainders must be non-negative and strictly less than the divisor, which is achieved by adding the divisor to the negative result.

Key Concept

Modular arithmetic principles, specifically managing negative bases and converting negative remainders, applied alongside the standard order of operations.

Alternative Method

One could utilize Fermat's Little Theorem, which states

a^{p-1} \equiv 1 \pmod{p}

for prime

p

. Here,

28^{28} \equiv 1 \pmod{29}

. The power 67 can be broken down:

28^{67} = (28^{28})^2 \times 28^{11} \equiv 1^2 \times (-1)^{11} = -1 \pmod{29}

. This rigorous path mathematically verifies the simpler direct substitution of

-1

.

Estimated Time:1m 0s

Divisibility Rules and Remainder Theorem

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method