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.

Printable View

- Sep 27th 2008, 08:47 AMzerodigitGCD 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 AMo_O
#1: Since , we can say that for some .

So we're trying to find .

Since and is prime, or ... Can you finish off?

#2:

. Can you conclude? - Sep 27th 2008, 09:22 AMMoo
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:

. Can you conclude?

- Sep 27th 2008, 09:27 AMo_O
Ah whoops, too many prime 's today xD