Modular Arithmetic Quiz: Explore Congruence Concepts

The largest multiple of 11 that does not exceed 97 is 11 multiplied by 8 equals 88. Subtracting gives 97 minus 88 equals 9. The remainder when 97 is divided by 11 is 9. Confirming: 11 multiplied by 8 equals 88, plus 9 equals 97. Since 9 is less than the divisor 11, this is a valid remainder.

The largest multiple of 8 that does not exceed 74 is 8 multiplied by 9 equals 72. Subtracting gives 74 minus 72 equals 2. The remainder when 74 is divided by 8 is 2. Confirming: 8 multiplied by 9 equals 72, plus 2 equals 74. Since 2 is less than the divisor 8, this is a valid remainder.

The answer is True. A linear congruence ax is congruent to b mod m has a solution only when gcd(a, m) divides b. When this condition fails, no value of x can satisfy the congruence. For example, gcd(4, 8) equals 4 and 4 does not divide 3, so 4x is congruent to 3 mod 8 has no solution. This divisibility condition is the fundamental existence test for linear congruences.

The multiplicative inverse of 4 modulo 9 is the number k such that 4 multiplied by k is congruent to 1 mod 9. Testing k equals 7: 4 multiplied by 7 equals 28. Dividing 28 by 9 gives quotient 3 remainder 1, confirming 28 is congruent to 1 mod 9. So the inverse is 7. No other value from 1 to 8 satisfies this condition, and the inverse is unique because gcd(4, 9) equals 1.

Since gcd(3, 7) equals 1, a unique solution exists. Find the inverse of 3 mod 7: 3 multiplied by 5 equals 15, and 15 divided by 7 gives remainder 1, so the inverse of 3 mod 7 is 5. Multiply both sides by 5: x is congruent to 5 multiplied by 4 equals 20 mod 7. 20 divided by 7 gives remainder 6. So x is congruent to 6 mod 7. Confirming: 3 multiplied by 6 equals 18, and 18 divided by 7 gives remainder 4.

A congruence ax is congruent to b mod m has no solution when gcd(a, m) does not divide b. Option A: gcd(4, 8) equals 4, and 4 does not divide 3 — no solution. Option B: gcd(6, 9) equals 3, and 3 does not divide 5 — no solution. Option C: gcd(3, 9) equals 3, and 3 divides 6 — solutions exist. Option D: gcd(5, 7) equals 1, and 1 divides 3 — a solution exists. Only A and B fail the divisibility condition.

Since gcd(5, 7) equals 1, a unique solution exists. Find the inverse of 5 mod 7: 5 multiplied by 3 equals 15, and 15 divided by 7 gives remainder 1, so the inverse of 5 mod 7 is 3. Multiply both sides by 3: x is congruent to 3 multiplied by 3 equals 9 mod 7. 9 divided by 7 gives remainder 2. So x is congruent to 2 mod 7. Confirming: 5 multiplied by 2 equals 10, and 10 divided by 7 gives remainder 3.

The answer is False. When gcd(a, m) equals d and d divides b, the congruence has exactly d solutions modulo m, not one. For example, gcd(6, 10) equals 2 and 2 divides 4, so 6x is congruent to 4 mod 10 has exactly 2 solutions: x equals 4 and x equals 9. A unique solution only occurs when gcd(a, m) equals 1, because in that case d equals 1 and there is exactly 1 solution.

Since gcd(4, 9) equals 1, a unique solution exists. Find the inverse of 4 mod 9: 4 multiplied by 7 equals 28, and 28 divided by 9 gives remainder 1, so the inverse of 4 mod 9 is 7. Multiply both sides by 7: x is congruent to 7 multiplied by 1 equals 7 mod 9. So x is congruent to 7 mod 9. Confirming: 4 multiplied by 7 equals 28, and 28 divided by 9 gives remainder 1.

The number of solutions equals gcd(a, m) when gcd(a, m) divides b. Here gcd(6, 10) equals 2, and 2 divides 4, so solutions exist and there are exactly 2 solutions modulo 10. To find them, divide through by 2: 3x is congruent to 2 mod 5. The inverse of 3 mod 5 is 2 (since 3 multiplied by 2 equals 6 is congruent to 1 mod 5). So x is congruent to 4 mod 5. The two solutions modulo 10 are x equals 4 and x equals 9.

The number of solutions equals gcd(a, m) when gcd(a, m) divides b. Here gcd(6, 15) equals 3, and 3 divides 9, so solutions exist and there are exactly 3 solutions modulo 15. Dividing through by 3: 2x is congruent to 3 mod 5. The inverse of 2 mod 5 is 3. So x is congruent to 9 is congruent to 4 mod 5. The three solutions modulo 15 are x equals 4, x equals 9, and x equals 14.

The two solutions modulo 10 are x equals 4 and x equals 9. Their sum is 4 plus 9 equals 13. Confirming both solutions: 6 multiplied by 4 equals 24, and 24 divided by 10 gives remainder 4. 6 multiplied by 9 equals 54, and 54 divided by 10 gives remainder 4. Both values satisfy the original congruence, and their sum is 13.

The answer is True. If a is congruent to b mod n, then n divides a minus b. If b is congruent to c mod n, then n divides b minus c. Adding these two divisibility statements: n divides (a minus b) plus (b minus c) equals a minus c. Therefore a is congruent to c mod n. For example, if 17 is congruent to 3 mod 7 and 3 is congruent to 10 mod 7, then 17 is congruent to 10 mod 7, confirmed since 17 minus 10 equals 7.

From the first condition, x equals 3k plus 2 for some integer k. Substituting into the second: 3k plus 2 is congruent to 3 mod 5, so 3k is congruent to 1 mod 5. The inverse of 3 mod 5 is 2 (since 3 multiplied by 2 equals 6 is congruent to 1 mod 5). So k is congruent to 2 mod 5, meaning k equals 5j plus 2. Substituting back: x equals 3(5j plus 2) plus 2 equals 15j plus 8. The smallest positive solution is x equals 8. Confirming: 8 divided by 3 gives remainder 2, and 8 divided by 5 gives remainder 3.

The system x is congruent to 1 mod 4 and x is congruent to 2 mod 7 has the unique solution x is congruent to 9 mod 28, meaning all solutions are of the form 9, 37, 65, and so on. Checking option A: 9 divided by 4 gives remainder 1 and 9 divided by 7 gives remainder 2 — both conditions satisfied. Option B: 13 divided by 7 gives remainder 6, not 2 — fails. Option C: 37 divided by 4 gives remainder 1 and 37 divided by 7 gives remainder 2 — both satisfied. Option D: 25 divided by 7 gives remainder 4, not 2 — fails.

Fermat's Little Theorem states that if p is prime and p does not divide a, then a to the power of p minus 1 is congruent to 1 mod p. Here p equals 7 (prime) and a equals 5 (7 does not divide 5). So 5 to the power of 7 minus 1 equals 5 to the power of 6 is congruent to 1 mod 7. This can also be verified using the cycle of 5 mod 7: 5, 4, 6, 2, 3, 1 with period 6. The 6th term is 1, confirming the result.

Count the day number of March 15. January has 31 days, February has 28 days in a non-leap year, and March 15 is the 15th day of March. Total: 31 plus 28 plus 15 equals 74. January 1 is day 1, which is Wednesday. The number of days elapsed from day 1 to day 74 is 73. Find 73 mod 7: 7 multiplied by 10 equals 70; 73 minus 70 equals 3. Moving 3 days forward from Wednesday: Thursday is 1, Friday is 2, Saturday is 3. March 15 falls on a Saturday.

The answer is False. The multiplicative inverse of a modulo m exists only when gcd(a, m) equals 1. When gcd(a, m) is greater than 1, no integer k satisfies a multiplied by k is congruent to 1 mod m. For example, gcd(4, 6) equals 2, so 4 has no multiplicative inverse modulo 6. No matter what value of k is tried, 4k will always be even and can never leave remainder 1 when divided by 6.

The multiplicative inverse of 5 modulo 13 is the number k such that 5 multiplied by k is congruent to 1 mod 13. Testing k equals 8: 5 multiplied by 8 equals 40. Dividing 40 by 13 gives quotient 3 remainder 1, confirming 40 is congruent to 1 mod 13. So the inverse is 8. This is unique because gcd(5, 13) equals 1. No other value from 1 to 12 satisfies the condition.

From the first condition, x equals 4k plus 1. Substituting into the second: 4k plus 1 is congruent to 2 mod 7, so 4k is congruent to 1 mod 7. The inverse of 4 mod 7 is 2 (since 4 multiplied by 2 equals 8 is congruent to 1 mod 7). So k is congruent to 2 mod 7, meaning k equals 7j plus 2. Substituting back: x equals 4(7j plus 2) plus 1 equals 28j plus 9. The smallest positive solution is x equals 9. Confirming: 9 divided by 4 gives remainder 1, and 9 divided by 7 gives remainder 2.