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