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*}
latex
To find the least positive four-digit solution to the given system of congruences, we can solve each congruence separately and then find the intersection of the solutions.
1. Solving the congruence $7x\equiv 21 \pmod{14}$:
To solve this congruence, we can simplify the equation by dividing both sides by 7 (since 7 is invertible modulo 14, since $\gcd(7, 14) = 7$).
\begin{align*}
7x &\equiv 21 \pmod{14} \\
\Rightarrow x &\equiv 3 \pmod{14}
\end{align*}
So, the solutions to this congruence are of the form $x \equiv 3 \pmod{14}$.
2. Solving the congruence $2x+13\equiv 16 \pmod{9}$:
To solve this congruence, we can simplify the equation by subtracting 13 from both sides.
\begin{align*}
2x+13 &\equiv 16 \pmod{9} \\
\Rightarrow 2x &\equiv 3 \pmod{9}
\end{align*}
Since 2 and 9 are coprime (since $\gcd(2, 9) = 1$), we can multiply both sides of the congruence by the inverse of 2 modulo 9, which is 5, to find the solution.
\begin{align*}
2x &\equiv 3 \pmod{9} \\
\Rightarrow 5 \cdot 2x &\equiv 5 \cdot 3 \pmod{9} \\
\Rightarrow 10x &\equiv 15 \pmod{9} \\
\Rightarrow x &\equiv 6 \pmod{9}
\end{align*}
So, the solutions to this congruence are of the form $x \equiv 6 \pmod{9}$.
3. Solving the congruence $-2x+1\equiv x \pmod{25}$:
To solve this congruence, we can simplify the equation by adding 2x to both sides.
\begin{align*}
-2x+1 &\equiv x \pmod{25} \\
\Rightarrow -2x+x &\equiv x+x \pmod{25} \\
\Rightarrow -x &\equiv 2x \pmod{25}
\end{align*}
Now, we can add x to both sides to isolate the x term.
\begin{align*}
-x &\equiv 2x \pmod{25} \\
\Rightarrow -x+x &\equiv 2x+x \pmod{25} \\
\Rightarrow 0 &\equiv 3x \pmod{25}
\end{align*}
Since the congruence is divisible by 3, we can divide both sides by 3 (since 3 is invertible modulo 25, since $\gcd(3, 25)=1$).
\begin{align*}
0 &\equiv 3x \pmod{25} \\
\Rightarrow 0 &\equiv x \pmod{25}
\end{align*}
So, the solutions to this congruence are of the form $x \equiv 0 \pmod{25}$.
To find the intersection of the solutions, we need to find a number that satisfies all three congruences simultaneously. We can use the Chinese Remainder Theorem (CRT) to find such a number.
The CRT states that if we have a system of congruences of the form:
\begin{align*}
x &\equiv a \pmod{m} \\
x &\equiv b \pmod{n}
\end{align*}
where $m$ and $n$ are coprime, then the solution can be expressed as $x \equiv M_1aM_1^{-1}+M_2bM_2^{-1} \pmod{m \cdot n}$, where $M_1=m$, $M_2=n$, and $M_1^{-1}$ and $M_2^{-1}$ are the inverses of $M_1$ and $M_2$ modulo $m$ and $n$ respectively.
Applying CRT to the congruences $x \equiv 3 \pmod{14}$ and $x \equiv 6 \pmod{9}$:
\begin{align*}
x &\equiv 3 \cdot 9 \cdot 9^{-1} + 6 \cdot 14 \cdot 14^{-1} \pmod{14 \cdot 9} \\
\Rightarrow x &\equiv 243+588 \pmod{126} \\
\Rightarrow x &\equiv 831 \pmod{126}
\end{align*}
Now, applying CRT to the congruences $x \equiv 831 \pmod{126}$ and $x \equiv 0 \pmod{25}$:
\begin{align*}
x &\equiv 831 \cdot 25 \cdot 25^{-1} + 0 \cdot 126 \cdot 126^{-1} \pmod{126 \cdot 25} \\
\Rightarrow x &\equiv 20775+0 \pmod{3150} \\
\Rightarrow x &\equiv 20775 \pmod{3150}
\end{align*}
Therefore, the least positive four-digit solution to the given system of congruences is $x \equiv 20775 \pmod{3150}$. To find the least positive four-digit solution, we can take $20775 \mod 10000$:
$$20775 \mod 10000 = 775$$
So, the least positive four-digit solution is $x = 775$.