# Proof...having trouble in one direction.

• Feb 21st 2010, 05:04 AM
Proof...having trouble in one direction.
1) Let p be prime, m be a positive integer
Show that if a is an integer, then gcd(a,p^m)=/=1 if and only if p divides a.

I think I got the first way:
So first I suppose the gcd (a,p^m)=/=1. So a and p^m have a common factor greater than one. Call it k. So k divides p^m and k divides a. Since k divides p^m, k divides p. So p=lk for some integer l and a=mk for some integer m. So k=p/l means a=m(p/l)=p(m/l), and since m/l is an integer, p divides a.

For the second way, I started, but got stuck, and maybe it is all wrong:

Now suppose p divides a. Then a=mp for some integer m. Suppose that gcd(a,p^m)=1. Then a and p^m have no common factors besides 1. Stuck. Thanks
• Feb 21st 2010, 08:37 AM
Black
Quote:

But how can this be true if $p$ is prime?
If $\text{gcd}(a,p^m)=k>1$, then $k|p^m \Longrightarrow k=p^n$ for $n \le m$. Therefore, $p|k \Longrightarrow p|a.$
If $p|a,$ then $\text{gcd}(a,p)=p.$ So $\text{gcd}(a,p^m) \ge p.$