Proving the Primality of a Natural Number with Divisibility Property

In summary, the question is asking to prove that if a natural number q has the property that it divides either a or b whenever it divides their product ab, then q must be a prime number. The student is seeking guidance and suggests trying to prove the contrapositive. Another user suggests choosing a and b to be composite numbers and proving the converse, but this is not necessary for the assignment.
  • #1
ar6
5
0

Homework Statement


I'm starting an introductory course in "Advanced math" and need a little homework guidance please.

The question: Let a, b, and q be natural numbers, and q > 1. Prove that if q has the property: q divides a or q divides b whenever q divides ab, then q is prime.




Homework Equations





The Attempt at a Solution



Ok. First I'm assuming that this proof can't be too hard especially for one of the first assignments and is probably a standard one to assign new students in this subject so I apologize if this has been asked before. A little nudge in the right direction would be helpful. I think that I should try to prove the contrapositive. So assume q is not prime but then I am a little confused on what exactly ~(p) would be. Any help would be appreciated
 
Physics news on Phys.org
  • #2
Since a and b are both composite, let ab= mnjk, where two factors of mnjk is a and the other two is b. If p is prime and it divides ab = mnjk, then taking any combination of two of m,n,j, or k to be one factor and two to be the other, it is evident that one of the two factors must be divisible by p. Now prove the converse.
 
  • #3
I like your contrapositive idea. The contrapositive is that if q is NOT prime, then there is an a and b such that q divides ab but q does not divide a or b. If q is NOT prime, i.e. composite, what's a good choice for a and b? bel, the OP doesn't have to prove the converse. That's harder and requires unique prime factorization.
 

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.

How can you prove that a number is prime?

There are several methods for proving that a number is prime, including trial division, Sieve of Eratosthenes, and various primality tests such as the AKS primality test or the Miller-Rabin primality test.

What is the proof of the infinitude of prime numbers?

The proof of the infinitude of prime numbers was first given by Euclid in his work Elements. It states that if there is a finite number of prime numbers, we can always find a larger prime number by multiplying all of them together and adding 1. Therefore, there must be an infinite number of prime numbers.

Can every number be expressed as a product of prime numbers?

Yes, this is known as the Fundamental Theorem of Arithmetic. It states that every positive integer can be expressed as a unique product of prime numbers, regardless of how large the number may be.

What is the significance of prime numbers in mathematics?

Prime numbers have a significant role in mathematics, particularly in number theory. They are fundamental building blocks for all positive integers and have various applications in cryptography, coding theory, and other fields of mathematics. They also have connections to other important mathematical concepts, such as the distribution of prime numbers and the Riemann Hypothesis.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
929
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
906
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
Back
Top