+266 For everybody to know the answer is not 2877. Please give me the solution if you can and not just the answer.
Find the least positive four-digit solution to the following system of congruences.
\(\begin{align*} 7x &\equiv 21 \pmod{14} \\ 2x+13 &\equiv 16 \pmod{9} \\ -2x+1 &\equiv x \pmod{25} \\ \end{align*}\)
Computer program:
for (n = 1000..9999)
if (7*n % 14 == 21 && 2*n + 13 % 16 == 9 && -2*n + 1 % 25 == n) {output(n);}
1041, 1491, 1941, 2391, 2841, 3291, 3741, 4191, 4641, 5091, 5541, 5991, 6441, 6891, 7341, 7791, 8241, 8691, 9141, 9591
The smallest solution is 1041.
The congruence 7x≡21(mod14) is the same as
x≡3(mod2)
The congruence 2x+13≡16(mod9) is the same as 2x≡3(mod9) and therefore to
x≡15(mod9)
because 2⋅5≡1(mod9)
The congruence −2x+1≡x(mod25) is the same as 3x≡1(mod25) and therefore to
x≡17(mod25)
because 3⋅17≡1(mod25)
Thus you have
x≡1(mod2)
x≡6(mod9)
x≡17(mod25)
The first one tells you that x=2a+1 for some integer a . Thus we need
2a+1≡6(mod9)
so 2a≡5(mod9) and therefore
a≡25≡7(mod9)
Hence a=9b+7 for some integer b. Now we have
x=2a+1=2(9b+7)+1=18b+15
and so we need
18b+15≡17(mod25)
so 9b≡1(mod25)
Multiplying by 3 we have 27b≡3(mod25) , so 2b≡28(mod25) and finally
b≡14(mod25)
Thus b=25c+14 and
x=18(25c+14)+15=450c+267
In order to get a four digit number we need
450c+267>999
hence c>122/75 , so c=2 is the least integer and we get
450⋅2+267=1167 - is the smallest 4-digit integer.
+266 Divide the first congruence by 7, remembering to divide 14 by as well. We find that the first congruence is equivalent to . Subtracting 13 from both sides and multiplying both sides by 5 (which is the modular inverse of 2, modulo 9) gives for the second congruence. Finally, adding to both sides in the third congruence and multiplying by 17 (which is the modular inverse of 3, modulo 25) gives . So we want to solveLet's first find a simultaneous solution for the second and third congruences. We begin checking numbers which are 17 more than a multiple of 25, and we quickly find that 42 is congruent to 17 (mod 25) and 6 (mod 9). Since 42 does not satisfy the first congruence we look to the next solution . Now we have found a solution for the system, so we can appeal to the Chinese Remainder Theorem to conclude that the general solution of the system is , where 450 is obtained by taking the least common multiple of 2, 9, and 25. So the least four-digit solution is .
