• Support PF! Buy your school textbooks, materials and every day products Here!

Proofs with Primes

  • Thread starter Hoovilation
  • Start date
  • #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
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
In my text, that is the definition of a prime number. :smile:
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
955
That Hurkyl is good looking man, ain't he?
 

Related Threads on Proofs with Primes

  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
2
Views
9K
Replies
5
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
10
Views
4K
  • Last Post
Replies
5
Views
4K
Top