+537 Find the least positive four-digit solution to the following system of congruences.
\(7x \equiv 21 \pmod{14} \)
\(2x+13 \equiv 16 \pmod{9} \)
\(-2x+1 \equiv x \pmod{25} \)
+532 from the first one, you can see that x is odd.
now you do the second one.
this means 2x leaves a remainder of 3 when divided by 9.
this means x is a multiple of 3.
now, 3x divided by 25 leaves remainder of 1 from the third one.
now you do guess and check and see tht the first x is 17, the next is 42, the next is 67, and on and on
this means that the number when divided by 25 leaves remainder 17, and that it is odd.
2x is remainder of 3 when divided by 9, so the first one would be 42, then adding 225 because of 25 and 9, so then it would be 942 would be one, then 1167. you can double check and it all works.
HOPE THIS HELPED!
+6248 There is a more formal method to solving this problem.
First let's reduce these congruences.
\(7x \equiv 21 \pmod{14}\\ x \equiv 3 \pmod{2}\\ x \equiv 1 \pmod{2}\)
--------------------------------
\(2x+13 \equiv 16 \pmod{9}\\ 2x \equiv 3 \pmod{9}\\ \text{now we multiply both sides by the multiplicative inverse of }2 \pmod{9}\\ 5\cdot 2x \equiv 5\cdot 3 \pmod{9}\\ x \equiv 6 \pmod{9}\)
---------------------------------
\(-2x + 1 \equiv x \pmod{25}\\ 3x \equiv 1 \pmod{25}\\ 17\cdot 3x \equiv 17 \pmod{25}\\ x \equiv 17 \pmod{25}\)
\(\text{Now we have the following system of linear congruences}\\ x \equiv 1 \pmod{2}\\ x \equiv 6 \pmod{9}\\ x \equiv 17 \pmod{25}\)
\(\text{From the first congruence we have}\\ x = 2t+1,~t \in \mathbb{Z}\\ \text{substitute this into the second congruence}\\ 2t+1 \equiv 6 \pmod{9}\\ 2t\equiv 5 \pmod{9}\\ 5\cdot 2t \equiv 5\cdot 5 \pmod{9}\\ t \equiv 7 \pmod{9}\\ t = 9s+7,~s \in \mathbb{Z}\)
\(\text{substitute this back into }x \text{ and simplify}\\ x = 2(9s+7)+1\\ x = 18s + 14+1 = 18s+15\)
\(\text{Now we substitute this into the third congruence}\\ 18s+15 \equiv 17 \pmod{25}\\ 18s \equiv 2 \pmod{25}\\ \text{Now we have to find }18^{-1} \pmod{25},\text{ with these small numbers trial and error works}\\ 18^{-1}\pmod{25} = 7\\ 7\cdot 18 s \equiv 14 \pmod{25}\\ s \equiv 14 \pmod{25}\\ s = 25u+14,~u\in \mathbb{Z}\)
\(\text{and we substitute this back into }x\\ x = 18(25u+14)+15 = 267+450u\\ x \equiv 267 \pmod{450}\\ \text{The smallest 4 digit solution will be}\\ x = 2\cdot 450 + 267 = 1167\)
