Theorem: If p is a prime and p | ab, then p | a or p | b

We prove the above theorem.

[hellostranger]

Thank you for the clear explanation! ^___^

[tonyhaddad]

consider a*b & p (prime)/a*b

first base case : wlog let a = 1
we have 1*b
in this case its obvious that if p/ 1*b then p/b
(so the statment p divide 1 or b is true)

second base case: a = 2
we have 2*b
2*b = k*p
bwoc suppose p does not divide 2 and b
so b = p*t + r (r<p)
2*p*t + 2*r = k*p
p / 2*r
so 2*r = p*v
since p > r then v < 2 so v = 1
2*r = p
since p is prime then r = 1
2 = p so its a contridiction beacaus if p = 2 then p /2

so we have 1*b and 2*b are proven for all b natural number

now suppose j is from the set 1 to n
& if p/j*b p must divide j or b

suppose p / (n+1)*b
and p does not divide (n+1) and b
b = p*k + r
(n+1)*b=(n+1)*p*k + r*(n+1)
same logic
r*(n+1) = p*v and v < (n+1)
so v comes from the set (1 to n)
so if a prime / v*p it must divide v or p
if n+1 is prime n+1 must divide
v or p but v smaller so n+1 must divide p so n+1 = p so p/n+1 which is a contradiction
if n+1 is a composite so there exist a natural number g > 1 that divide n+1
n+1 = g*L
g*L*r = v*p
where g <(n+1) and L < (n+1) beacause the smallest prime is 2
we have p /g*(L*r) so p divide g or (L*r)
if p/ g so p / g*L = (n+1) we have contradiction
and if p/ (L*r)
p must divide L or r
p > r so p / L so same contradiction
where done !

[hasnainabbas]

3 divides product of6, 9
but 3/6 and also 3/9
how is it possible ????

[purabimahata]

Sir, is the converse part true? i. e. If p|ab implies either p|a or p|b, then p is prime?

[tapioca]

i'm confused because let's say p=10, then 10 divides product of 10 and 6, so 10|10, so 10 is a prime number? or we have to assume that p is not a or b?