Proofing a Prime Number: A Guide

  • Thread starter liangiecar
  • Start date
  • Tags
In summary, the conversation discusses the proof for a prime number p being a factor of a non-zero product of integers a*b, using the fundamental theorem of arithmetic and the unique decomposition of integers into prime factors. The conversation also mentions the need for rigor in writing out the proof and the use of Euclid's lemma.
  • #1
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.
Physics news on
  • #2
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
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.
  • #5
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
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.

What is a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. In other words, it has exactly two factors.

Why is proving a number to be prime important?

Proving a number to be prime is important because prime numbers are the building blocks of all other numbers. They have many applications in mathematics and computer science, such as in cryptography and number theory.

What is the process of proofing a prime number?

The process of proofing a prime number involves using various mathematical techniques to show that the number is indeed prime. This may include using divisibility rules, prime factorization, or advanced mathematical concepts like the Sieve of Eratosthenes or the Fundamental Theorem of Arithmetic.

What are some common misconceptions about prime numbers?

One common misconception about prime numbers is that they are all odd. While it is true that most prime numbers are odd, there are also some that are even, such as 2. Another misconception is that 1 is a prime number, when in fact it is not. Additionally, many people believe that all prime numbers are rare, but in reality, there are infinitely many prime numbers.

Are there any unsolved problems related to prime numbers?

Yes, there are many unsolved problems related to prime numbers, such as the Twin Prime Conjecture, Goldbach's Conjecture, and the Riemann Hypothesis. These problems have puzzled mathematicians for centuries and continue to be areas of active research.

Suggested for: Proofing a Prime Number: A Guide