Given $d,d'$ are in $\mathbb{Z} > 1$, and $\gcd(d,d')=1$, and $d \mid n$ and $d'\mid n$,

Show that $d\cdot d'\mid n$.

I pretty much have it but I think it could be made more clear. I have:

$d \mid n$ so $n=q*d$ and $d'\mid n$ so $n=q'*d'$

So $q*d*q'*d'=n^2$

So $(q*d*q'*d')/n=n$

So $(q*q'/n)*(d*d')=n$ ... so the only thing left to do is show that $q*q'/n$ must be an integer.

I think it has something to do with $\gcd(d,d')=1$ because $d$ and $d'$ cannot both divide an integer $n$ unless $n$ is a multiple of $d*d'$, but I'm not sure how to show this elegantly.



Hint: since $\gcd(d, d') = 1$, there exist $\alpha, \beta \in \mathbb{Z}$ such that $\alpha d + \beta d' =1$. Now multiply both sides by $n$, and use the fact that $d \mid n$ and $d' \mid n$. Feel free to comment if you need further clarification!


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.