Proving Prime Numbers: Understanding the Non-Divisibility Theorem in Mathematics

In summary, the conversation is about proving that if p is a prime number and a and b are positive integers less than p, then a x b is not divisible by p. The first suggested approach of breaking down a and b into primes and using circular reasoning is not acceptable. Instead, the basic properties of addition, subtraction, multiplication, division, and the definition of a prime number can be used. Another common mistake is assuming that it is not possible for the product of two primes to be equal to the product of two other primes. The alternative problem to prove is that for any four distinct prime numbers, it is not possible for the product of two of them to be equal to the product of the other two. The fact that if ab
  • #1
Hoovilation
Hello everyone,

My first post on these forums and I was wondering if I could have some assistance/direction with a problem:

Prove that if p is a prime number and a and b are any positive integers strictly less than p then a x b is not divisible by p.

The first thing I thought to myself was to break down a and b into primes and then show that since a and b are less than p and p is a prime that a x b cannot be divisble by p. This was not an acceptable answer since it is using circular reasoning which is based on this theorem. He talks about this below:

You are not allowed to use theorems such as all numbers can be uniquely prime factorized, or something along those lines that is actually based on this theorem. You are, however, certainly allowed to assume a prime factorization and can most certainly use the basic properties of addition / subtraction and multiplication / division, and what it means to be a prime, i.e., p when divided by any number a satisfying 1 < a < p leaves a non-zero remainder.

A common mistake is to assume that for any primes p1, p2, p3, p4 it is not possible to have p1 x p2 = p3 x p4 or some glorified version of this. This is simply a specific version of what needs to be proved.
If you can not seem to understand why this amounts to circular reasoning, drop the above problem and prove the following instead:

We are given this alternative but even for this I'm clueless and have no idea on where to start:

Prove that for any four distinct prime numbers p1, p2, p3, and p4, it is not possible that p1 x p2 = p3 x p4.

Any help is greatly appreciated, thanks!
-Hoov
 
Physics news on Phys.org
  • #2
You certainly should be able to use the fact that if ab is divisible by the prime number p, then either a or b is divisible by p. That only uses the basic definition of prime number.
 
  • #3
In my text, that is the definition of a prime number. :smile:
 
  • #4
That Hurkyl is good looking man, ain't he?
 

1. What is the definition of 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?

The most common way to prove that a number is prime is by using the non-divisibility theorem in mathematics. This theorem states that if a number, n, is not divisible by any integer from 2 to the square root of n, then n is a prime number.

3. What is the process for proving a number is not prime?

To prove that a number is not prime, you must show that it is divisible by at least one integer other than 1 and itself. This can be done by finding any factors of the number or by using other mathematical methods such as the Sieve of Eratosthenes.

4. What are some real-life applications of proving prime numbers?

Proving prime numbers has many practical applications in fields such as cryptography, computer science, and statistics. For example, prime numbers are used in encryption algorithms to ensure the security of data and in generating random numbers for statistical simulations.

5. Why is it important to understand the concept of prime numbers?

Understanding prime numbers is crucial in mathematics as they serve as the building blocks for many other mathematical concepts. They also have practical applications in various fields and play a significant role in number theory and other areas of advanced mathematics.

Similar threads

Replies
1
Views
705
  • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • General Math
Replies
6
Views
990
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Replies
35
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
Back
Top