# 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?

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

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

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.

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

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

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