If $\gcd(n,18)=3$ then $\gcd(n^2,18)=9$ Rest of the problem is fairly obvious. If $\gcd(n,18)=3$ then $3$ divides $n$ so there exists $a$ such that $3a=n$. Squaring both sides gets us $9a^2=n^2$ so we get $9 \mid n^2$. Obviously $9$ divides $18$ so we know that $9$ is a common factor. I am having problems proving that $9$ is the $\gcd$ though. If I assume $c \mid n^2$ and $c \mid 18$, then $c \mid n^2 + 18$ and substituting $3a=n$ I get $c \mid 9(a^2+2)$ but I don't know where to go from here. Another angle I thought of is that since the only bigger factor of $18$ is $18$ itself, I could try to prove that if $18 \mid n^2$, then $\gcd(n,18)$ isn't $3$. It seems that $18$ divides a square only if $6 \mid n$ so $\gcd(n,18)$ would be $6$. But I am not sure why that is. Any help?
 A: You have already shown that $9$ is a divisor of both $n^2$ and $18$.
The only number larger than $9$ that divides $18$ is $18$. But if $18$ divides $n^2$ then $n$ is even so $\text{gcd}(n,18)$ would have to be greater than or equal to $6$. Therefore, $\text{gcd}(n^2,18)=9$.
A: Hint Since $9| \gcd(n^2,18)$ and $\gcd(n^2,18) |18$ you get that $\gcd(n^2,18) \in  \{ 9, 18 \}$. All you have to do is argue that 
$$\gcd(n^2,18) \neq 18$$
A: It's simple: if $\gcd(n,18)=3$, $n$ is odd (otherwise, $\gcd(n,18)=6$), so $n^2$ is odd, and $\gcd(n^2,18)$ can't be $18$, which is even.
A: If $\gcd{(n,18)}=3$, then $n=3\cdot p_1^{k_1}\cdot p_2^{k_2} \cdot\cdot\cdot p_n^{k_n}$ for some primes $p_1$, $p_2$, ... , $p_n \ne2,3$. 
$$\therefore n^2=3^2\cdot p_1^{2k_1}\cdot p_2^{2k_2} \cdot\cdot\cdot p_n^{2k_n}$$
$$\gcd{(n^2,18)}=\gcd{(3^2\cdot p_1^{2k_1}\cdot p_2^{2k_2} \cdot\cdot\cdot p_n^{2k_n},18)}$$
$$=9$$
A: Hint $\ \  \overbrace{ (n,18)\!=\!3}^{\Large \Rightarrow\,\color{#c00}{(n,\,6)\ =\ 3}\ \ \ \ }\!\!\!\!\!\Rightarrow\, (n^2,\,6\cdot 3) = 3^2\,\ $ via
Lemma $\ \color{#c00}{(n,a) = b}\,\Rightarrow\, (n^2,\ a\cdot b) = b^2$
Proof  #$\bf 1$ $\,\ \ b^2 = (n,a)^2 = (nn,an,aa) = (nn,a\color{#c00}{(n,a)}) = (n^2,a\,\color{#c00}b)$
Proof  #$\bf 2$ $\,\ \ (n/b,a/b)=1\,\Rightarrow\, ((n/b)^2,a/b)=1\!\underset{\large \times\ b^2}\Rightarrow (n^2,ab)=b^2$
A: Euclid lemma.  If $p $ is a prime divisor of $n^2$ then $p|n $.  But the only prime that divides $n $ and $18$ is $3$.  So $\gcd(n^2,18)=3^k $.  So $\gcd $ is $9$.
Also... the only divisors of $18=2*3^2$ are $2^a3^b$.  Can't have $2|n $ so ....
