FindCoprimeAB

Let $d=\gcd(a,c)$ and $e=\gcd(b,c)$. Then $\gcd(a/d, c/d)=\gcd(b/d,c/d)=\gcd(d,e)=1$. By Dirichlet's theorem on arithmetic progressions, there are infinitely many primes in each of the lists $$ \frac ad,\,\frac ad+\frac cd,\,\frac ad+\frac {2c}d,\,\dots, $$ and $$ \frac be,\,\frac ae+\frac be,\,\frac be+\frac {2c}e,\,\dots. $$ Pick a prime $p=\frac ad+\frac {kc}d$ in the first list such that $\gcd(p,e)=1$, and then a prime $q=\frac be+ \frac {hc}e$ in the second list with $p\not=q$ and $\gcd(q,d)=1$. Then $a'=pd\equiv a\pmod c$, $b'=qe\equiv b\pmod c$, and $\gcd(a',b')=1$ as required. This shows that such $a'$ and $b'$ exist.

Checking if $p$ and $q$ are primes could be hard. In reality, one may simply pick any $u$ from the first list with $\gcd(u,e)=1$. This is easily done with the help of the Euclidean Algorithm. Then switch to the second list to find $v$ with $\gcd(v,d)=\gcd(v,u)=1$ (again with the help of the Euclidean Algorithm). Set $a'=ud$ and $b'=ve$ and we are done.