How to Proof?

  • Thread starter liangiecar
  • Start date
  • #1

Main Question or Discussion Point

How to proof?
A prime number p is a factor of a non-zero product of integers a*b if and only if it is a facotr of a and/or b.
 

Answers and Replies

  • #2
97
0
The "if" direction is obvious. For the "only if", you need to use the fundamental theorem of arithmetic. Because a*b has a unique prime decomposition, if a prime p divides a*b then it must be one of the primes in the decomposition. The prime decomposition of a*b is just the product of the decompositions of a and b, so p must divide a and/or b.

This sounds like a homework question! In which case you will need to be a lot more rigorous when you write it out.
 
Last edited:
  • #3
CompuChip
Science Advisor
Homework Helper
4,302
47
One side is trivial: if p is a factor of a and/or b, then it is clearly a factor of a * b.

For the converse implication, the easiest way I can think of is using the unique decomposition of any integer into its prime factors.
 
  • #4
thx,guys
 
  • #5
607
0
Caution. Some proofs of unique factorization may use this property of primes. And then it would be illegitimate to use unique factorization in the proof of this...
 
  • #6
crd
14
0
assume p is a factor of ab. then p|ab. since p is prime, euclid's lemma says p|a and/or p|b, thus p is a factor of a and/or b.
 

Related Threads on How to Proof?

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
10
Views
1K
Replies
2
Views
4K
Replies
3
Views
1K
Replies
10
Views
1K
Replies
1
Views
3K
Top