0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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}$). $\endgroup$ – kccu Dec 8 '15 at 22:19
1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.