View Full Version : Help with prime factorization proof
Ed Quanta
Feb29-04, 01:43 PM
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
(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.
matt grime
Mar1-04, 12:17 PM
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
Jul6-04, 12:59 AM
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
robert Ihnot
Aug5-04, 11:13 PM
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.
HallsofIvy
Aug6-04, 09:10 AM
Perhaps it's not true?
Perhaps WHAT'S not true?
vBulletin® v3.7.6, Copyright ©2000-2009, Jelsoft Enterprises Ltd.