# GCD questions

• Sep 27th 2008, 08:47 AM
zerodigit
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.
• Sep 27th 2008, 09:16 AM
o_O
#1: Since \$\displaystyle p \mid a\$, we can say that \$\displaystyle a = kp\$ for some \$\displaystyle k\$.

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

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

#2:
\$\displaystyle (a,c) =1 \ \Rightarrow \ ax + cy = 1 \ \iff \ abx + cby = b\$. Can you conclude?
• Sep 27th 2008, 09:22 AM
Moo
Quote:

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

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

Since \$\displaystyle d \mid p\$ and \$\displaystyle p\$ is prime, \$\displaystyle d = 1\$ or \$\displaystyle 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.

Quote:

#2:
\$\displaystyle (a,c) =1 \ \Rightarrow \ ax + cy = 1 \ \iff \ abx + cby = b\$. Can you conclude?
Note that the first \$\displaystyle \Rightarrow\$ can be an equivalence :)
• Sep 27th 2008, 09:27 AM
o_O
Ah whoops, too many prime \$\displaystyle p\$'s today xD