# Find the greatest common divisor of $n$ and $\frac{n}{d}$

Could anyone help me to prove this basic result in elementary number theory?

Let $$n,d$$ be two natural numbers with $$n\geq 2$$ and $$d \mid n$$, prove that

$$\gcd(n,\frac{n}{d}) = \frac{n}{d}$$

It seems vary basic but I am really stuck!

I know many basic theorems of number theory that might be helpful (like Bézout's lemma), but I have no idea how to proceed with the proof.

Through a contradiction? maybe a straight proof?

We used this in class, with out any further explanation, in order to prove a theorem in group theory, and I really need to understand that step.

Thank you.

• First show that $\frac{n}{d}$ is a divisor of $n$ and a divisor of $\frac{n}{d}$. Next show that it is the greatest common divisor of $n$ and $\frac{n}{d}$ (there's really nothing to show here - nothing greater than $\frac{n}{d}$ can divide $\frac{n}{d}$). – kccu Dec 8 '15 at 22:19

Well, go back to definitions.

n/d divides n/d and it divides n. (d*n/d = n). So n/d is a common divisor. If x > n/d then x is not a divisor of n/d (divisors have to be smaller) so n/d is the greatest common divisor.

In light of marty cohen's answer. Note: gcd(m, a*m) = m always as m|m and m|a*m so m|gcd(m, a*m) and gcd(m,a*m)|m so m|gcd and gcd|m $\implies$ m = gcd(m, a*m).

If $m = gcd(n, n/d)$ then (1) $n/d\ |\ m$ since $n/d$ divides both $n$ and $n/d$; (2) $m\ |\ n/d$ since $gcd(a, b)$ divides both $a$ and $b$.

Therefore $m = n/d$.

$\frac{n}{d}$ is just a number c that c|n. And obviously that gcd(n,c)=c for every c|n

Note that if $d\mid n$ then $n=d.m$ with m integer and then $m\mid n$. Finally, $gdc(n,m)=m$