What is the proof for divisibility of prime numbers?

In summary, if P is a prime number and ab is divisible by P, then either a or b must be divisible by P. This can be shown by considering the complete factorization of ab and the properties of real numbers.
  • #1
andrew34765
1
0

Homework Statement



a, b, P, and any other numbers introduced are members of the integer set.

If P is known to be a prime number, and ab can be divided by P, then prove that either a or b can be divided by P.

Homework Equations



All properties of real numbers. Need not be explicitly mentioned in the proof.

The Attempt at a Solution



ab=p*c such that the complete factorization of ab results in p multiplied by the complete factorization of c.

I don't know what to do from here.
 
Physics news on Phys.org
  • #2
Assume that p does not divide b (if it does then we are done). Then gcd(p,b)=1 and so there exist integers x and y such that xp + yb = 1. Multiply through by a to get the equation xpa + yba = a
 
  • #3
Multiplication does not introduce new factors to the product, it is just the addition of all pre-existing factors. Hence, if a*b can be divided by P, then the factor which enables this must be located in either a or b.

You probably want something a little more formal than that blurb though.

k

Edit: I re-read this and I don't think I was too clear, so I'll try to elaborate a little:
If you have a number X consisting of the factors a and b so that X = a * b, and a number Y consisting of the factors a and c so that Y = a * c, then the multiplication of X and Y is the same as putting all the factors together.

XY = aabc

When you perform this process of putting all the factors together, you are not creating any new factors, just combining those you already have. For the original question, this means that if ab is divisible by P, then the factors which makes ab divisible by P must be in either a or b, no new factor occur in the multiplication of the two.

Or, perhaps easier:

P is a prime. ab is divisible by P, and so ab must contain P as a factor. But P is prime, so P cannot be the product of two different integers (one part in a and one part in b), because that violates the definition of a prime number. So a or b must already contain P before the multiplication.
 
Last edited:

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 no other factors.

2. How do I determine if a number is prime?

To determine if a number is prime, you can check if it is only divisible by 1 and itself. If it has any other factors, it is not a prime number.

3. What is the significance of prime numbers in mathematics?

Prime numbers are important in mathematics because they are the building blocks of all other numbers. Every positive integer can be expressed as a unique combination of prime numbers, known as its prime factorization.

4. Can all numbers be divided by prime numbers?

No, not all numbers can be divided by prime numbers. For example, prime numbers themselves cannot be divided by any other numbers, and there are some numbers that are not divisible by any prime numbers, such as 1.

5. How are prime numbers used in cryptography?

Prime numbers are used in cryptography to create secure encryption algorithms. This is because prime numbers are difficult to factorize, making it difficult for hackers to decode encrypted messages.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
899
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
1K
  • Precalculus Mathematics Homework Help
Replies
32
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
469
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
919
Back
Top