Floor, ceilings, and roots

The real numbers fall along a number line that includes the integers;
and the integers are equally spaced along that line at distance 1 from
one to the next: 7...8...9... etc.  So each real number either is an
integer itself, or falls between two consecutive integers n and n+1.

So given a real number x, if it is not an integer) we can ask in
*which* interval of two consecutive integers (n and n+1) x lies:

n <= x <= n+1

For instance,

      3  <=  pi=3.14.19...  <=  4

More generally, whether x is an integer or not, there will always be
an integer n which the the largest integer less than or equal to
x. That is, such that n <= x < n+1.  We call this n the "floor" of x:

flr(x) <= x < flr(x) + 1

Similary, the ceiling of x is the smallest integer greater than or
equal to x:

ceil(x) - 1 < x <= ceil(x).

From these definitions we can prove standard facts about floors and
ceiings.

Examples:
(i) flr(3x) <= 2+3flr(x)
Proof: We have
    x < flr(x)+1, so
   3x < 3flr(x)+3 
But also
   flr(3x) <= 3x
and so flr(3x) < 3flr(x)+3
Finally, since flr(3x) and 3flr(x)+3 are integers,
then flr(3x) <= 3flr(x)+2.

(ii) flr(2+x) = 2 + flr(x) for all rel x
Proof: We know
   flr(x) <= x < flr(x) + 1
so
   2+flr(x) <= 2 + x < 2+flr(x) + 1

This means that 2+flr(x) is the greatest integer less than or equal to
2+x; and that is what is meant by the floor of 2+x. So
flr(2+x) = 2 + flr(x).



We now return to prime numbers, with an odd twist: square roots and
irrational numbers.

Theorem: There are infinitely-many prime numbers.

Proof (Euclid): Suppose otherwise: that there are only finitely-many
primes, say k in all: p1, p2, ... pk. Then let E = 1 +
p1*p2*...*pk. Now, either E is prime or is divisible by a prime (since
by UFT every integer > 1 is a product of primes).

 Case 1: E is prime. But then E is another prime, not one of the k
primes, which contradicts our assumption.  So E cannot be prime.

 Case 2: E is composite (not prime). Then as noted above, E is
 divisible by a prime, say for instance that pj | E. But if we divide
E = 1 + p1*p2*...*pj*...*pk by pj, we get a remainder (of 1); so pj
cannot divide E; and this holds for every one of the primes
p1,...,pk. So E has no prime divisors, contradicting UFT.
So neither case is possible; we conclude that there cannot be only
finitely-many primes.

end of proof

Note -- We can put this in Sherlockian format as follows: there are
three possibilities: either (a) there are infinitely many primes, or
(b) there are finitely many and E (1 plus their product) is also
prime, or (c) there are finitely many and E is composite. Since we
showed (b) and (c) are impossible, then (a) must be the case.


Theorem: sqrt(2) is irrational.

Proof: Suppose otherwise: that sqrt(2) = a/b for some integers a,b
where b=/=0.

Then 2 = a^2/b^2, so a^2 = 2b^2. This means a^2 must be even, and that
forces a to be even as well, say a = 2c for some integer c.

[One can give a more rigorous proof of the above reasoning: 
a^2 equiv 0 mod 2 
but either a eqiv 0 mod 2, or a equiv 1 mod 2.
Case 1: a equiv 1 mod 2. Then a = 1+2m, so 
a^2 = 1+ 4m + 4m^2 = 1 + 2(2m + 2m^2) equiv 1 mod 0. But this is
false: a^2 equiv 0 mod 2. So this case cannot happen.
Case 0: a equiv 0 mod 2. Since this is the only case remaining, it
must hold. So a is even.]

Then (2c)^2 = 2b^2, so
4c^2 = 2 b^2 and thus b^2 = 2c^2, so b^2 is even which forces b to be
even.

But then a and b must both be even, simply due to their quotient a/b
being sqrt(2). That is impossible. The value of a rational number
(a/b) cannot force a and b to be even, since factors of 2 that
might be in both numerator and denominator can always be divided out
until at least one of them has no such factors left.\

Put another way:

a/b = upf(a) / upf(b) = p1^a1*p2^a2*... / p1^b1*p2^b2*...

                      = p2^a2*... / p1^(b1-a1)*p2^b2*... [if a1<b1]
or
                      = p1^(a1-b1)p2^a2*... / p2^b2*... [if a1>b1]
or
                      = p2^a2*... / p2^b2*... [if a1=b1]

and each of these three possible outcomes has either an odd numerator
or denominator (or both).

Or a rather different proof:

Given that a^2 = 2 b^2 with a and b being positive integers, it
follows that the number of factors of 2 that appear in the upf of the
LHS is even (twice the number in a); and the number on the RHS is odd
(the even number in b^2 plus one extra). So we get two different
factorizations into primes, which is impossible by the UFT.


end of proof