0

The greatest common divisor of a natural number $n$ and $90$ equals 18. The GCD of $n$ and $120$ equals 12. How can I find the GCD of $n$ and $900$?

student28
  • 385
  • 4
    You can write $n=2^a3^b5^cd$ where $\gcd(d,30)=1$, and find as much information as you can about $a,b,c$, and then use it to solve the problem. Try it! – Gerry Myerson Sep 14 '17 at 07:46

1 Answers1

1

\begin{align} \gcd(n,90)=18 &\implies n=18p \\ &\implies \gcd(p,5)=1 \end{align}

\begin{align} \gcd(n,120)=12 &\implies n=12q \\ &\implies \gcd(q,10)=1 \\ &\implies \gcd(q,2)=\gcd(q,5)=1 \end{align}

\gcd(n,900) = \gcd(18p, 900) = 18 \gcd(p, 50) = 18 \gcd(p,2) \in {18, 36}$

$\gcd(n,900) = \gcd(12q, 900) = 12 \gcd(q, 75) = 12 \gcd(q,3) \in \{12, 36\}$

So $\gcd(n,900) = 36$

Steven Alexis Gregory
  • 26,769