+0

-1
63
6
+115

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

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.

Dec 24, 2022
#2
+115
-2

oh thanks

Dec 24, 2022
#3
+115
-1

Wait no its 1167

Dec 24, 2022
#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
+115
+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 .

Dec 24, 2022