Find the solution of the congruence 3x ≡ 7 (mod 11)
The Correct Answer and Explanation is:
To solve the congruence 3x≡7(mod11)3x \equiv 7 \pmod{11}3x≡7(mod11), we aim to find an integer xxx that satisfies this congruence. Here are the steps to solve it:
Step 1: Find the inverse of 3 modulo 11
The first step is to find the modular inverse of 3 modulo 11. The modular inverse of 3 is a number yyy such that:3y≡1(mod11)3y \equiv 1 \pmod{11}3y≡1(mod11)
To find yyy, we can use the Extended Euclidean Algorithm. We need to find integers yyy and kkk such that:3y−11k=13y – 11k = 13y−11k=1
Perform the Euclidean algorithm to find the greatest common divisor (gcd) of 3 and 11:11=3×3+2(divide 11 by 3)11 = 3 \times 3 + 2 \quad \text{(divide 11 by 3)}11=3×3+2(divide 11 by 3)3=2×1+1(divide 3 by 2)3 = 2 \times 1 + 1 \quad \text{(divide 3 by 2)}3=2×1+1(divide 3 by 2)2=1×2+0(divide 2 by 1, remainder 0, so gcd is 1)2 = 1 \times 2 + 0 \quad \text{(divide 2 by 1, remainder 0, so gcd is 1)}2=1×2+0(divide 2 by 1, remainder 0, so gcd is 1)
Now, work backwards to express 1 as a linear combination of 3 and 11:1=3−1×21 = 3 – 1 \times 21=3−1×2
Substitute 2=11−3×32 = 11 – 3 \times 32=11−3×3:1=3−1×(11−3×3)1 = 3 – 1 \times (11 – 3 \times 3)1=3−1×(11−3×3)1=3−1×11+3×31 = 3 – 1 \times 11 + 3 \times 31=3−1×11+3×31=4×3−1×111 = 4 \times 3 – 1 \times 111=4×3−1×11
Thus, the inverse of 3 modulo 11 is 444, because 4×3≡1(mod11)4 \times 3 \equiv 1 \pmod{11}4×3≡1(mod11).
Step 2: Multiply both sides of the congruence by 4
Now that we know the inverse of 3 modulo 11 is 4, we multiply both sides of the congruence 3x≡7(mod11)3x \equiv 7 \pmod{11}3x≡7(mod11) by 4:4×3x≡4×7(mod11)4 \times 3x \equiv 4 \times 7 \pmod{11}4×3x≡4×7(mod11)12x≡28(mod11)12x \equiv 28 \pmod{11}12x≡28(mod11)
Since 12≡1(mod11)12 \equiv 1 \pmod{11}12≡1(mod11), we simplify the left-hand side:x≡28(mod11)x \equiv 28 \pmod{11}x≡28(mod11)
Now, reduce 28 modulo 11:28÷11=2 remainder 628 \div 11 = 2 \text{ remainder } 628÷11=2 remainder 6
So, 28≡6(mod11)28 \equiv 6 \pmod{11}28≡6(mod11).
Thus, the solution to the congruence is:x≡6(mod11)x \equiv 6 \pmod{11}x≡6(mod11)
Final Answer:
The solution to 3x≡7(mod11)3x \equiv 7 \pmod{11}3x≡7(mod11) is x≡6(mod11)x \equiv 6 \pmod{11}x≡6(mod11). Therefore, x=6x = 6x=6 is the smallest non-negative solution, and any integer xxx of the form x=6+11kx = 6 + 11kx=6+11k, where kkk is any integer, is also a solution.
