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'm currently tackling the following problems:

a) Let $a,b \in \mathbb{Z}$ and let $m$ be a nonnegative integer. Prove that $(a,b)=1$ if and only if $(a^m,b)=1$.

If $(a^m,b)=1$ then $pa^m+qb=1$ for some integers $p$ and $q$. It follows that $(pa^{m-1})a+qb=1$, which shows that $(a,b)=1$. This took care of the ''$\Leftarrow$'' direction. I can't think of a way for the ''$\Rightarrow$'' direction. Can you help me here?

b) In addition to the above, let now $n$ be a nonnegative integer as well. Prove that $(a,b)=1$ if and only if $(a^m,b^n)=1$.

The ''$\Leftarrow$'' direction is completely analogous. How about the ''$\Rightarrow$'' direction?

Edit: Wow, this really wasn't that hard. Here is what I ended up with:

(a) We prove this by contradiction. First assume that $(a,b)=1$ and suppose that $(a^m,b)=d>1$. Then there is a prime $p$ in the prime factorization of $d$ such that $p \mid a^m$ and $p \mid b$. But if $p \mid a^m$, then $p \mid a$, which implies that $p \mid a$ and $p \mid b$, which contradicts the fact that $(a,b)=1$. Thus, $(a^m,b)=1$.

Now assume that $(a^m,b)=1$ and $(a,b)=d>1$. Then we have a prime $p$ such that $p \mid a$ and $p \mid b$, whence $p \mid a^m$ and therefore $p \mid (a^m,b)$, contradiction. Thus, $(a,b)=1$. This completes the proof.

(b) This proof is analogous to the one in (a). Assume that $(a,b)=1$ and suppose that $(a^m,b^n)=d>1$. Then we have a prime $p$ such that $p \mid b^n$ and $p \mid a^n$. But then $p \mid a$ and $p \mid b$, from which it follows that $p \mid (a,b)$, which contradicts our initial assumption. Thus, $(a^m,b^n)=1$.

Now assume that $(a^m,b^n)=1$ and that $(a,b)=d>1$. Then we have a prime $p$ such that $p \mid a$ and $p \mid b$, whence $p \mid a^m$ and $p \mid b^n$. It follows that $p \mid (a^m,b^n)$, contradiction. Thus, $(a,b)=1$. This completes the proof.

share|improve this question
    
This isn't a tough GCD question. You're using an unsuitable definition of $(a,b)=1$ for this question. That's what makes it tough for you. If you use the other definition that you know about $\gcd(a,b)$ you'll see how easy this question is. –  some1.new4u Sep 16 '13 at 4:00

3 Answers 3

up vote 4 down vote accepted

The Bezout Theorem is I think not the best approach. I prefer the approach of some1.new4U.

But Bezout will work. Since $a$ and $b$ are relatively prime, there exist integers $x$ and $y$ such that $ax+by=1$.

Take the $m$-th power of $ax+by$, using the Binomial Theorem. The first term is $a^mx^m$. The remaining terms all have a positive power of $b$ in them, so they add up to $bt$ for some integer $t$.

Thus $a^ms+bt=1$, where $s=x^m$.

share|improve this answer
    
+1 for using the Bézout theorem. However, there is also one more disagreement that I have with using Bézout's theorem for this type of questions by students who are new to number theory. Not only it ruins the fun of practicing number theory theorems and concepts, but also, many students that are new to number theory use Bézout's theorem wrongly. I mean, some people say that because $\exists x_0, \exists y_0: ax_0 + by_0 = d$ then $(a,b)=d$. But they can only conclude that $(a,b) \mid d$. So, it doesn't work if $d>1$ and some students fail to see that at first. –  some1.new4u Sep 16 '13 at 4:31
1  
The OP seems to like using Bezout. I am trying to discourage that somewhat. Sometimes the result is the perfect tool. But at other times it substitutes computation for getting to grips with the problem. –  André Nicolas Sep 16 '13 at 4:43
1  
@some1.new4u: Yup, I fell for that a couple times (assuming $(a,b)=d$ from $a_0+by_0=d$). Amazing use of Bézout :) –  Bo Schmidt Sep 16 '13 at 4:44

HINT: How about thinking this way: $(a,b) \neq 1 \iff (a^m,b) \neq 1$?

So, for example, if $(a^m,b)=d>1$ then you can find a prime number that $p \mid d$, and this is guaranteed by the prime factorization theorem in integers. Now see what happens in this case.

share|improve this answer

This really boils down to two important facts:

$(1)$ If $p$ is prime, then $p\mid ab\implies p\mid a $ or $p\mid b$.

$(2)$ We have $(a,b)>1$ iff there exists a prime $p$ such that $p\mid a $ and $p\mid b$ (, if and only if $p\mid (a,b))$.

Consequently, if $(a^m,b)>1, p\mid a^m\implies p\mid a$, also $p\mid b$ so $p\mid (a,b)$, and $(a,b)>1$. Conversely, if $p\mid (a,b)$ then trivially $p\mid a^m$, thus $p\mid (a^m,b)$.

The other claim's proof is completely analogous. For ease, assume say $n\leqslant m$.

share|improve this answer

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.