Prove the following statement using the well ordering property.?
Every natural number > 1 is divisible by a prime number.
Let S = {n a natural number such that n > 1 and n is NOT divisible by a prime number}. We want to show that S is empty (that’s just a restatement of the question.)
Suppose, for a contradiction, that S is in fact not empty. By the well ordering principle, every non-empty subset of the integers has a least element in it. Therefore there exists x in S that is minimal. Notice that x cannot itself be prime, since otherwise x is divisible by a prime number, namely itself. So x is composite, meaning x = a*b for some a and b both not 1 (this is possible since x in S means x > 1). In particular, since a and b aren’t 1, both a and b are smaller than x. Now a and b cannot be in S, otherwise they would be the minimal element and not x. Just look at a, since a is not in S, then by definition of S a is divisible by a prime number. But if a is divisible by a prime number, then since x = a*b, x is also divisible by a prime number. Therefore x is not in S, contradicting the definition of x. So S is in fact empty and the prove is done.
September 3rd, 2009 at 6:29 am
Let S = {n a natural number such that n > 1 and n is NOT divisible by a prime number}. We want to show that S is empty (that’s just a restatement of the question.)
Suppose, for a contradiction, that S is in fact not empty. By the well ordering principle, every non-empty subset of the integers has a least element in it. Therefore there exists x in S that is minimal. Notice that x cannot itself be prime, since otherwise x is divisible by a prime number, namely itself. So x is composite, meaning x = a*b for some a and b both not 1 (this is possible since x in S means x > 1). In particular, since a and b aren’t 1, both a and b are smaller than x. Now a and b cannot be in S, otherwise they would be the minimal element and not x. Just look at a, since a is not in S, then by definition of S a is divisible by a prime number. But if a is divisible by a prime number, then since x = a*b, x is also divisible by a prime number. Therefore x is not in S, contradicting the definition of x. So S is in fact empty and the prove is done.
References :
September 3rd, 2009 at 6:51 am
Do you accept that n, a, b natural numbers > 1 and n = ab ==> n > a and n > b? Suppose b >= n then ab > b > n =><=
So n, a, b nat numbers >1 and n = ab => n > a and n > b.
Pick n. Either n is prime and we are done or n is the factor of two numbers n1 and n2 now wlog say n1 is <= n2 (this is not where the well ordering property comes in, this is just to simplify life) again n1 is either prime and we are done or there are n11 and n12 which are factors of n1 again wlog say n11 <= n12. So through this process we have n < n1 < n11 < n111 < … and by well ordering we know that this must end after no more than n steps (actually ln(n)/ln(2) steps but that’s no more than n) with a prime which is a factor of n. It’s prime because it can’t be divided further.
References :