Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was looking back at my notes on number theory and I came across this question.

Let $a$, $b$ be positive integers such that $\gcd(a, b) = 3$. What are the possible values for $\gcd(a^2, b)$?

I know it has to do with their prime factorization decomposition, but where do I go from here?

share|improve this question
add comment

5 Answers

up vote 5 down vote accepted

If $p$ is a prime, and $p|a^2$, then $p|a$; thus, if $p|a^2$ and $p|b$, then $p|a$ and $p|b$, hence $p|\gcd(a,b) = 3$. So $\gcd(a^2,b)$ must be a power of $3$.

Also, $3|a^2$ and $3|b$, so $3|\gcd(a^2,b)$; so $\gcd(a^2,b)$ is a multiple of $3$.

If $3^{2k}|a^2$, then $3^k|a$ (you can use prime factorization here); so if $3^{2k}|\gcd(a^2,b)$, then $3^k|\gcd(a,b) = 3$. Thus, $k\leq 1$. That is, no power of $3$ greater than $3^2$ can divide $\gcd(a^2,b)$.

In summary: $\gcd(a^2,b)$ must be a power of $3$, must be a multiple of $3$, and cannot be divisible by $3^3=27$. What's left? Now give examples to show all of those possibilities can occur.

share|improve this answer
add comment

HINT: write out the prime factorization of a and that of b. Divisors of a are products of the primes in the prime factorization of a. Same for b. since gcd(a,b)=3, then a and be share a $3^{1}$ in their prime factorization. What happens when you square a number? You end up squaring all the primes, including the 3.

share|improve this answer
    
I see that all the primes get squared for a when a is squared. But how would that change the GCD from 3? –  Dominick Gerard Feb 23 '12 at 22:24
    
@DominickGerard: Check the edit I added to my answer, it should make things clearer. –  savick01 Feb 24 '12 at 9:46
add comment

There exist integers $x$ and $y$ such that $ax+by=3$. Square both sides. Then $$a^2 x^2+b(2axy+by^2)=9,$$ and therefore $\gcd(a^2,b)$ divides $9$. Finally, show that $1$ cannot happen, but $3$ and $9$ can.

share|improve this answer
    
Remark $\:$ This is just a Bezout form of the first proof I gave, i.e. it proves $(a^2,b)\:|\:(a,b)^2$ not by gcd laws but, rather, by writing the gcd in Bezout form $\:(a,b) = ax+by,\:$ which yields $$(a^2,b)\ |\ a^2,b\ \ \Rightarrow\ \ (a^2,b)\:|\:a^2x^2 + b\:(2axy+b^2x^2) = (ax+by)^2 = (a,b)^2$$ Using gcd laws yields a more general proof, since the proof works in any domain with gcds, e.g. it works in non-PID UFDs such as $K[x,y]$, where the Bezout proof fails. –  Math Gems Feb 23 '12 at 23:16
    
@Math Gems: My opinion is that dealing directly with common divisors, like you did, is better. Just wanted to mention the linear combination idea to add to the mix. –  André Nicolas Feb 23 '12 at 23:16
    
Yes, the Bezout proof is more accessible to those not fluent in gcd laws. It's instructive to compare the two proofs. Hence my above remark. –  Math Gems Feb 23 '12 at 23:19
add comment

Hint $\rm\: \ (a,b)\ |\ (a^2,b)\ |\ (a,b)^2\ $ since $\rm\ (a^2,b)\ |\ a^2,ab,b^2\ \Rightarrow\ (a^2,b)\ |\ (a^2,ab,b^2) = (a,b)^2 $

Therefore $\rm\:3\ |\ (a^2,b)\ |\ 9\:$ when $\rm\:(a,b) = 3\ \ $ QED

Or: $\:$ let $\rm\:a = 3^K A,\:\ b = 3^N B,\ \ 3\nmid A,B.\ \ $ $\rm(a,b)=3\ \Rightarrow \ (A,B) = 1\:$ and $\rm\:\min(K,N) = 1.\:$ Thus

$$\rm (a^2,b) = (3^{2K} A^2, 3^N B) = (3^{2K},3^N)(A^2,B) = (3^{2K},3^N) = 3\: \ if\: \ N\! =\! 1\: \ else \ 9\ ( N \ge 2\Rightarrow K = 1)$$

share|improve this answer
add comment

We know that among all the divisors of $b$, only 3 divides $a$. There are two cases: 1) 3 divides $b$ only one time xor 2) 3 divides $a$ only one time (and $b$ more then once!). 1) $GCD(a^2,b)$ is 3. 2) 3 divides $a^2$ two times, so $GCD(a^2,b)$ is $3^2=9$.

EDIT: I think I need to add the general law, which is extensively used here and enables short reasonings. Let $\{ p_i\}$ be the set of all the prime divisors of $a$ or $b$. Then we have:

If $a=\prod_{i=1}^n p_i^{q_i},\ b=\prod_{i=1}^n p_i^{r_i}$ (some of $q_i,\ r_i$ might be equal to zero), then $$GCD(a,b) = \prod_{i=1}^n p_i^{min(r_i,q_i)}.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.