Proving Euclid's Lemma: The Role of Primality in Divisibility

[Suyogya]

"If a prime p divides the product ab of two integers a and b,then p must divide at least one of those integers a and b."(its euclid lemma true for primes only) when i tried to prove it as:
let for any integer p divides ab (ab)=(pn) ;for some integer n (a*b)/p=n
since RHS is integer, therefore for LHS to be integer either (a/p) or (b/p) or both must be integer, which means either p divides a or b or both.(hence proved)
But there is no restriction on p to be prime yet? is there any mistake in it?

 

[scottdave]

Try some sample numbers with p being prime and nonprime to see how it plays out. Here's one to try with a nonprime.
If a is 4 and b is 15, and p is 6, see how that works and go from there.

 

[PeroK]

"If a prime p divides the product ab of two integers a and b,then p must divide at least one of those integers a and b."(its euclid lemma true for primes only) when i tried to prove it as:
let for any integer p divides ab (ab)=(pn) ;for some integer n (a*b)/p=n
since RHS is integer, therefore for LHS to be integer either (a/p) or (b/p) or both must be integer, which means either p divides a or b or both.(hence proved)
But there is no restriction on p to be prime yet? is there any mistake in it?

If ##a=2, b=3, p=6##, then you have a counterexample when ##p## is not prime.

In other words, in your "proof" you have said that as ##6## divides ##2 \times 3##, then either ##6## divides ##2## or ##6## divides ##3##.

It is necessary, therefore, that ##p## is prime.

 

[scottdave]

Rereading it looks like they telling you that p is prime. Your job is not to prove p is prime, but to prove it is a divisor of a or b. Try representing a and b as product of prime factors.

 

[Suyogya]

Rereading it looks like they telling you that p is prime. Your job is not to prove p is prime, but to prove it is a divisor of a or b. Try representing a and b as product of prime factors.

I proved it by assuming p an integer, hence should be valid for composites as well as primes, but its only for primes actually. so where its wrong

 

[PeroK]

I proved it by assuming p an integer, hence should be valid for composites as well as primes, but its only for primes actually. so where its wrong

See post #3.

 

[scottdave]

You have 2 examples of nonprimes, showing it doesn't necessarily work for nonprimes. I gave one in Post #2, and @PeroK gave one in Post #3.