We know that by the definition of rational numbers, essentially: rationals can be written as $\frac{p}{q}$ for integers $p,q$, $q \neq 0$.
If for some choice they would have a common factor, we could divide it out, with the same quotient (our rational number) remaining, and they would have one factor less in common. As the number of common factors is finite, we have to repeat this at most finitely many times to have a choice of $p$ and $q$ with no common factors.
The proof starts by assuming we have done this step already.
More formally, you could consider the set $A:= \{(n,m) \in \mathbb{N} \times \mathbb{N}: n^2 = 5m^2\}$, and if $\sqrt{5}$ were rational, $A$ would be non-empty (as $\sqrt{5} > 0$ we can pick two positive integers WLOG.)
But $\mathbb{N} \times \mathbb{N}$ is well-ordered in the order $(a,b) < (c,d)$ iff $c < d$ or $c=d$ and $a<b$. (This is just the product of the ordinal $\omega$ with itself in set theory.). Let $(n,m)$ be the minimum of this non-empty set. If $a|n$ and $a|m$ would both hold for some $a > 1$, then $(n',m'):=(\frac{n}{a}, \frac{m}{a}) \in A$ and $(n',m') < (n,m)$, contradicting minimality. This agument can easily be adapted to show any fraction has a unique (modulo the sign of $p,q$, or demand $q>0$) equivalent representation $\frac{p}{q}$ where there is no $a>1$ such that $a|p$ and $a|q$.
Yes, you could instead (uniquely!) write $\,p = 2^j a\,$ and $\,q = 2^k b\,$ for $\,a,b\,$ odd and then deduce a contradiction by comparing the number of factors of $2,\,$ viz. $\,p^2\,$ has an even number of $2$'s but $\,2q^2\,$ has an odd number of $2$'s, a contradiction. This method uses only the very easily-proved existence and uniqueness of $2$-factorizations, i.e. representations of the form $\,2^j n,\,$ with $\,n\,$ odd (versus the much more powerful, and much more difficult to prove Fundamental Theorem of Arithmetic = existence and uniqueness of arbitrary prime factorizations).
As for your second question, yes, every fraction $\,A/B\,$ can be written with coprime numerator and denominator $\,a/b\,$ simply by cancelling their gcd $\,c,\,$ i.e. $\,A/B = ca/cb = a/b.\,$ By the maximality ("greatest") property of the gcd it follows that $\,d =\gcd(a,b) = 1,\,$ else $\,cd\,$ would be a common divisor of $\,A,B\,$ larger than the greatest common divisor $\,c=\gcd(A,B),\,$ contradiction. However, as above, it suffices to cancel only common factors of $\,2,\,$ so no knowledge of gcds is required.
Best Answer
If $13\sqrt{2}$ were rational then it would be of the form $a/b$ for $a,b$ integers ($b\neq 0$). But then $\sqrt{2}=(a/b)/13=a/(13b)$ would be rational.