On the sizes of the maximal prime powers divisors of factorials
Dan Levy
Abstract
. Let p p be any prime, and p ν p ( n ! ) p^{\nu_{p}\left(n!\right)} the maximal power of p p dividing n ! n! . It is proved that there exists a positive integer n 0 n_{0} , which depends only on p p , such that q ν q ( n ! ) < p ν p ( n ! ) q^{\nu_{q}\left(n!\right)}
p q>p . For twin primes p p and q = p + 2 q=p+2 it is proved that the minimal n 0 n_{0} satisfying q ν q ( n ! ) < p ν p ( n ! ) q^{\nu_{q}\left(n!\right)}
p\text{.}
Corollary 1.2
.
Let
m
be any positive integer and let
p_{1}3^{\nu_{3}\left(n!\right)}>5^{\nu_{5}\left(n!\right)}>\cdots>p_{m}^{\nu_{p_{m}}\left(n!\right)}>q^{\nu_{q}\left(n!\right)}\text{; }\forall n\geq n_{0}\left(m\right)
for any prime
q
which is larger than
p_{m}
.
Proof.
This follows from Theorem (
1.1
) by taking
n_{0}\left(m\right)=\max\left\{n_{0}\left(p_{1}\right),\ldots,n_{0}\left(p_{m}\right)\right\}
.
Corollary 1.3
.
Let
q
be any odd prime, and
n\geq 2
any
integer. Then
2^{\nu_{2}\left(n!\right)}>q^{\nu_{q}\left(n!\right)}
with the single exception
q=n=3
.
Remark 1.4
.
Shortly after uploading the first version (arXiv:submit/7138707) of the
present paper, I have learned about a paper by Mehdi Hassani, published in
2005, with results similar to Theorem (
1.1
) and Corollary (
1.3
) (
[
4
]
Theorem (5.2) and Corollary
(5.3)). It can be checked that Theorem (
1.1
) and Corollary (
1.3
) of the present paper imply, respectively, Hassani’s
Theorem (5.2) and Corollary (5.3), but not the other way around. I am
grateful to Carlo Sanna for informing me about Hassani’s results.
Let
p
be a fixed prime. The prime successor of
p
, denoted
p_{\text{succ}}
, is the smallest prime which is strictly larger than
p
. As we shall
see, the proof of Theorem (
1.1
) shows that any positive integer
solution
n
of
\left\lfloor\log_{p}n\right\rfloor<\left(n-1\right)h_{p}\left(p_{\text{succ}}\right)-\frac{p-2}{p-1}\text{,}
where
h_{p}\left(x\right):=\frac{1}{p-1}-\frac{\log_{p}x}{q-1}
,
satisfies
q^{\nu_{q}\left(n!\right)}p
. Moreover, there exists
n_{0}\in\mathbb{N}
such that the
above inequality holds true for all
n\geq n_{0}
. Note that since
p_{\text{succ}}
is uniquely determined by
p
, the minimal such
n_{0}
is a
function of
p
, and hence we refer to this minimal value as
n_{0}\left(p\right)
. It is easy to see that the existence of
n_{0}\left(p\right)
implies, in turn, the existence of a minimal positive integer
n_{\min}\left(p\right)
such that
p_{\text{succ}}^{\nu_{p_{\text{succ}}}\left(n!\right)}
2
), and if so, can
n_{\min}\left(p\right)
be written in polynomial form whose coefficients are parametrized
by
p_{\text{succ}}-p
?
2.
Proofs
2.1.
Proof of Theorem (
1.1
)
Lemma 2.1
.
Let
pp
we have
h_{p}\left(q\right)\geq h_{p}\left(p_{\text{succ}}\right)>0\text{.}
Proof.
The differentiability of
h_{p}\left(x\right)
in
[p,\infty)
is clear.
In order to prove that it is monotonically increasing we compute its first
derivative in
[p,\infty)
h_{p}^{\prime}\left(x\right)=\frac{1}{\ln p}\frac{1}{\left(x-1\right)^{2}}\left(\ln x+\frac{1}{x}-1\right)\text{,}
and check that
h_{p}^{\prime}\left(x\right)
is positive in
[p,\infty)
. Clearly, for any
x\in[p,\infty)
we have
h_{p}^{\prime}\left(x\right)>0
iff
g\left(x\right):=\ln x+\frac{1}{x}-1>0
. For
p=2
we
have
g\left(2\right)=\ln 2+\frac{1}{2}-1
\geq 0.693-\frac{1}{2}>0
. For
p\geq 3
we have
\ln p>1
and hence
g\left(p\right)=\ln p+\frac{1}{p}-1>\frac{1}{p}>0
. Thus
g\left(p\right)>0
for all primes
p
. Now
g^{\prime}\left(x\right)=\frac{1}{x}-\frac{1}{x^{2}}
and
g^{\prime}\left(x\right)>0
for all
x\in[p,\infty)
since
p>1
. It
follows that
g\left(x\right)
is monotonically increasing in
[p,\infty)
, which together with
g\left(p\right)>0
shows that
g\left(x\right)>0
for all
x\in[p,\infty)
. Hence
h_{p}^{\prime}\left(x\right)>0
for all
x\in[p,\infty)
, and so
h_{p}\left(x\right)
is
monotonically increasing in
[p,\infty)
. This implies that for any
u>p
the function
h_{p}\left(x\right)
has a global minimum in
[u,\infty)
,
given by
h_{p}\left(u\right)
. The value
h_{p}\left(u\right)
is
strictly positive since
h_{p}\left(p\right)=0
, and
h_{p}\left(x\right)
is monotonically increasing in
[p,\infty)
. Choosing
u=p_{\text{succ}}
concludes the proof.
Proof of Theorem (
1.1
).
Let
p
be any prime. We have to prove the existence of
n_{0}\in\mathbb{N}
, which may depend on
p
, such that
q^{\nu_{q}\left(n!\right)}p\text{ .}
Since
q^{\nu_{q}\left(n!\right)}\geq 1
we must have
n_{0}\geq p
.
Under this assumption
\nu_{p}\left(n!\right)>0
for all
n\geq n_{0}
and hence
q^{\nu_{q}\left(n!\right)}
p
and all
n\geq n_{0}
with
q>n
. Hence
it suffices to show that there exist
n_{0}\in\mathbb{N}
such that
n_{0}>p
and
q^{\nu_{q}\left(n!\right)}
0
, and hence, any positive integer
n
satisfying
(2.8)
\left\lfloor\log_{p}n\right\rfloor<\left(n-1\right)h_{p}\left(p_{\text{succ}}\right)-\frac{p-2}{p-1}\text{,}
also satisfies (
2.7
) for all primes
q
such that
pq^{\nu_{q}\left(n!\right)}
for all primes
q>2
and all integers
n\geq n_{0}
. By (
2.1
) we have
(2.11)
h_{2}\left(2_{\text{succ}}\right)=h_{2}\left(3\right)=1-\frac{1}{2}\frac{\ln 3}{\ln 2}>0.2075>\frac{1}{5}
and hence we get that any
n
satisfying
\left(\ast\ast\right)~\left\lfloor\log_{2}n\right\rfloor\leq\frac{n-1}{5}\text{,}
also satisfies
\left(\ast\right)
. By inspection, the smallest integer
solution of
\left(\ast\ast\right)
is
n=21
, and
\left(\ast\ast\right)
also holds true for all
21\leq n\leq 31
. Now,
\left\lfloor\log_{2}n\right\rfloor
is a step function which is constant on each step (an
interval of the form
\left[2^{k},2^{k+1}-1\right]
) and increases by one
unit from step to step. On the other hand,
\frac{n-1}{5}
is a linear
function of
n
that increases by
\frac{2^{k}}{5}
along the step
\left[2^{k},2^{k+1}-1\right]
. Since
n=32
corresponds to
k=5
, and
\frac{2^{5}}{5}>6>1
, it is clear that
\left(\ast\ast\right)
holds also for all
n\geq 32
. We have thus shown that
2^{\nu_{2}\left(n!\right)}>q^{\nu_{q}\left(n!\right)}
holds true for all
n\geq 21
and all primes
q>2
.
It remains to consider the interval
2\leq n\leq 20
. Since this interval is
finite and the relevant values of
q
are the odd primes in this same
interval, namely the primes
3,5,7,11,13,17,19
, one can check ”by hand”,
e.g., an easy to write GAP (
[
3
]
) program, that
2^{\nu_{2}\left(n!\right)}>q^{\nu_{q}\left(n!\right)}
holds true for all integers
2\leq n\leq 20
and all primes
q\in\left\{3,5,7,11,13,17,19\right\}
with the single exception
q=n=3
.
2.2.
Proof of Theorem (
1.5
)
Let
n\geq 1
and
b\geq 2
be integers. Recall that the base
b
representation of
n
is the unique sequence
\left(n\right)_{b}:=\left(d_{l}\text{,}d_{l-1},\ldots,d_{1},d_{0}\right)
of non-negative integers (the base
b
digits of
n
)
d_{i}
,
0\leq i\leq l
such that
d_{i}\in\left\{0,1,\ldots,b-1\right\}
,
d_{l}\geq 1
,
and
n=d_{l}b^{l}+d_{l-1}b^{l-1}+\cdots+d_{1}b+d_{0}\text{.}
Furthermore we say that
n
is an
l+1
digit number in base
b
, and
s_{b}\left(n\right):=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}
.
Lemma 2.3
.
With notation as above,
n-s_{b}\left(n\right)=0
for all
1\leq n\leq b-1
, and
n-s_{b}\left(n\right)>0
for
all
n\geq b
. Furthermore,
\left(b-1\right)|\left(n-s_{b}\left(n\right)\right)
.
Proof.
The first claim is clear. For
n\geq b
we have:
n-s_{b}\left(n\right)=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}b^{i}-\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}\left(b^{i}-1\right)=\mathop{\textstyle\sum}\limits_{i=1}^{l}d_{i}\left(b^{i}-1\right)\overset{d_{l}\geq 1}{\geq}b^{l}-1>0\text{.}
Moreover,
\left(b-1\right)|\left(b^{i}-1\right)
for all
1\leq i\leq l
, so
\left(b-1\right)|\left(n-s_{b}\left(n\right)\right)
follows.
Let
p
be a prime such that
p+2
is also a prime. Set
q:=p+2\text{, }k:=\frac{p^{2}+p}{2}-1\text{.}
In order to prove Theorem (
1.5
) we have to prove that
q^{\nu_{q}\left(k!\right)}>p^{\nu_{p}\left(k!\right)}\text{;}
and
(2.12)
~~~~~~p^{\nu_{p}\left(n!\right)}>q^{\nu_{q}\left(n!\right)}\text{; }\forall n\geq k+1\text{.}
Lemma 2.4
.
\nu_{q}\left(k!\right)=\nu_{p}\left(k!\right)=\frac{p-1}{2}\text{,}
and consequently
q^{\nu_{q}\left(k!\right)}>p^{\nu_{p}\left(k!\right)}
.
Proof.
We calculate the exponents
\nu_{q}\left(k!\right)
and
\nu_{p}\left(k!\right)
using (
1.3
). We have
k=\left(\frac{p-1}{2}\right)\left(p+2\right)\Longrightarrow\left(k\right)_{p+2}=\left(\frac{p-1}{2},0\right)\Longrightarrow s_{p+2}\left(k\right)=\frac{p-1}{2}\text{.}
Similarly
k=\left(\frac{p-1}{2}\right)p+p-1\Longrightarrow\left(k\right)_{p}=\left(\frac{p-1}{2},p-1\right)\Longrightarrow s_{p}\left(k\right)=\frac{3}{2}\left(p-1\right)\text{.}
Substituting in (
1.3
) gives:
\nu_{q}\left(k!\right)=\frac{k-s_{q}\left(k\right)}{q-1}=\frac{\left(\frac{p-1}{2}\right)\left(p+2\right)-\frac{p-1}{2}}{p+1}=\frac{p-1}{2}
\nu_{p}\left(k!\right)=\frac{k-s_{p}\left(k\right)}{p-1}=\frac{\left(\frac{p-1}{2}\right)p+p-1-\frac{3}{2}\left(p-1\right)}{p-1}=\frac{p}{2}+1-\frac{3}{2}=\frac{p-1}{2}\text{.}
Having proved
\nu_{q}\left(k!\right)=\nu_{p}\left(k!\right)
,
q^{\nu_{q}\left(k!\right)}>p^{\nu_{p}\left(k!\right)}
follows from
q>p
.
Proving (
2.12
) requires more effort. First, (
2.12
) is equivalent
to
(2.13)
r\left(n,p\right):=\frac{n-s_{p}\left(n\right)}{n-s_{p+2}\left(n\right)}>\left(\frac{\ln\left(p+2\right)}{\ln p}\right)\left(\frac{p-1}{p+1}\right)\text{; }\forall n\geq k+1=\frac{p^{2}+p}{2}\text{,}
by Lemma (
2.1
). Note that
n-s_{p+2}\left(n\right)>0
by Lemma (
2.3
) (
p+2\leq n
since
n\geq k+1
and
p\geq 3
).
For a fixed odd prime
p
we view
r\left(n,p\right)
as a function from
the set of all integers
n
satisfying
n\geq k+1
into the set of positive
rational numbers.
Lemma 2.5
.
r\left(k+1,p\right)=1
.
Proof.
Using
\left(k\right)_{p}
and
\left(k\right)_{p+2}
from the proof of
Lemma (
2.4
), gives
\left(k+1\right)_{p}=\left(\frac{p+1}{2},0\right)\text{ and }\left(k+1\right)_{p+2}=\left(\frac{p-1}{2},1\right)\text{.}
Hence
s_{p}\left(k+1\right)=s_{p+2}\left(k+1\right)=\frac{p+1}{2}
, and
the claim follows.
Lemma 2.6
.
r\left(n,p\right)
has a global
minimum in the interval
n\geq\frac{p^{2}+p}{2}
.
Proof.
First we prove
\lim_{n\rightarrow\infty}r\left(n,p\right)=1
. Write
r\left(n,p\right):=\frac{n-s_{p}\left(n\right)}{n-s_{p+2}\left(n\right)}=\frac{1-\frac{s_{p}\left(n\right)}{n}}{1-\frac{s_{p+2}\left(n\right)}{n}}\text{,}
and use the bounds
1\leq s_{p}\left(n\right)\leq\left(p-1\right)\left(1+\log_{p}n\right)
(see the proof of Theorem (
1.1
)). Since a
similar inequality applies to
s_{p+2}\left(n\right)
, we get:
(2.14)
\frac{1-\frac{\left(p-1\right)\left(1+\log_{p}n\right)}{n}}{1-\frac{1}{n}}\leq r\left(n,p\right)\leq\frac{1-\frac{1}{n}}{1-\frac{\left(p+1\right)\left(1+\log_{p+2}n\right)}{n}}\text{.}
Since
p
is fixed, we have
\lim_{n\rightarrow\infty}\frac{\left(p-1\right)\left(1+\log_{p}n\right)}{n}=\lim_{n\rightarrow\infty}\frac{\left(p+1\right)\left(1+\log_{p+2}n\right)}{n}=0\text{,}
and
\lim_{n\rightarrow\infty}r\left(n,p\right)=1
follows. Now assume
by contradiction that
r\left(n,p\right)
has no global minimum in the
interval
n\geq k+1
. By Lemma (
2.5
) we have
r\left(k+1,p\right)=1
. Since this cannot be a global minimum in the interval
n\geq k+1
, there exists an infinite monotonically increasing sequence of
integers
k+1=i_{0}r\left(i_{1},p\right)>r\left(i_{2},p\right)>\cdots
is a monotonically decreasing sequence of positive rational numbers. It
follows that this sequence is bounded from below by some nonnegative
rational number less than
1
. Therefore there exists
0\leq l<1
such that
\lim_{j\rightarrow\infty}r\left(i_{j},p\right)=l
. This contradicts
\lim_{n\rightarrow\infty}r\left(n,p\right)=1
.
We will prove that (
2.13
) holds true for all
n\geq k+1
by showing
that the global minimum of
r\left(n,p\right)
in the interval
n\geq k+1
satisfies (
2.13
). The following theorem gives the necessary
information about the global minimum of
r\left(n,p\right)
.
Theorem 2.7
.
(a) The smallest integer
m
at which the global minimum of
r\left(n,p\right)
in the interval
n\geq k+1
occurs is given by
(2.15)
m=\left\{\begin{array}[]{c}\left(p+2\right)^{2}\text{ if }p\in\left\{3,5\right\}\\
p^{2}-4\text{ if }p\geq 11\text{.}\end{array}\right.
(b) The value of the global minimum of
r\left(n,p\right)
in the interval
n\geq k+1
is given by:
\displaystyle r\left(m,3\right)
\displaystyle=
\displaystyle r\left(25,3\right)=\frac{5}{6}
\displaystyle r\left(m,5\right)
\displaystyle=
\displaystyle r\left(49,5\right)=\frac{5}{6}
\displaystyle r\left(m,p\right)
\displaystyle=
\displaystyle r\left(p^{2}-4,p\right)=\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}\text{; }\forall p\geq 11\text{.}
Before proving Theorem (
2.7
) we check that it
implies (
2.12
). As we already saw, (
2.12
) is equivalent to (
2.13
). Since
r\left(m,p\right)
is the global minimum of
r\left(n,p\right)
in the interval
n\geq k+1
, (
2.13
) follows iff
(2.16)
r\left(m,p\right)>\left(\frac{\ln\left(p+2\right)}{\ln p}\right)\left(\frac{p-1}{p+1}\right)\text{.}
Lemma 2.8
.
Assuming that Theorem (
2.7
) is correct, (
2.16
) holds true for all
p
such that
p
and
p+2
are twin primes.
Proof.
For each
p
we compare the value of the r.h.s. of (
2.16
) with the
value of
r\left(m,p\right)
as given by Theorem (
2.7
).
1.
p=3
\frac{\ln\left(p+2\right)}{\ln p}\cdot\frac{p-1}{p+1}=\frac{\ln 5}{\ln 3}\cdot\frac{2}{4}<0.733\left(p-2\right)\ln\left(p+2\right)
\displaystyle\Longleftrightarrow
\displaystyle\left(p-1\right)\ln p-\left(p-2\right)\ln\left(p+2\right)>0
Set
f\left(x\right):=\left(x-1\right)\ln x-\left(x-2\right)\ln\left(x+2\right)\text{; }\forall x\geq 11\text{.}
We will show that
f\left(x\right)
is positive in its domain of
definition.
\displaystyle f\left(x\right)
\displaystyle=x\left(\ln x-\ln\left(x+2\right)\right)+2\ln\left(x+2\right)-\ln x
\displaystyle=x\ln\left(\frac{x}{x+2}\right)+\ln\left(x+2\right)^{2}-\ln x
\displaystyle=-x\ln\left(\frac{x+2}{x}\right)+\ln\left(\frac{\left(x+2\right)^{2}}{x}\right)
\displaystyle=-\ln\left(\left(\frac{x+2}{x}\right)^{x}\right)+\ln\left(\frac{\left(x+2\right)^{2}}{x}\right)
\displaystyle=-\ln\left(\left(1+\frac{2}{x}\right)^{x}\right)+\ln\left(\frac{\left(x+2\right)^{2}}{x}\right)\text{.}
Using
\lim_{x\rightarrow\infty}\left(1+\frac{2}{x}\right)^{x}=e^{2}\text{,}
we have
-\lim_{x\rightarrow\infty}\ln\left(\left(1+\frac{2}{x}\right)^{x}\right)=-\ln e^{2}=-2\text{.}
Moreover
-\ln\left(\left(1+\frac{2}{x}\right)^{x}\right)
is
monotonically decreasing towards its limit. On the other hand
\ln\left(\frac{\left(x+2\right)^{2}}{x}\right)
is monotonically increasing for
x\geq 11
and for
x=11
we have
\ln\left(\frac{\left(11+2\right)^{2}}{11}\right)=\ln\frac{13}{11}+\ln 13>\ln\frac{13}{11}+\ln e^{2}>2\text{.}
We get:
f\left(x\right)>-\lim_{x\rightarrow\infty}\ln\left(\left(1+\frac{2}{x}\right)^{x}\right)+\ln\left(\frac{\left(11+2\right)^{2}}{11}\right)>-2+2=0\text{.}
Now we prove Theorem (
2.7
). Given that part (a)
is established, deriving part (b) from part (a) is an easy task.
Proof of Theorem (
2.7
)(b)
assuming (a).
These are just routine calculations that are required for substituting
n\leftarrow m
into
r\left(n,p\right):=\frac{n-s_{p}\left(n\right)}{n-s_{p+2}\left(n\right)}
. Equality (
2.15
) immediately yields:
1. If
p=3
then
m=25
and
\displaystyle\left(m\right)_{3}=\left(25\right)_{3}=\left(2,2,1\right)\text{, }s_{3}\left(25\right)=5
\displaystyle\left(m\right)_{3+2}=\left(25\right)_{5}=\left(1,0,0\right)\text{, }s_{5}\left(25\right)=1\text{.}
2. If
p=5
then
m=49
and
\displaystyle\left(m\right)_{5}=\left(49\right)_{5}=\left(1,4,4\right)\text{, }s_{5}\left(49\right)=9
\displaystyle\left(m\right)_{5+2}=\left(49\right)_{7}=\left(1,0,0\right)\text{, }s_{7}\left(49\right)=1\text{.}
3. If
p\geq 11
then
m=p^{2}-4=\left(p-2\right)\left(p+2\right)=\left(p-1\right)p+p-4
and hence
\displaystyle\left(m\right)_{p}=\left(p-1,p-4\right)\text{, }s_{p}\left(p^{2}-4\right)=2p-5
\displaystyle\left(m\right)_{p+2}=\left(p-2,0\right)\text{, }s_{p+2}\left(p^{2}-4\right)=p-2
By definition:
r\left(m,p\right)=\frac{m-s_{p}\left(m\right)}{m-s_{p+2}\left(m\right)}\text{.}
The explicit expressions for
r\left(m,p\right)
in the various cases are
as follows:
r\left(m,3\right)=\frac{25-s_{3}\left(25\right)}{25-s_{5}\left(25\right)}=\frac{25-5}{25-1}=\frac{5}{6}\text{.}
r\left(m,5\right)=\frac{49-s_{5}\left(49\right)}{49-s_{7}\left(49\right)}=\frac{49-9}{49-1}=\frac{5}{6}\text{.}
For all
p\geq 11
we get
\displaystyle r\left(m,p\right)=\frac{p^{2}-4-s_{p}\left(p^{2}-4\right)}{p^{2}-4-s_{p+2}\left(p^{2}-4\right)}
\displaystyle=\frac{p^{2}-4-\left(2p-5\right)}{p^{2}-4-\left(p-2\right)}=\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}\text{.}
Finally we turn to prove part (a) of Theorem (
2.7
). First we show that the global minimum of
r\left(n,p\right)
in the
interval
n\geq k+1
occurs at
m
, and then we show that for all
k+1\leq nr\left(m,p\right)
. Therefore
m
is the
smallest integer in the interval
n\geq k+1
at which the global minimum of
r\left(n,p\right)
in this interval occurs.
We begin by arguing that the global minimum of
r\left(n,p\right)
occurs
”not too far” from
k+1
. To this end we use the lower bound (
2.14
)
on
r\left(n,p\right)
:
r\left(n,p\right)\geq\frac{1-\frac{\left(p-1\right)\left(\log_{p}\left(n\right)+1\right)}{n}}{1-\frac{1}{n}}>1-\frac{\left(p-1\right)\left(\log_{p}\left(n\right)+1\right)}{n}\text{; }\forall n\geq q\text{.}
Since
\log_{p}\left(n\right)=\frac{\ln n}{\ln p}
we have
(2.17)
~r\left(n,p\right)>1-\left(p-1\right)\left(\frac{\ln n}{\ln p}+1\right)\frac{1}{n}\text{; }\forall n\geq q\text{.}
Lemma 2.9
.
The real function
f\left(x\right):=\left(\frac{\ln x}{\ln p}+1\right)\frac{1}{x}\text{; }\forall x\geq 1
is positive and monotonically decreasing.
Proof.
Positivity is clear. To show that the function is monotonically decreasing,
we calculate its first derivative:
f^{\prime}\left(x\right)=\frac{1}{\ln p}\frac{1}{x^{2}}+\left(\frac{\ln x}{\ln p}+1\right)\frac{-1}{x^{2}}=\frac{1}{x^{2}}\left(\frac{1}{\ln p}-\frac{\ln x}{\ln p}-1\right)\text{.}
Since
p\geq 3>e
, we have
\frac{1}{\ln p}<1
and
\frac{1}{\ln p}-1<0
.
Hence, since
\frac{\ln x}{\ln p}\geq 0
for all
x\geq 1
,
f^{\prime}\left(x\right)<0
, finishing the proof of the lemma.
Corollary 2.10
.
Let
\widetilde{n}\geq q
be an integer. Then, for all
integers
n\geq
\widetilde{n}
we have
r\left(n,p\right)>1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}\text{.}
Proof.
Let
n\geq
\widetilde{n}
be an integer. Since
\widetilde{n}\geq q
and
n\geq
\widetilde{n}
we have
n\geq q
and therefore, by
2.17
,
r\left(n,p\right)>1-\left(p-1\right)\left(\frac{\ln n}{\ln p}+1\right)\frac{1}{n}\text{.}
In the notation of Lemma (
2.9
) we have
r\left(n,p\right)>1-\left(p-1\right)f\left(n\right)\text{.}
Since
f\left(x\right)
is monotonically decreasing for all
x\geq 1
,
1-\left(p-1\right)f\left(x\right)
is monotonically increasing for all
x\geq 1
. Hence, since
n\geq
\widetilde{n}
,
r\left(n,p\right)>1-\left(p-1\right)f\left(n\right)\geq 1-\left(p-1\right)f\left(\widetilde{n}\right)\text{.}
To utilize the last corollary we look for
\widetilde{n}\geq q
such that
(2.18)
1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}\geq r\left(m,p\right)\text{,}
where
m
is given by (
2.15
). Given such
\widetilde{n}
, Corollary (
2.10
) implies
r\left(n,p\right)>r\left(m,p\right)
for
all
n\geq\widetilde{n}
, and it will remain to establish the claim of part
(a) of Theorem (
2.7
) for the range
k+1\leq n<\widetilde{n}
.
Lemma 2.11
.
Define
m
by (
2.15
).
(a) For
p=3
(
2.18
) holds true for
\widetilde{n}=3^{4}
.
(b) For
p=5
(
2.18
) holds true for
\widetilde{n}=5^{3}
.
(c) For any prime
p\geq 11
(
2.18
) holds true for
\widetilde{n}=4p^{2}
.
Proof.
(a) If
p=3
and
\widetilde{n}=3^{4}
we have:
\displaystyle 1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}=1-2\left(\frac{\ln 3^{4}}{\ln 3}+1\right)\frac{1}{81}=1-\frac{10}{81}
\displaystyle=\frac{71}{81}>\frac{5}{6}=r\left(25,3\right)\text{.}
(b) If
p=5
and
\widetilde{n}=5^{3}
we have:
\displaystyle 1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}=1-4\left(\frac{\ln 5^{3}}{\ln 5}+1\right)\frac{1}{5^{3}}
\displaystyle=1-\frac{4\cdot 4}{125}=\frac{109}{125}>\frac{5}{6}=r\left(49,5\right)\text{.}
(c) If
p\geq 11
and
\widetilde{n}=4p^{2}
we have to show that
1-\left(p-1\right)\left(\frac{\ln 4p^{2}}{\ln p}+1\right)\frac{1}{4p^{2}}\geq r\left(m,p\right)\text{; }\forall p\geq 11\text{.}
We have
\left(\frac{\ln 4p^{2}}{\ln p}+1\right)\frac{1}{4p^{2}}=\left(\frac{\ln 4+\ln p^{2}}{\ln p}+1\right)\frac{1}{4p^{2}}=\frac{1}{4}\left(3+\frac{\ln 4}{\ln p}\right)\frac{1}{p^{2}}\text{.}
Therefore, setting
c_{p}:=\frac{1}{4}\left(3+\frac{\ln 4}{\ln p}\right)
,
we have to show that
1-\frac{c_{p}\left(p-1\right)}{p^{2}}\geq\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}\text{; }\forall p\geq 11\text{.}
We have:
\displaystyle 1-\frac{c_{p}\left(p-1\right)}{p^{2}}\geq\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}
\displaystyle\Longleftrightarrow
\displaystyle p^{2}\left(p-2\right)\left(p+1\right)-p^{2}\left(p-1\right)^{2}\geq c_{p}\left(p-1\right)\left(p-2\right)\left(p+1\right)
\displaystyle\Longleftrightarrow
\displaystyle p^{2}\left(p^{2}-p-2\right)-p^{2}\left(p^{2}-2p+1\right)\geq c_{p}\left(p-2\right)\left(p^{2}-1\right)
\displaystyle\Longleftrightarrow
\displaystyle p^{3}-3p^{2}\geq c_{p}\left(p^{3}-2p^{2}-p+2\right)
Set
\displaystyle f\left(x\right):=x^{3}-3x^{2}-c_{x}\left(x^{3}-2x^{2}-x+2\right)
\displaystyle\text{where }c_{x}:=\frac{1}{4}\left(3+\frac{\ln 4}{\ln x}\right)
Then
f^{\prime}\left(x\right)=3x^{2}-6x-\left(c_{x}\right)^{\prime}\left(x^{3}-2x^{2}-x+2\right)-c_{x}\left(3x^{2}-4x-1\right)\text{.}
Substituting
\left(c_{x}\right)^{\prime}:=\frac{1}{4}\left(3+\frac{\ln 4}{\ln x}\right)^{\prime}=\frac{\ln 4}{4}\frac{-1}{x\left(\ln x\right)^{2}}
gives
\displaystyle f^{\prime}\left(x\right)
\displaystyle=
\displaystyle 3x^{2}-6x+\frac{\ln 4}{4}\frac{1}{x\left(\ln x\right)^{2}}\left(x^{3}-2x^{2}-x+2\right)-c_{x}\left(3x^{2}-4x-1\right)
\displaystyle=
\displaystyle\left(3x^{2}-4x-1\right)\left(1-c_{x}\right)+\frac{\ln 4}{4}\frac{1}{x\left(\ln x\right)^{2}}\left(x-2\right)\left(x^{2}-1\right)+1-2x\text{.}
In order to prove that
f^{\prime}\left(x\right)>0
for all
x\geq 11
,
start with
\frac{\ln 4}{4}\frac{1}{x\left(\ln x\right)^{2}}\left(x-2\right)\left(x^{2}-1\right)+1>1\text{; }\forall x\geq 11\text{.}
Then observe that
\left(c_{x}\right)^{\prime}<0
for all
x\geq 11
so
c_{x}
is maximal in
[11,\infty)
at
x=11
and hence
c_{x}\leq c_{11}<0.895<\frac{9}{10}
\Longleftrightarrow 1-c_{x}>\frac{1}{10}
for
all
x\geq 11
. Since
3x^{2}-4x-1>0
for all
x\geq 11
we have
\left(3x^{2}-4x-1\right)\left(1-c_{x}\right)-2x>\frac{1}{10}\left(3x^{2}-4x-1\right)-2x\text{; }\forall x\geq 11\text{,}
and hence it suffices to prove that
\frac{1}{10}\left(3x^{2}-4x-1\right)-2x>0
;
\forall x\geq 11
. But the last inequality is equivalent to
3x^{2}-24x=3x\left(x-8\right)>1
which is true for all
x\geq 11
. This
concludes the proof that
f^{\prime}\left(x\right)>0
for all
x\geq 11
.
Using
c_{x}<0.895
for all
x\geq 11
, we check that
f\left(11\right)>968-1080\cdot 0.895=1.4>0\text{,}
which together with the positivity of
f^{\prime}\left(x\right)
for all
x\geq 11
, concludes the proof of the lemma.
Proposition 2.12
.
Let
p\in\left\{3,5\right\}
,
k:=\frac{p^{2}+p}{2}-1
,
m:=\left(p+2\right)^{2}
and
\widetilde{n}:=p^{4}
if
p=3
and
\widetilde{n}:=p^{3}
if
p=5
. Then
r\left(n,p\right)\geq r\left(m,p\right)=\frac{5}{6}
for all
k+1\leq n\leq\widetilde{n}
, and if
k+1\leq nr\left(m,p\right)
.
Proof.
GAP (
[
3
]
) calculation.
Proposition 2.13
.
Let
p\geq 11
be a prime such that
q:=p+2
is a prime. Let
k:=\frac{p^{2}+p}{2}-1
,
m:=p^{2}-4
and
\widetilde{n}:=4p^{2}
. Then
r\left(n,p\right)\geq r\left(m,p\right)=\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}
for all
k+1\leq n\leq\widetilde{n}
, and
if
k+1\leq nr\left(m,p\right)
.
Proof.
Let
k+1\leq n\leq\widetilde{n}
, and let
\left(n\right)_{p}:=\left(d_{l},d_{l-1},\ldots,d_{1},d_{0}\right)\text{
and }\left(n\right)_{q}:=\left(e_{l^{\prime}},e_{l^{\prime}-1},\ldots,e_{1},e_{0}\right)
be, respectively, the base
p
and the base
q
digits of
n
. Then (see
Lemma (
2.3
))
n-s_{p}\left(n\right)=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}p^{i}-\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}\left(p^{i}-1\right)=\mathop{\textstyle\sum}\limits_{i=1}^{l}d_{i}\left(p^{i}-1\right)\text{,}
and, similarly,
n-s_{q}\left(n\right)=\mathop{\textstyle\sum}\limits_{i=1}^{l^{\prime}}e_{i}\left(\left(p+2\right)^{i}-1\right)\text{.}
Since
k+1\leq n<\widetilde{n}=4p^{2}
, and
p\geq 11
, we have
4p^{2}<4\left(p+2\right)^{2}0
and condition
\left(\ast\right)
reads
\frac{d_{1}}{e_{1}}\geq\frac{p-1}{p-2}
.
Since
e_{2}=d_{2}=0
we get:
n=d_{1}p+d_{0}=e_{1}\left(p+2\right)+e_{0}=e_{1}p+2e_{1}+e_{0}\text{.}
Since
d_{0}
0
we see, using
e_{1}\leq p-5
and
p\geq 11
, that the l.h.s
is strictly positive. If
\alpha=0
we have to prove that
d_{2}\left(p-7\right)-e_{1}\geq 0\text{.}
By (
2.19
),
4e_{2}+2e_{1}+e_{0}=4d_{2}+2e_{1}+e_{0}=\beta\leq p-1
,
or, equivalently
2e_{1}\leq p-1-4d_{2}-e_{0}\leq p-1-4d_{2}\text{.}
Since
d_{2}\geq 1
, this implies
e_{1}\leq\frac{p-5}{2}
. It follows that
\displaystyle d_{2}\left(p-7\right)-e_{1}\geq d_{2}\left(p-7\right)-\frac{p-5}{2}
\displaystyle\overset{d_{2}\geq 1}{\geq}\left(p-7\right)-\frac{p-5}{2}=\frac{p-9}{2}>0
as required. This concludes the proof that Condition
\left(\ast\right)
is true in case (2.1).
(2.2). Suppose that
e_{2}e_{2}=1
we have
d_{2}=
\alpha_{1}+1\geq 2
, and hence
\alpha_{1}+2\geq 3
. Therefore
\alpha_{1}+\alpha_{0}+2\geq 3
and
\left(\alpha_{1}+\alpha_{0}+2\right)\left(p-2\right)\geq 3\left(p-2\right)\text{.}
But
3\left(p-2\right)\geq 2p+4\Longleftrightarrow p\geq 10\text{.}
Hence, for all
p\geq 11
we have
3\left(p-2\right)\geq 2p+4
and
therefore (
2.22
) is true. This concludes the proof that Condition
\left(\ast\right)
holds true in case (2.2.2).
(2.2.3). Suppose that
e_{2}=2
. Then
d_{2}=\alpha_{1}+2
, and Condition
\left(\ast\right)
reads:
\displaystyle\frac{\left(\alpha_{1}+2\right)\left(p+1\right)+d_{1}}{2\left(p+3\right)+e_{1}}\geq\frac{p-1}{p-2}
\displaystyle\Longleftrightarrow
\displaystyle\frac{2\left(p+1\right)+\alpha_{1}+\alpha_{1}\cdot p+d_{1}}{2\left(p+3\right)+e_{1}}\geq\frac{p-1}{p-2}\text{.}
Since
\alpha_{1}\cdot p+d_{1}=4e_{2}+e_{1}+\alpha_{0}=8+e_{1}+\alpha_{0}
, we get the equivalent inequality:
\displaystyle\frac{2\left(p+3\right)+e_{1}+\alpha_{0}+\alpha_{1}+4}{2\left(p+3\right)+e_{1}}\geq\frac{p-1}{p-2}
\displaystyle\Longleftrightarrow
\displaystyle\frac{\alpha_{0}+\alpha_{1}+4}{2\left(p+3\right)+e_{1}}\geq\frac{1}{p-2}
\displaystyle\Longleftrightarrow
\displaystyle\left(\alpha_{0}+\alpha_{1}+4\right)\left(p-2\right)\geq 2\left(p+3\right)+e_{1}\text{.}
Since
e_{1}\leq p+1
the last inequality certainly holds true if
\left(\alpha_{0}+\alpha_{1}+4\right)\left(p-2\right)\geq 3p+7\text{.}
Since
3\geq d_{2}=
\alpha_{1}+2
and
d_{2}>e_{2}=2
, we have
\alpha_{1}+2=3
, and hence
\alpha_{1}+4=5
. Therefore
\alpha_{1}+\alpha_{0}+4\geq 5
and
\left(\alpha_{0}+\alpha_{1}+4\right)\left(p-2\right)\geq 5\left(p-2\right)\text{.}
But
5\left(p-2\right)\geq 3p+7\Longleftrightarrow 2p\geq 17\text{.}
Thus, Condition
\left(\ast\right)
holds true in case (2.2.3).