Help with prime factorization proof

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

Hurkyl

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...

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.

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

robert Ihnot

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.

Muzza

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

Sariaht

Perhaps it's not true?

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.

Muzza

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

HallsofIvy

Perhaps WHAT'S not true?