## Help with prime factorization proof

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
 PhysOrg.com science news on PhysOrg.com >> New language discovery reveals linguistic insights>> US official: Solar plane to help ground energy use (Update)>> Four microphones, computer algorithm enough to produce 3-D model of simple, convex room

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

 b= sab + tpb
Well, you want to know if p divides the LHS of this, and the LHS is equal to the RHS...

 Originally posted by 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
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.

Recognitions:
Homework Help

## Help with prime factorization proof

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[i]?

Recognitions:
Gold Member
 Quote by 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
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.
 Do you enjoy necromancing threads that are months old or something? :P
 Perhaps it's not true?

Recognitions:
Gold Member
 Quote by Muzza Do you enjoy necromancing threads that are months old or something? :P
I hoped I wasn't doing any harm. As for as good, well, I don't know. I thought it added for completeness.
 Oh no, I was just kidding around when I said that.

Recognitions:
Gold Member