Help with prime factorization proof

1. Feb 29, 2004

Ed Quanta

I have to prove that if ab is divisible by the prime p, and a is not divisible by p, then b is divisible by p.

In order to prove this, I have to show (a,p)=1. I am not sure what this statement means.

Then I am supposed to use the fact that 1=sa + tp when s,t are elements of the set of integers. (This statement was already proved in class). Then I figured to multiply across by b so that we get

b= sab + tpb. I am not sure where to from here. I have not seen to many proofs regarding prime factorization. Thanks

Ed

2. Feb 29, 2004

Hurkyl

Staff Emeritus
This means "The greatest common divisor of a and p is 1". You may have sometimes seen this written as gcd(a, p) = 1.

Well, you want to know if p divides the LHS of this, and the LHS is equal to the RHS...

3. Mar 1, 2004

Sariaht

If ab has a factor p and a don't, then b has the factor. That's logic.

If a = c + id and b = e - id, it's a bit harder.

Last edited: Mar 1, 2004
4. Mar 1, 2004

matt grime

Every result in maths is 'just logic', surely.

To show there is some content, consider Z{sqrt(5)]

2 is prime

2 divides 4=(sqrt5 - 1)(sqrt 5 +1)

2 divides neither of the terms on the left as they are both prime too.

so it important that the division algorithm works in Z. Or was that reference to x+iy some indiction of something in the ring Z?

Last edited: Mar 1, 2004
5. Jul 5, 2004

robert Ihnot

You are almost finished.

Since you have already arrived at b=sab +tpb, we know that p divides tpb, and p divides sab so that p divides b.

If there seems a need here for steps, we can look at p(sab/p +tb) =b. Since we know (sab/p +tb) is an integer, we see that b contains the factor p.

Last edited: Jul 6, 2004
6. Jul 6, 2004

Muzza

Do you enjoy necromancing threads that are months old or something? :P

7. Aug 4, 2004

Sariaht

Perhaps it's not true?

8. Aug 5, 2004

robert Ihnot

I hoped I wasn't doing any harm. As for as good, well, I don't know. I thought it added for completeness.

9. Aug 6, 2004

Muzza

Oh no, I was just kidding around when I said that.

10. Aug 6, 2004

HallsofIvy

Perhaps WHAT'S not true?