Prime number divisibility


by andrew34765
Tags: divisibility, prime, proof
andrew34765
andrew34765 is offline
#1
Jun28-09, 08:29 PM
P: 1
1. The problem statement, all variables and given/known data

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.

2. Relevant equations

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

3. 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.
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
VeeEight
VeeEight is offline
#2
Jun29-09, 12:49 AM
P: 612
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
kenewbie
kenewbie is offline
#3
Jun29-09, 02:52 AM
P: 236
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.


Register to reply

Related Discussions
8-digit number and divisibility puzzle Brain Teasers 3
a prime number which equals prime numbers General Math 10
Number Theory - divisibility and primes Calculus & Beyond Homework 1
Prime numbers and divisibility Linear & Abstract Algebra 4
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number. Linear & Abstract Algebra 0