# Math Help - GCD questions

1. ## GCD questions

1.Let a be an integer and p be a positive integer. Prove that if p divides a, then
GCD(a,p)=p.

2.Show that if GCD(a, c)=1 and c divides ab, then c divides b.

2. #1: Since $p \mid a$, we can say that $a = kp$ for some $k$.

So we're trying to find $d = (p, kp)$.

Since $d \mid p$ and $p$ is prime, $d = 1$ or $d = p$... Can you finish off?

#2:
$(a,c) =1 \ \Rightarrow \ ax + cy = 1 \ \iff \ abx + cby = b$. Can you conclude?

3. Originally Posted by o_O
#1: Since $p \mid a$, we can say that $a = kp$ for some $k$.

So we're trying to find $d = (p, kp)$.

Since $d \mid p$ and $p$ is prime, $d = 1$ or $d = p$... Can you finish off?
Huh.. It is not said that p is a prime integer..

__________________________________________________
Let d=gcd(a,p). We can say, in particular, that d divides p.
Since p divides both p (obvious) and a (because a is a multiple of p), we can say that p divides the gcd of a and p, that is d.

d | p and p | d
Hence p=d.

#2:
$(a,c) =1 \ \Rightarrow \ ax + cy = 1 \ \iff \ abx + cby = b$. Can you conclude?
Note that the first $\Rightarrow$ can be an equivalence

4. Ah whoops, too many prime $p$'s today xD