gcd(a,b)=d then show that gcd(a/d,b/d)=1 (without euclids lemma or bezout's theorem) I was solving the problem $\gcd(a,b)=d$ then show that $\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1$ (without Euclid's lemma or Bézout's theorem) then stumbled upon the fact that if we say
$$\gcd\left(\frac{a}{d},\frac{b}{d}\right)= k \tag{1}$$
then $a=kdn$ and $b=kdm$ then,
$$\gcd(a,b)=\gcd(m,n) \, kd \tag{2}$$
but I seem to not be able to prove that $(1)$ holds. If this holds then from this it’s clear that $d = \gcd(m,n)\,kd$ then $\gcd(m,n) = \frac{1}{k}$
Since $k$ is an integer and $\gcd(m,n)$ is also an integer then only value of $k$ that satisfies such a relation is $k = 1$ then by $(1)$ our question is answered.
So the question here is if two numbers $a = A \cdot B$ and $b = M \cdot N$, then
is it true that,
$$\gcd(a,b) = \gcd(A,M) \cdot \gcd(B,N)?$$
Let $a,b&gt;0$, $d=(a,b)$. Let $a'=ad^{-1},b'=bd^{-1}$. Suppose that $e\mid a',b'$. Then $de\mid a,b$, so $de\mid (a,b)=d$. This means $e\mid 1$. It follows that $(a',b')=1$.
Proof: Before starting with the proof proper, we should observe that although a/d and b/d have the appearance of the functions, in fact, they are integers because d is a divisor both of a and of b. Now, knowing that gcd(a, b) = d, it is possible to find integers x and y such that d = ax + by. Upon dividing each side of this equation by d, we obtain the expression 
1 = (a/d)x + (b/d)y
Because a/d and b/d are integers, an appeal to the theorem is legitimate. The conclusion is that a/d and b/d are relatively prime.   (Proved)