1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

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