**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*}\)

Imcool Dec 24, 2022

#1**-1 **

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.

Guest Dec 24, 2022

#3

#5**+2 **

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.**

Guest Dec 24, 2022

#4**+1 **

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 .

Imcool Dec 24, 2022