<s>[INST] How do I simplify a modular congruence? If I have $$13x\equiv 15 \pmod{35}$$ or something like $$197x\equiv -1 \pmod{371}$$
How do I go about making the coefficient of the $13x$ and $197x$ $1$? Brute forcing this would take far too long. I know that you can use the Extended Euclidean Algorithm and Modular Inverses to solve, but I am unsure how.
 [/INST] Assuming you don't know how to use modular inverses (which is the way to do this and you should learn it) you can do it just be setting up equations
$13x \equiv 15 \pmod {35}$ means there exists an integer $m$ so that $13x =15 + 35m$ so $x = \frac{15 + 35m}{13}= 1 + 2m +\frac {2+9m}{13}$.
This means that $13|2+9m$ so $2+9m\equiv 0\pmod {13}$ and so $9m\equiv -2 \equiv 11\pmod {13}$.
That means there is an integer $n$ so that $9m = 11 + 13n$ and $m=\frac {11+13n}9=(n+1) + \frac {2+4n}9$.
That means $4n \equiv -2\equiv 7\pmod 9$.  Let $4n = 7 +9p$ so $n = \frac {7+9p}4 =(2p+1) + \frac{3+p}4$.
That means $p\equiv -3 \equiv 1\pmod 4$.
Let $p = 4z + 1$.
So $n = (2p+1) + \frac{3+p}4 = (2(4z+1)+1) + \frac {4z + 4}4 = 8z+3 + z + 1 =9z + 4$.
So $m =(n+1) + \frac {2+4n}9 = (9z+5) + \frac {2+4(9z+4)}9=(9z+5)+\frac{18+4\cdot 9z}9=(9z+5) + 2+4z = 13z +7$
So $x = 1 + 2m +\frac {2+9m}{13}= 1+2(13z +7) + \frac {2+9(13z+7)}{13}=(26z+15)+\frac {65 + 9\times 13z}{13}=(26z+15)+(5+9z)=20+35z$.
So $x \equiv 20 \pmod {35}$.
</s>