Skip to main content

Section 9.3 The Floor Function

Definition 9.3.1.

Let \(x\in\mathbb{R}.\) Then \(\lfloor x\rfloor\) denotes the greatest integer less than or equal to \(x.\) This is sometimes called the integer part of \(x.\)

We have

\begin{equation*} \lfloor \pi\rfloor = 3 \end{equation*}

and

\begin{equation*} \lfloor 2 \rfloor = 2. \end{equation*}

According to Gauss' Lemma \((2/p) = (-1)^n,\) where \(n\) is the number of integers in the set

\begin{equation*} S =\left\{2, 2(2), 3(2),..., \frac{p-1}{2}(2)\right\} \end{equation*}

whose remainders upon division by \(p\) are greater than \(p/2.\) Since every member of \(S\) is less than \(p,\) we may just count them. Now for \(k\) with \(1 \leq k\leq (p-1)/2,\) we have \(2k\lt p/2\) precisely when \(k \lt p/4;\) that is, there are \(\lfloor p/4\rfloor\) integers in \(S\) less than \(p/2,\) so there are

\begin{equation*} n=\frac{p-1}{2}-\left\lfloor\frac{p}{4}\right\rfloor \end{equation*}

integers that are greater than \(p/2.\)

Now if \(p\) is an odd prime, then \(p\) is of the form \(8k + 1, 8k + 3, 8k + 5,\) or \(8k + 7.\)

If \(p = 8k + 1,\) then

\begin{equation*} n = 4k-\left\lfloor 2k+\frac{1}{4}\right\rfloor = 4k-2k = 2k. \end{equation*}

If \(p = 8k + 3,\) then

\begin{equation*} n = 4k+1-\left\lfloor 2k+\frac{3}{4}\right\rfloor = 4k+1-2k = 2k+1. \end{equation*}

If \(p = 8k + 5,\) then

\begin{equation*} n = 4k+2-\left\lfloor 2k+1+\frac{1}{4}\right\rfloor = 4k+2-(2k+1) = 2k+1. \end{equation*}

If \(p = 8k + 7,\) then

\begin{equation*} n = 4k+3-\left\lfloor 2k+1+\frac{3}{4}\right\rfloor = 4k+3-(2k+1) = 2k+2. \end{equation*}

Thus if \(p = 8k+1\) or \(8k+7, n\) is even and so \((2/p) = 1,\) and if \(p = 8k+3\) or \(8k + 5, n\) is odd and so \((2/p) =-1.\)

Suppose there are finitely many primes of the form \(8k-1,\) say \(p_1, p_2,..., p_n\) and consider

\begin{equation*} N = (4p_1p_2\cdots p_n)^2-2. \end{equation*}

Note that since \(N\gt 2\) and \(N = 2(2k-1)\) for some \(k,\) there is at least one odd prime divisor of \(N,\) say \(p.\) So

\begin{equation*} (4p_1p_2\cdots p_n)^2\equiv 2\pmod{p} \end{equation*}

or rather, \((2/p) = 1.\) From a previous result, we have that \(p \equiv \pm 1\pmod{8}.\) If all of the odd prime divisors of \(N\) were of the form \(8k + 1,\) then \(N\) would be of the form \(16a + 2\) for some \(a.\) But \(N\) is of the form \(16a- 2\) for some \(a.\) So \(N\) must have a prime divisor \(q\) of the form \(8k-1.\) As before, \(q\vert N\) and \(q\vert (4p_1p_2\cdots p_n)^2,\) so that \(q\vert 2,\) which is impossible. Hence, there are infinitely many primes of the form \(8k-1.\)