Modular Arithmetic

16 questions

Question 1Question

Find the smallest non-negative integer xx that satisfies the linear modular congruence 3x8(mod11)3x \equiv 8 \pmod{11}.

Show answer & explanation

Answer: 10

Answer

The smallest non-negative integer xx is 10.
Evaluating 3x8(mod11)3x \equiv 8 \pmod{11} by testing multiples of 1111 added to 88 gives 3030, which divided by 33 yields x=10x = 10. Since 10[0,10]10 \in [0, 10], it is the canonical solution.

Step-by-Step Solution

1
Convert the modular congruence into an algebraic equation
3x=8+11k3x = 8 + 11k for an integer kk
By definition of congruence modulo 1111, 3x83x - 8 must be a multiple of 1111.
2
Find the smallest integer k0k \ge 0 such that 8+11k8 + 11k is divisible by 3
When k=2k = 2, 8+11(2)=308 + 11(2) = 30
3030 is divisible by 33 (30/3=1030 / 3 = 10).
3
Divide by 3 to isolate xx
x=10x = 10
3(10)=308(mod11)3(10) = 30 \equiv 8 \pmod{11}.

Key Concept

Linear Modular Congruence
Estimated Time:1m 15s
Question 2Question

What is the value of (38)(mod7)(-38) \pmod{7} expressed in standard non-negative remainder form?

Show answer & explanation

Answer: 4

Answer

4
The value 44 is correct because 38=7×(6)+4-38 = 7 \times (-6) + 4. The remainder 44 lies in the standard non-negative range 0r<70 \le r < 7. Alternatively, adding multiples of 77 to 38-38 gives 38+35=3-38 + 35 = -3, and adding 77 once more gives 3+7=4-3 + 7 = 4.

Step-by-Step Solution

1
Find the largest multiple of the modulus 77 that is less than or equal to 38-38.
The multiple is 7×(6)=427 \times (-6) = -42.
Modular arithmetic requires the remainder rr to satisfy 0r<70 \le r < 7 in standard form.
2
Calculate the remainder by subtracting the multiple from the dividend.
38(42)=38+42=4-38 - (-42) = -38 + 42 = 4.
The remainder is the non-negative difference between the number and the multiple of the modulus.

Key Concept

Modular Arithmetic with Negative Numbers
Estimated Time:1m 0s
Question 3Question

If 5x2(mod11)5x \equiv 2 \pmod{11}, what is the value of (x34x)(mod11)(x^3 - 4x) \pmod{11} expressed in standard non-negative remainder form?

Show answer & explanation

Answer: 7

Answer

7
Solving the linear congruence 5x2(mod11)5x \equiv 2 \pmod{11} gives x7(mod11)x \equiv 7 \pmod{11}. Substituting x=7x = 7 into the expression (x34x)(x^3 - 4x) yields 734(7)=34328=3157^3 - 4(7) = 343 - 28 = 315. Dividing 315 by 11 gives a quotient of 28 and a remainder of 7. Alternatively, working entirely modulo 11 gives 26=47(mod11)2 - 6 = -4 \equiv 7 \pmod{11}. Thus, the canonical non-negative remainder is 7.

Step-by-Step Solution

1
Find the modular inverse of 5 modulo 11
The inverse is 9, since 5×9=451(mod11)5 \times 9 = 45 \equiv 1 \pmod{11}.
To isolate xx in the linear congruence 5x2(mod11)5x \equiv 2 \pmod{11}, multiply both sides by the modular inverse of 5.
2
Solve for x modulo 11
x2×9=187(mod11)x \equiv 2 \times 9 = 18 \equiv 7 \pmod{11}.
Simplifying 18 modulo 11 gives the canonical value of xx.
3
Evaluate x34xx^3 - 4x modulo 11
x373=3432(mod11)x^3 \equiv 7^3 = 343 \equiv 2 \pmod{11} and 4x4(7)=286(mod11)4x \equiv 4(7) = 28 \equiv 6 \pmod{11}, so x34x26=4(mod11)x^3 - 4x \equiv 2 - 6 = -4 \pmod{11}.
Substitute x7x \equiv 7 into the polynomial expression and reduce each term modulo 11.
4
Convert negative remainder to canonical non-negative form
4+11=7(mod11)-4 + 11 = 7 \pmod{11}.
Modular remainders must be expressed within the standard range [0,10][0, 10].

Key Concept

Linear modular congruences and negative remainder canonical reduction
Estimated Time:2m 0s
Question 4Question

What is the smallest non-negative integer kk that satisfies the modular congruence 799+k15(mod11)7^{99} + k \equiv -15 \pmod{11}?

Show answer & explanation

Answer: 10

Answer

The correct answer is 10.
Using Fermat's Little Theorem, 7101(mod11)7^{10} \equiv 1 \pmod{11}, which simplifies 799(mod11)7^{99} \pmod{11} to 798(mod11)7^9 \equiv 8 \pmod{11}. Reducing the right-hand side gives 157(mod11)-15 \equiv 7 \pmod{11}. The modular equation 8+k7(mod11)8 + k \equiv 7 \pmod{11} yields k1(mod11)k \equiv -1 \pmod{11}. Adding the modulus 1111 gives the canonical positive remainder 1010.

Step-by-Step Solution

1
Simplify 799(mod11)7^{99} \pmod{11} using Fermat's Little Theorem.
7101(mod11)7^{10} \equiv 1 \pmod{11}, so 799=(710)9×7919×7979(mod11)7^{99} = (7^{10})^9 \times 7^9 \equiv 1^9 \times 7^9 \equiv 7^9 \pmod{11}.
Since 1111 is prime and gcd(7,11)=1\gcd(7, 11) = 1, Fermat's Little Theorem allows exponent reduction modulo 1010.
2
Compute 79(mod11)7^9 \pmod{11}.
7177^1 \equiv 7, 72=4957^2 = 49 \equiv 5, 7452=2537^4 \equiv 5^2 = 25 \equiv 3, 757×3=21107^5 \equiv 7 \times 3 = 21 \equiv 10, 79=75×7410×3=308(mod11)7^9 = 7^5 \times 7^4 \equiv 10 \times 3 = 30 \equiv 8 \pmod{11}.
Repeated squaring and modular multiplication efficiently reduces 797^9 modulo 1111.
3
Reduce the right-hand side 15(mod11)-15 \pmod{11}.
15=2(11)+77(mod11)-15 = -2(11) + 7 \equiv 7 \pmod{11}.
Converting negative numbers into the standard non-negative remainder range [0,10][0, 10].
4
Substitute remainders into the congruence and solve for kk.
8+k7    k78=1(mod11)8 + k \equiv 7 \implies k \equiv 7 - 8 = -1 \pmod{11}.
Linear algebraic rearrangement in modular arithmetic.
5
Convert the negative remainder 1-1 to canonical non-negative form.
k=1+11=10k = -1 + 11 = 10.
The standard remainder must satisfy 0k<110 \leq k < 11.

Key Concept

Modular Exponentiation & Negative Remainder Reduction
Question 5Question

Find the smallest positive integer nn that simultaneously satisfies the linear modular congruences 3n5(mod13)3n \equiv 5 \pmod{13} and 4n2(mod9)4n \equiv 2 \pmod{9}.

Show answer & explanation

Answer: 32

Answer

The smallest positive integer satisfying both congruences is 32.
Solving the first congruence 3n5(mod13)3n \equiv 5 \pmod{13} gives n6(mod13)n \equiv 6 \pmod{13} (since 3×91(mod13)3 \times 9 \equiv 1 \pmod{13} and 5×9=456(mod13)5 \times 9 = 45 \equiv 6 \pmod{13}), which means nn can be written as 13k+613k + 6. Substituting this into the second congruence 4n2(mod9)4n \equiv 2 \pmod{9} yields 4(13k+6)2(mod9)    52k+242(mod9)4(13k + 6) \equiv 2 \pmod{9} \implies 52k + 24 \equiv 2 \pmod{9}. Reducing the coefficients modulo 9 gives 7k+62(mod9)    7k45(mod9)7k + 6 \equiv 2 \pmod{9} \implies 7k \equiv -4 \equiv 5 \pmod{9}. Multiplying by 4 (the modular inverse of 7 modulo 9) yields k202(mod9)k \equiv 20 \equiv 2 \pmod{9}. Setting k=2k = 2 yields the smallest positive integer n=13(2)+6=32n = 13(2) + 6 = 32.

Step-by-Step Solution

1
Solve the first modular congruence 3n5(mod13)3n \equiv 5 \pmod{13} for nn
n6(mod13)n \equiv 6 \pmod{13}, which implies n=13k+6n = 13k + 6
Multiplying both sides by the modular inverse of 3 modulo 13 (which is 9) isolates nn.
2
Solve the second modular congruence 4n2(mod9)4n \equiv 2 \pmod{9} for nn
n5(mod9)n \equiv 5 \pmod{9}
Multiplying both sides by the modular inverse of 4 modulo 9 (which is 7) isolates nn.
3
Substitute n=13k+6n = 13k + 6 into n5(mod9)n \equiv 5 \pmod{9} and simplify modulo 9
4k8(mod9)4k \equiv 8 \pmod{9}
Reducing 13 modulo 9 yields 4k4k, and subtracting 6 from 5 yields 18(mod9)-1 \equiv 8 \pmod{9}.
4
Solve for kk and calculate the smallest positive integer nn
k2(mod9)k \equiv 2 \pmod{9}, giving n=13(2)+6=32n = 13(2) + 6 = 32
Setting the integer parameter kk to its minimum non-negative value 22 provides the smallest positive integer solution.

Key Concept

System of Linear Modular Congruences and Modular Inverses
Question 6Question

If xx is the smallest positive integer satisfying the modular congruence 2x7(mod11)2^x \equiv 7 \pmod{11}, what is the value of (3x24x+5)(mod11)(3x^2 - 4x + 5) \pmod{11} expressed in standard non-negative remainder form?

Show answer & explanation

Answer: 3

Answer

The smallest positive integer exponent satisfying 2x7(mod11)2^x \equiv 7 \pmod{11} is x=7x = 7. Substituting x=7x = 7 into 3x24x+53x^2 - 4x + 5 yields 124124, which simplifies to 3(mod11)3 \pmod{11}.
Evaluating powers of 2 modulo 11 shows that 27=1287(mod11)2^7 = 128 \equiv 7 \pmod{11}, giving x=7x = 7. Substituting x=7x = 7 into 3x24x+53x^2 - 4x + 5 gives 124124, which leaves a remainder of 33 when divided by 1111.

Step-by-Step Solution

1
Find the smallest positive integer exponent xx satisfying 2x7(mod11)2^x \equiv 7 \pmod{11}
x=7x = 7
Evaluating consecutive powers of 2 modulo 11 shows 2122^1 \equiv 2, 2242^2 \equiv 4, 2382^3 \equiv 8, 2452^4 \equiv 5, 25102^5 \equiv 10, 2692^6 \equiv 9, and 2772^7 \equiv 7, making x=7x = 7 the smallest positive integer power.
2
Substitute x=7x = 7 into the expression 3x24x+53x^2 - 4x + 5
124
Direct substitution gives 3(7)24(7)+5=3(49)28+5=14728+5=1243(7)^2 - 4(7) + 5 = 3(49) - 28 + 5 = 147 - 28 + 5 = 124.
3
Reduce 124 modulo 11 to standard non-negative remainder form
3
Dividing 124 by 11 yields a quotient of 11 with a remainder of 3 (124=11×11+3124 = 11 \times 11 + 3).

Key Concept

Modular Exponentiation and Algebraic Evaluation in Modular Arithmetic
Question 7Question

What is the value of (1742)(mod9)(17 - 42) \pmod{9} expressed in standard non-negative remainder form?

Show answer & explanation

Answer: 2

Answer

The value of (1742)(mod9)(17 - 42) \pmod{9} in standard non-negative remainder form is 22.
Evaluating 174217 - 42 gives 25-25. Reducing 25-25 modulo 99 requires finding a non-negative remainder rr such that 25=9q+r-25 = 9q + r with 0r<90 \le r < 9. Choosing q=3q = -3 yields 25=9(3)+2-25 = 9(-3) + 2, making the correct non-negative remainder 22. Alternatively, 178(mod9)17 \equiv 8 \pmod{9} and 426(mod9)42 \equiv 6 \pmod{9}, so 86=2(mod9)8 - 6 = 2 \pmod{9}.

Step-by-Step Solution

1
Perform the subtraction within the parentheses.
1742=2517 - 42 = -25
Evaluate the arithmetic expression inside the modulo operation first.
2
Express 25-25 in terms of the modulus 99 using the division algorithm a=qn+ra = qn + r, where 0r<n0 \le r < n.
25=9×(3)+2-25 = 9 \times (-3) + 2
The remainder rr must be non-negative (0r<90 \le r < 9).
3
Identify the canonical non-negative remainder.
r=2r = 2
Alternatively, 257(mod9)-25 \equiv -7 \pmod{9}, and adding the modulus gives 7+9=2-7 + 9 = 2.

Key Concept

Modular Arithmetic and Negative Remainder Reduction
Estimated Time:45s
Question 8Question

A binary operation Δ\Delta defined on the set of integers modulo 1111 is given by aΔb(2a23ab+b2)(mod11)a \Delta b \equiv (2a^2 - 3ab + b^2) \pmod{11}. Find the smallest non-negative integer xx that satisfies the equation 4Δx5(mod11)4 \Delta x \equiv 5 \pmod{11}.

Show answer & explanation

Answer: 3

Answer

The smallest non-negative integer xx that satisfies 4Δx5(mod11)4 \Delta x \equiv 5 \pmod{11} is 3.
Evaluating 4Δx4 \Delta x gives 3212x+x2x2x+10(mod11)32 - 12x + x^2 \equiv x^2 - x + 10 \pmod{11}. Setting this congruent to 5(mod11)5 \pmod{11} yields x2x+50(mod11)x^2 - x + 5 \equiv 0 \pmod{11}, which converts to x2x60(mod11)x^2 - x - 6 \equiv 0 \pmod{11}. Factoring gives (x3)(x+2)0(mod11)(x - 3)(x + 2) \equiv 0 \pmod{11}, which yields solutions x3(mod11)x \equiv 3 \pmod{11} and x9(mod11)x \equiv 9 \pmod{11}. The smallest non-negative integer among these solutions is 33.

Step-by-Step Solution

1
Substitute the given value a=4a = 4 into the operation definition.
4Δx=2(4)23(4)x+x2=3212x+x24 \Delta x = 2(4)^2 - 3(4)x + x^2 = 32 - 12x + x^2
This establishes the explicit algebraic polynomial in terms of xx.
2
Reduce coefficients modulo 1111.
3210(mod11)32 \equiv 10 \pmod{11} and 12xx(mod11)-12x \equiv -x \pmod{11}, giving x2x+10(mod11)x^2 - x + 10 \pmod{11}.
Simplifying coefficients reduces computational complexity during equation solving.
3
Form the modular quadratic equation and set it to zero.
x2x+105(mod11)    x2x+50(mod11)    x2x60(mod11)x^2 - x + 10 \equiv 5 \pmod{11} \implies x^2 - x + 5 \equiv 0 \pmod{11} \implies x^2 - x - 6 \equiv 0 \pmod{11}.
Expressing 56(mod11)5 \equiv -6 \pmod{11} allows standard integer factorisation.
4
Factor the quadratic polynomial and solve for xx.
(x3)(x+2)0(mod11)    x3 or x29(mod11)(x - 3)(x + 2) \equiv 0 \pmod{11} \implies x \equiv 3 \text{ or } x \equiv -2 \equiv 9 \pmod{11}.
Since 1111 is prime, a product congruent to 0(mod11)0 \pmod{11} implies at least one factor is congruent to 0(mod11)0 \pmod{11}.
5
Select the smallest non-negative integer from the valid solution set {3,9}\{3, 9\}.
x=3x = 3
33 is non-negative and strictly smaller than 99.

Key Concept

Modular Arithmetic Binary Operations and Quadratic Congruences
Estimated Time:3m 0s
Question 9Question

What is the value of (17×5)(mod6)(-17 \times 5) \pmod{6} expressed in standard non-negative remainder form?

Show answer & explanation

Answer: 55

Answer

55
Multiplying 17-17 by 55 yields 85-85. When 85-85 is divided by 66, the closest multiple of 66 below 85-85 is 90-90. The non-negative remainder is 85(90)=5-85 - (-90) = 5, which belongs to the canonical set {0,1,2,3,4,5}\{0, 1, 2, 3, 4, 5\}.

Step-by-Step Solution

1
Multiply the numbers inside the parentheses
17×5=85-17 \times 5 = -85
Perform standard multiplication before applying the modulo operation.
2
Express the negative number in terms of the modulus 6
85=6×(15)+5-85 = 6 \times (-15) + 5
Find the largest multiple of 6 less than or equal to -85, which is -90.
3
Extract the canonical non-negative remainder
55
In standard modular arithmetic, remainders must lie in the range [0,n1][0, n-1], where nn is the modulus.

Key Concept

Modular Arithmetic and Non-Negative Remainders
Question 10Question

Find the value of rr such that 29r(mod8)-29 \equiv r \pmod{8}, where 0r<80 \le r < 8.

Show answer & explanation

Answer: 3

Answer

The value of rr in standard non-negative remainder form is 33.
Dividing 29-29 by 88 yields a quotient of 4-4 and a remainder of 33, because 8×(4)+3=298 \times (-4) + 3 = -29. Since 03<80 \le 3 < 8, 33 is the standard non-negative remainder.

Step-by-Step Solution

1
Express 29-29 in the form 8q+r8q + r, where qq is an integer and 0r<80 \le r < 8.
29=8(4)+3-29 = 8(-4) + 3
To find the standard remainder modulo 88, the remainder rr must satisfy 0r<80 \le r < 8.
2
Identify the remainder value rr.
r=3r = 3
Since 33 lies within the required range [0,7][0, 7], it is the canonical remainder.

Key Concept

Modular Arithmetic and Non-Negative Remainders
Question 11Question

Determine the least non-negative integer congruent to 68(mod9)68 \pmod{9}.

Show answer & explanation

Answer: 5

Answer

The least non-negative integer congruent to 68(mod9)68 \pmod{9} is 5.
Dividing 68 by 9 gives a quotient of 7 and a remainder of 5. Since 05<90 \le 5 < 9, the value 5 is the standard non-negative remainder.

Step-by-Step Solution

1
Divide 68 by the modulus 9 using the division algorithm.
68=9×7+568 = 9 \times 7 + 5
Every integer aa can be written uniquely as a=nq+ra = nq + r where qq is the quotient and 0r<n0 \le r < n.
2
Extract the non-negative remainder rr.
r=5r = 5
In modular arithmetic, the least non-negative integer congruent to a(modn)a \pmod{n} is the remainder rr when aa is divided by nn.

Key Concept

Modular Arithmetic Remainder
Question 12Question

What is the smallest non-negative integer xx that satisfies the modular congruence 5x+72(mod9)5x + 7 \equiv 2 \pmod{9}?

Show answer & explanation

Answer: 88

Answer

The smallest non-negative integer xx is 8.
Subtracting 77 from both sides yields 5x5(mod9)5x \equiv -5 \pmod{9}, which reduces to 5x4(mod9)5x \equiv 4 \pmod{9}. Multiplying both sides by the modular multiplicative inverse of 55 modulo 99 (which is 22, since 5×2=101(mod9)5 \times 2 = 10 \equiv 1 \pmod{9}) gives x4×2=8(mod9)x \equiv 4 \times 2 = 8 \pmod{9}. Thus, the smallest non-negative integer value is 88.

Step-by-Step Solution

1
Isolate the term containing xx by subtracting 7 from both sides of the congruence.
5x275(mod9)5x \equiv 2 - 7 \equiv -5 \pmod{9}
Standard algebraic balance operations apply under modular arithmetic.
2
Convert the negative remainder 5-5 to its canonical non-negative representative in modulo 9.
5+9=4    5x4(mod9)-5 + 9 = 4 \implies 5x \equiv 4 \pmod{9}
Modular numbers are conventionally expressed in the non-negative range [0,n1][0, n-1].
3
Find the modular multiplicative inverse of 5 modulo 9 and multiply both sides by it.
Since 5×2=101(mod9)5 \times 2 = 10 \equiv 1 \pmod{9}, the inverse is 2. Multiplying gives x4×2=8(mod9)x \equiv 4 \times 2 = 8 \pmod{9}.
Multiplying by the modular inverse solves for xx when gcd(5,9)=1\gcd(5, 9) = 1.

Key Concept

Linear Modular Congruences and Modular Inverses
Estimated Time:1m 30s
Question 13Question

If xx is the least positive integer satisfying the modular congruence 4x+93(mod11)4x + 9 \equiv 3 \pmod{11}, what is the value of (x25x+2)(mod11)(x^2 - 5x + 2) \pmod{11} expressed in standard non-negative remainder form?

Show answer & explanation

Answer: 9

Answer

The value of (x25x+2)(mod11)(x^2 - 5x + 2) \pmod{11} in standard non-negative remainder form is 9.
Solving 4x+93(mod11)4x + 9 \equiv 3 \pmod{11} yields 4x65(mod11)4x \equiv -6 \equiv 5 \pmod{11}. Multiplying by 3 (the inverse of 4 mod 11) gives x154(mod11)x \equiv 15 \equiv 4 \pmod{11}. Evaluating (x25x+2)(x^2 - 5x + 2) at x=4x = 4 gives 1620+2=216 - 20 + 2 = -2. Converting 2-2 into the standard non-negative remainder range [0,10][0, 10] gives 2+11=9-2 + 11 = 9.

Step-by-Step Solution

1
Isolate the variable term in the linear modular congruence
4x396(mod11)4x \equiv 3 - 9 \equiv -6 \pmod{11}
Subtract 9 from both sides of the congruence.
2
Convert the negative right-hand side to a non-negative residue modulo 11
4x6+115(mod11)4x \equiv -6 + 11 \equiv 5 \pmod{11}
Add the modulus 11 to obtain the canonical non-negative equivalent.
3
Solve for xx by multiplying by the multiplicative inverse of 4 modulo 11
Since 4×3=121(mod11)4 \times 3 = 12 \equiv 1 \pmod{11}, multiply both sides by 3: x5×3=154(mod11)x \equiv 5 \times 3 = 15 \equiv 4 \pmod{11}. Thus, the least positive integer is x=4x = 4.
The modular inverse of 4 modulo 11 is 3.
4
Substitute x=4x = 4 into the expression (x25x+2)(x^2 - 5x + 2)
425(4)+2=1620+2=24^2 - 5(4) + 2 = 16 - 20 + 2 = -2
Evaluate the quadratic expression using the calculated value of xx.
5
Express 2-2 in canonical non-negative remainder form modulo 11
2+11=9(mod11)-2 + 11 = 9 \pmod{11}
Add the modulus 11 to convert the negative result to a non-negative remainder within [0,10][0, 10].

Key Concept

Solving linear modular congruences and converting negative remainders to canonical form
Question 14Question

What is the canonical non-negative remainder when 345113^{45} - 11 is divided by 77?

Show answer & explanation

Answer: 2

Answer

The correct answer is 2.
Using modular exponentiation, 33=271(mod7)3^3 = 27 \equiv -1 \pmod{7}, so 345=(33)15(1)15=1(mod7)3^{45} = (3^3)^{15} \equiv (-1)^{15} = -1 \pmod{7}. Subtracting 11 yields 111=12(mod7)-1 - 11 = -12 \pmod{7}. Adding 14 (a multiple of 7) gives 12+14=2-12 + 14 = 2, which is the canonical non-negative remainder.

Step-by-Step Solution

1
Evaluate 345(mod7)3^{45} \pmod{7} using power rules
3451(mod7)3^{45} \equiv -1 \pmod{7}
Since 33=271(mod7)3^3 = 27 \equiv -1 \pmod{7}, raising both sides to the power of 15 gives (33)15(1)15=1(mod7)(3^3)^{15} \equiv (-1)^{15} = -1 \pmod{7}.
2
Subtract 11 from the modular result
-12 \pmod{7}
Replacing 3453^{45} with 1-1 gives 111=12-1 - 11 = -12.
3
Reduce -12 to its canonical non-negative remainder in [0,6][0, 6]
2
Adding the smallest multiple of 7 that makes the result non-negative gives 12+14=2-12 + 14 = 2.

Key Concept

Modular Exponentiation and Negative Remainder Reduction
Question 15Question

What is the value of (43×15)(mod8)(-43 \times 15) \pmod{8} expressed in standard non-negative remainder form?

Show answer & explanation

Answer: 33

Answer

3
Reducing 43-43 modulo 88 gives 55, and 1515 modulo 88 gives 77. Multiplying these results yields 353(mod8)35 \equiv 3 \pmod{8}, which is the canonical non-negative remainder.

Step-by-Step Solution

1
Reduce individual factors modulo 8
435(mod8)-43 \equiv 5 \pmod{8} (since 43=6×8+5-43 = -6 \times 8 + 5) and 157(mod8)15 \equiv 7 \pmod{8} (since 15=1×8+715 = 1 \times 8 + 7)
Simplifying terms before multiplication makes arithmetic easier.
2
Multiply the reduced remainders
5×7=355 \times 7 = 35
Modular arithmetic preserves multiplication.
3
Reduce the product modulo 8 to obtain the canonical non-negative remainder
35=4×8+3    353(mod8)35 = 4 \times 8 + 3 \implies 35 \equiv 3 \pmod{8}
The final answer in modular arithmetic must fall within the range [0,n1][0, n-1].

Key Concept

Modular Arithmetic and Canonical Non-Negative Remainders
Question 16Question

If xx is the smallest non-negative integer satisfying the modular congruence 7x+42(mod13)7x + 4 \equiv 2 \pmod{13}, find the value of (x3+2x)(mod13)(x^3 + 2x) \pmod{13} expressed as a canonical non-negative remainder.

Show answer & explanation

Answer: 6

Answer

The canonical non-negative remainder is 6.
Subtracting 4 from both sides of 7x+42(mod13)7x + 4 \equiv 2 \pmod{13} gives 7x211(mod13)7x \equiv -2 \equiv 11 \pmod{13}. Multiplying by the modular inverse of 7 (which is 2, since 7×2=141(mod13)7 \times 2 = 14 \equiv 1 \pmod{13}) yields x229(mod13)x \equiv 22 \equiv 9 \pmod{13}. Evaluating (93+2×9)(mod13)(9^3 + 2 \times 9) \pmod{13} gives (729+18)=747(729 + 18) = 747. Dividing 747 by 13 gives a quotient of 57 and a remainder of 6.

Step-by-Step Solution

1
Isolate the linear term in the congruence
7x211(mod13)7x \equiv -2 \equiv 11 \pmod{13}
Subtracting 4 from both sides simplifies the equation, and 2+13=11-2 + 13 = 11 converts the negative remainder to positive form.
2
Solve for xx by multiplying by the multiplicative inverse of 7 modulo 13
x9(mod13)x \equiv 9 \pmod{13}, so x=9x = 9
Since 7×2=141(mod13)7 \times 2 = 14 \equiv 1 \pmod{13}, multiplying 7x11(mod13)7x \equiv 11 \pmod{13} by 2 yields x229(mod13)x \equiv 22 \equiv 9 \pmod{13}.
3
Evaluate (x3+2x)(mod13)(x^3 + 2x) \pmod{13} using modular reduction
66
93=729=56×13+11(mod13)9^3 = 729 = 56 \times 13 + 1 \equiv 1 \pmod{13} and 2×9=18=1×13+55(mod13)2 \times 9 = 18 = 1 \times 13 + 5 \equiv 5 \pmod{13}. Adding these gives 1+5=61 + 5 = 6.

Key Concept

Solving linear modular congruences and modular polynomial evaluation
Estimated Time:1m 30s
Modular Arithmetic Practice Questions — JAMB UTME | Examkin