Proof of Prime Number: Beginner's Guide

  • Thread starter Black Orpheus
  • Start date
  • Tags
    Prime Proof
In summary, the conversation discusses the problem of proving that if q is a positive integer and q is greater than or equal to 2, and if q divides ab, then q divides a or q divides b, then q must be a prime number. The conversation notes that this statement is the contrapositive of the original statement. The conversation also discusses the definition of a prime number and suggests using the contrapositive to prove the statement.
  • #1
Black Orpheus
23
0
1. Here is the problem I'm stuck on:

Let q be a positive integer, q is greater than or equal to 2, let a and b be integers such that if q divides ab, then q divides a or q divides b. Show that q is a prime number.




2. I know that q is prime if and only if 1 divides q and q divides q.



3. I don't really know where to begin. Where might I go from here?
 
Physics news on Phys.org
  • #2
You want to show that if q is such that whenever q divides ab, q divides a or q divides b, then q must be prime. One way to do this is to show that if q is not prime, then it is not true that whenever q divides ab, q divides a or q divides b. Do you see why this is the same thing? This is called the contrapositive of the original statement.
 
  • #3
Notice that "if q divides ab then q divides a or q divides b" must be true for all numbers a, b. Suppose q was not prime. Can you use that to construct numbers a, b such that "q divides ab but q does not divide a or b separately". The easiest case to try is q= 6.
 
Last edited by a moderator:
  • #4
If I assume that q is prime, then that implies that there exist two integers ab such that q divides ab. It also must mean that a and b are both greater than 1 and less than q. If this is the case, then q does not divide a and q does not divide b (contrapositive: if q is not prime, then q divides ab implies q does not divide a and q does not divide b). Therefore p is prime?
 
  • #5
Black Orpheus said:
2. I know that q is prime if and only if 1 divides q and q divides q.

Just to nitpick a little bit (maybe a lot..) that definition can't be exactly right since it is trivially true for all integers.

In other words it is true for all integers n that 1|n and n|n. You need to modify the definition to say something along the lines of that 1 and n are the only divisors or n, and n is not equal to 1.
 
  • #6
Black Orpheus said:
If I assume that q is prime, then that implies that there exist two integers ab such that q divides ab.
??Given any integer q, there certainly exist many integers a, b such that q divides ab. That's not the point!

It also must mean that a and b are both greater than 1 and less than q.
No, there is nothing said here requiring that a and b be less than q. Indeed, if q divides either a or b, then one of them must be at least as large as q.

If this is the case, then q does not divide a and q does not divide b (contrapositive: if q is not prime, then q divides ab implies q does not divide a and q does not divide b). Therefore p is prime?
?? Where did p come from?? Did you mean "q". If so, you started by saying "If I assume q is prime". What you have proved is "If q is prime, then q is prime"! No, what you give is not the contrapositive of the statement you want to prove- because the statement you give is NOT true.

One more time- you have misstated the problem itself:
Let q be a positive integer, q is greater than or equal to 2, let a and b be integers such that if q divides ab, then q divides a or q divides b. Show that q is a prime number.
is not true.
For example q= 6 is NOT a prime number but a= 5, b= 12 are numbers such that "if q (6) divides ab (60) then q divides a or q divides b (6 divides 12)".

What you want to prove is
Let q be a positive integer, q is greater than or equal to 2, such that for any integers, a, b, such that q divides ab, then q divides a or q divides b. Show that q is a prime number.
As you have been told, it is sufficient to prove the "contrapositive": "if there exist integers a,b such that q divides ab but q does not divide either a or b." Suppose q= 6. Can you find a, b such that 6 divides ab but does not divide either a or b?
 
Last edited by a moderator:

1. 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 positive divisors.

2. How do you prove that a number is prime?

There are a few different methods for proving a number is prime. One common method is to use trial division, which involves dividing the number by all smaller numbers to see if any of them are factors. Another method is to use the Sieve of Eratosthenes, which involves creating a list of all numbers up to the given number and crossing out all non-prime numbers.

3. Why is it important to prove a number is prime?

Proving a number is prime is important in many areas of mathematics, especially in number theory and cryptography. It helps in identifying patterns and relationships between prime numbers, and also in developing secure encryption algorithms.

4. Can all numbers be proven to be prime or composite?

No, there are some numbers that are currently considered to be prime, but have not yet been proven to be so. These are known as probable primes. Additionally, there are some numbers that are believed to be prime, but have not yet been proven to be so. These are known as possible primes.

5. Are there any other methods for proving a number is prime?

Yes, there are several other methods for proving a number is prime, such as the Lucas-Lehmer test for Mersenne primes and the AKS primality test. These methods are more complex and are typically only used for very large numbers.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
15
Views
927
  • Precalculus Mathematics Homework Help
Replies
3
Views
900
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
10
Views
1K
Back
Top