if p|ab (a, b whole numbers, p prime), then p|a or p|b

[twisted_logic89]

If a,b are whole numbers and p is a prime number, show that if p|ab, then p|a or p|b

is there a theorem i can use to do this?

 

[stapel]

If a,b are whole numbers and p is a prime number, show that if p|ab, then p|a or p|b

What does it mean for one number to "divide" another number? :wink:

Eliz.

 

[PAULK]

If a,b are whole numbers and p is a prime number, show that if p|ab, then p|a or p|b

is there a theorem i can use to do this?

Well, yes, there is -- this one is a standard number-theory result, which you'll find in any standard text.

HOWEVER, you should be able to prove it using the Fundamental Theorem of Arithmetic -- every whole number can be written as a product of primes in a unique way.

That should do it. If you get stuck, send us your work and we'll try to help.

 

[twisted_logic89]

p| a so we can say that a= jq
p| b so we can say that b=nq

a * b = jq & nq

you can factor out a q from that so you would have q (nj)

p=q(nj)
this shows that n and j are factors of p, therefore if p|ab then p|a and p|b

...?

 

[PAULK]

p| a so we can say that a= jq
p| b so we can say that b=nq

a * b = jq & nq

you can factor out a q from that so you would have q (nj)

p=q(nj)
this shows that n and j are factors of p, therefore if p|ab then p|a and p|b

...?

Does not look right. Try the FT of A like this:

a can be written pa1 pa2 .. pan, where the pai's are the prime factors of a, and there is only one way to do this, aside from reordering the factors.

b can be written pb1 pb2 .. pbm, likewise.

Now ab = pa1 pa2 .. pan pb1 pb2 .. pbm

And we know p | ab, and p is prime. Now can you finish the proof?

 

[o_O]

Or...

Assume \(\displaystyle p \not{\mid} \ a\) and \(\displaystyle p \mid ab\).

Since p does not divide a, it means that they are coprime, i.e. \(\displaystyle (p,a) = 1 \ \iff \ px + ay = 1\) for some \(\displaystyle x,y \in \mathbb{Z}\) (this might be the theorem you're talking about)

Multiply both sides by b: \(\displaystyle pbx + aby = b\)

Since \(\displaystyle p \mid (p)bx\) and \(\displaystyle p \mid (ab)y\) ... Can you conclude?

 

[PAULK]

Or...

Assume \(\displaystyle p \not{\mid} \ a\) and \(\displaystyle p \mid ab\).

Since p does not divide a, it means that they are coprime, i.e. \(\displaystyle (p,a) = 1 \ \iff \ px + ay = 1\) for some \(\displaystyle x,y \in \mathbb{Z}\) (this might be the theorem you're talking about)

Multiply both sides by b: \(\displaystyle pbx + aby = b\)

Since \(\displaystyle p \mid (p)bx\) and \(\displaystyle p \mid (ab)y\) ... Can you conclude?

No, it was not, but this is a nice way to do it.

 

[pka]

Do the prime factorizations of a & b: \(\displaystyle a = \left( {p_1^{j_1 } } \right)\left( {p_2^{j_2 } } \right)\left( {p_3^{j_3 } } \right) \cdots \left( {p_n^{j_n } } \right)\,\& \,b = \left( {p_1^{k_1 } } \right)\left( {p_2^{k_2 } } \right)\left( {p_3^{k_3 } } \right) \cdots \left( {p_m^{k_m } } \right)\).
Now clearly if \(\displaystyle p|ab\) then \(\displaystyle p = p_j ,j = 1, \cdots ,n\mbox{ or }p = p_j ,j = 1, \cdots ,m\)