\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\DeclareMathOperator{\lcm}{lcm}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 0.8cm{\LARGE\bf
On Composite Odd Numbers $k$ for Which\\
$2^nk$ is a Noncototient for All \\
\vskip .1in
Positive Integers $n$}
\vskip 0.8cm
Marcos J. Gonz\'alez and
Alberto Mendoza\\
Departamento de Matem\'aticas Puras y Aplicadas \\
Universidad Sim\'on Bol\'\i var \\
Sartenejas, Apartado 89000\\
Caracas, 1080-A \\
Venezuela \\
\href{mailto:mago@usb.ve}{\tt mago@usb.ve} \\
\href{mailto:jakob@usb.ve}{\tt jakob@usb.ve} \\
\ \\
Florian~Luca\\
School of Mathematics\\
University of the Witwatersrand \\
1 Jan Smuts Avenue
Braamfontein 2050\\
Johannesburg \\
South Africa \\
and \\
Research Group in Algebraic Structures and Applications\\
King Abdulaziz University\\
Jeddah \\
Saudi Arabia\\
\href{mailto:florian.luca@wits.ac.za}{\tt florian.luca@wits.ac.za}\\
\ \\
V. Janitzio Mej\'{\i}a Huguet \\
Departamento de Ciencias B\'asicas\\
Universidad Aut\'onoma Metropolitana-Azcapotzalco \\
Av.~San Pablo \#180 \\
Col.~Reynosa Tamaulipas\\
C. P. 02200, Azcapotzalco DF\\
M{\'e}xico\\
\href{mailto:vjanitzio@gmail.com}{\tt vjanitzio@gmail.com}\\
\end{center}
\vskip .2 in
\begin{abstract}
We provide some results
relating Riesel numbers with families of cototients and noncototients.
\end{abstract}
\section{Introduction}
A positive integer $k$ is called a {\em Riesel number} whenever
$k$ is odd and $k2^n-1$ is composite for every nonnegative integer $n$.
These numbers are named after Hans Riesel who in 1956 discovered
this property for the number $k = 509203$ (see \cite{riesel}). This is conjectured
to be the smallest Riesel number.
A conjecture due to Erd\H os asserts that if $k$ is a Riesel number then
the smallest prime factor $p_n$ of $k2^n-1$ is bounded as $n$ tends to infinity (see \cite{filaseta}).
We refer to such a $k$ as an {\em Erd\H os-Riesel number}. As far as we know,
each known example of a Riesel number is also an Erd\H os-Riesel number.
A positive integer $n$ is a {\em noncototient} if
$n \not = m - \varphi(m)$, for every integer $m \geq 2$, where $\varphi(m)$ denotes
{\em Euler's totient function}. Notice that $k$ is a Riesel number if and only if
$k2^n \not = p+1 = 2p - \varphi(2p)$, for every odd prime $p$. Sierpi\'nski and Erd\H os
asked whether or not there exist infinitely many noncototients.
This question was answered affirmatively by Browkin
and Schinzel \cite{browkinschinzel}, by showing that the number $k=509203$
has the property
that $k2^n$ is a noncototient for every $n\geq 1$.
In 2005, Flammenkamp and Luca~\cite{flammenluca}
found six more numbers with this property, namely:
$$
2554843,9203917,9545351,10645867,11942443,65484763.
$$
The method used in~\cite{flammenluca} is based on the fact that
{\em if $k$ is a prime Riesel number, which is not a Mersenne prime,
and $2k$ is a noncototient,
then $2^n k$ is a noncototient, for every $n\geq 1$}
(see \cite[Proposition~1]{flammenluca}).
For prime values of $k$, Grytczuk and M\c{e}dryk~\cite{grytczukmed} proved
that the criterion employed in~\cite{flammenluca} are optimal; more precisely,
they proved that {\em for a prime integer $k$, $2^n k$ is a noncototient for every $n\geq 1$,
if and only if $2k$ is a
noncototient and $k$ is a Riesel number which is not a
Mersenne prime} (see \cite[Theorem~1]{grytczukmed}). They also proved that
if $k$ is prime and $2k$ is a cototient then $2k = m - \varphi(m)$ for some
even, squarefree integer $m$ (see \cite[Theorem~3]{grytczukmed}).
We conclude that in this approach---adopted to find infinite families
of noncototients---it is essential to work with prime numbers.
The sequence of Riesel numbers is \seqnum{A101036} and starts as
$$
509203, 762701, 777149, 790841, 992077, 1106681, 1247173, 1254341,\ldots
$$
Our first aim in this paper is to present a method also valid for composite
Riesel numbers. As an application, we have obtain the following:
\begin{theorem} \label{thm:1}
For each $k$ in the set
$$
\{762701, 790841, 992077, 1247173, 1730653, 1744117, 1830187, 1976473, \
3419789, 3423373\},
$$
the number $2^nk$ is a
noncototient, for every $n\geq 1$.
\end{theorem}
It is worth adding that the $10$ Riesel numbers displayed in the statement of Theorem \ref{thm:1} are all composite.
One may ask what can one say about Riesel numbers $k$ such that $2^n k$ is a cototient for some $n\ge 1$. We next result addresses
such Riesel numbers.
\begin{theorem}
\label{thm:2}
There are infinitely many Riesel numbers $k$ such that $2^n k$ is a cototient for some $n\ge 1$.
\end{theorem}
\section{The proof of Theorem \ref{thm:1}}
Given non-zero integers $a,p$, with $p$ prime,
we let $\nu_p(a)$ denote the exponent of $p$ in the prime factorization
of $a$. Further, we use $P(n)$ for the largest prime factor of $n$. The following lemma is our workhorse when attempting to detect Riesel numbers $k$ such that $2^n k$ is a noncototient for some positive integer $n$.
\begin{lemma} \label{thm0}
Let $k$ be a Riesel number. Put $p:=P(k)$ and assume
\begin{equation}
\label{eq:*}
2^{\nu_2(p+1)} k \not =
p^{\nu_{p}(k)} (p+1).
\end{equation}
The following conditions are equivalent:
\begin{description}
\item[(i)] for some $n\geq 1$, the number $2^n k$ is a cototient;
\item[(ii)] for every $n\geq 1$, the number $2^n k$ is a cototient.
\end{description}
\end{lemma}
\begin{proof} It is clear that (ii) implies (i), so it is enough to show that (i) implies (ii).
Assume that (i) holds and let $n_0\ge 1$ be minimal such that $2^{n_0}k=m-\phi(m)$ for some positive integer $m$. Since $2^2-1=3$ is prime and $k$ is a Riesel number,
it follows that $k\ge 3$, so $m\ge 6$. In particular, $\phi(m)$ is even. The equation $2^{n_0} k=m-\phi(m)$ implies that $m$ is even.
Consider the case $n_0>1$. If $4\mid \phi(m)$, then $4\mid m$ and $2^{n_0-1}k=(m/2)-\phi(m/2)$, contradicting the minimality of $n_0$. So, $m\ge 6$ is even and $2\| \phi(m)$ showing that $m=2q^e$ for some odd prime $q$
and positive integer exponent $e$. But then
$$
2^{n_0}k=m-\phi(m)=2q^e-q^{e-1}(q-1)=q^{e-1}(q+1).
$$
If $e>1$, then $q=P(k)=p$ and $e-1=\nu_p(k)$. Since $k$ is odd, we get $\nu_2(p+1)=n_0$. Thus,
$$
2^{\nu_2(p+1)}k=p^{\nu_p(k)}(p+1),
$$
which we assumed not to hold. If $e=1$, then $2^{n_0}k-1=q$ is prime, contradicting the fact that $k$ is Riesel.
Thus, $n_0=1$. Since $m$ is even, we have $2k=m-\phi(m)$ and $m$ is even. Hence, for all $n\ge 1$, we have $2^nk=(2^{n-1}m)-\phi(2^{n-1}m)$ is a cototient, which is (ii).
\end{proof}
In particular, if we want $k$ to be a Riesel number such that $2^nk$ is a noncototient for all $n$, it suffices to do two things:
\begin{itemize}
\item[(i)] Check condition \eqref{eq:*}.
\item[(ii)] Check that $2k$ is a noncototient.
\end{itemize}
Given $k$, condition (i) is immediate to check. For (ii), we need to see whether there is a representation $2k=m-\phi(m)$ for some positive integer $m$. As we said, if this is so then $m$ is even, so $\phi(m)\le m/2$; hence, $2k=m-\phi(m)\ge m/2$, showing that $m\le 4k$.
Further, $m\equiv 2\pmod 4$. Entry \seqnum{A101036} lists $28$ Riesel numbers, with the largest one being $3580901<4\times 10^6$. If one of them say $k$ is such that $2k=m-\phi(m)$, then $m=2(2\ell+1)$ for some $\ell<4\times 10^6$. We generated with Mathematica
the set of numbers of the form
$$
\{m-\phi(m): m\equiv 2(2\ell+1),~\ell<4\times 10^6\}.
$$
There are $2117016$ such numbers. We intersected this set with the set
of numbers of the form $2k$, where $k$ runs through the 28 Riesel numbers
appearing in \href{A101036}.
Of these $28$, only $16$ numbers $k$ survived.
All of them passed condition \eqref{eq:*} but $6$ of them were primes. The remaining $10$ are displayed in the statement of Theorem \ref{thm:1}.
\section{The proof of Theorem \ref{thm:2}}
\begin{proof} Let us recall how one constructs Riesel numbers. Consider a
system of triples $\{ (a_i,b_i,p_i)\}_{i=1}^t$ of integers that
satisfies the following two properties:
\begin{description}
\item[cov] For every $n\in \mathbb{Z}$, there exists $i\in\{1,2,\ldots,t\}$ such that
$n\equiv a_i \pmod{b_i}$,
\item[ord] the numbers $p_1,\ldots,p_t$ are prime, pairwise distinct and
$p_i\,|\,2^{b_i}-1$ for $i=1,2,\ldots,t$.
\end{description}
Such covering progressions appeared in Erd\H os work \cite{erdos} in the context of proving that there are infinitely many odd integers not of the form $2^n+p$, where $p$ is some prime. As for Riesel numbers,
any odd positive integer $k$ solving the system of congruences
\begin{equation} \label{csries}
k \equiv 2^{-a_i}\pmod{p_i},\quad i = 1,2,\ldots,t,
\end{equation}
fulfilling in addition the inequality $k \geq \max\{p_1,\ldots, p_t\}$, is a Riesel number.
In addition to these congruences, we also want $k$ to satisfy \eqref{eq:*}. Assuming that $\nu_p(k)=1$, we impose the additional condition $2^{\nu_2(p+1)}k=p(p+1)$. Note that if
$k$ satisfies the above equation, then $p=P(k)$.
Consider the system of triples
$$
\{ (a_i,b_i,p_i)\}_{i=1}^7
= \{(1,2,3), (2,4,5), (4,8,17), (8,16,257), (16,32,65537),
$$
$$
(32,64,6700417), (0,64,641)\},
$$
which is known to fulfill conditions \textbf{cov} and \textbf{ord} (see \cite{filaseta}).
We note that $2^{a_i} \equiv \pm 1 \equiv 2^{-a_i} \pmod {p_i}$, for every $i=1,\ldots,7$. Choosing $\nu_2(p+1)=30$, the equation $2^{30}k=p(p+1)$ implies
$$
2^{30-a_i}\equiv p(p+1)\pmod {p_i}
$$
for $i=1,2,\ldots,7$. One checks that the quadratic equations $2^{30-a_i}\equiv x(x+1)\pmod {p_i}$ have an integer solution $x$ for each $i=1,\ldots,7$. The condition $\nu_2(p+1)=30$ is equivalent to
$p\equiv 2^{30}-1\pmod {2^{31}}$. Thus, by the Chinese Remainder Lemma there is an odd integer $x$ coprime to $p_1p_2\cdots p_7$ such that the residue class $x$ modulo $2^{31}p_1\cdots p_7$ satisfies all the above congruences.
By Dirichlet's theorem on primes in arithmetic progressions, there are infinitely many prime numbers $p$ in the above progression. For example,
$$
p=151673607358419855439422291967
$$
satisfies all the above congruences. With each such prime $p$, the number $k=p(p+1)/2^{30}$ is a Riesel number satisfying the required
property, namely that $2^n k$ is a cototient for
all $n\ge 1$. These numbers resemble Riesel numbers that are perfect powers, which have been studied in \cite{filaseta}.
\end{proof}
\section{Acknowledgments}
We thank the referee for a careful reading of the manuscript and
suggestions that led to the current formulation of Theorem \ref{thm:2}
and proofs of our results. During the preparation of this paper,
V.~J.~M.~H. was supported by Grant UAM-A.
\begin{thebibliography}{9}
\bibitem{browkinschinzel}
J. Browkin and A. Schinzel, On integers not of the form $n - \varphi(n)$, {\it Colloq. Math.} {\bf 68} (1995), 55--58.
\bibitem{erdos}
P. Erd\H os, On integers of the form $2^k + p$ and some related problems, {\it Summa Brasil. Math.} {\bf 2}
(1950), 113--123.
\bibitem{flammenluca}
A. Flammenkamp and F. Luca, Infinite families of noncototients, {\it Colloq. Math.} {\bf 86}
(2000), 37--41.
\bibitem{filaseta} M. Filaseta, C. Finch, and M. Kozek,
On powers associated with Sierpi\'nski numbers, Riesel
numbers and Polignac's conjecture, {\it J. Number Theory} {\bf 128} (2008), 1916--1940.
\bibitem{grytczukmed}
A. Grytczuk and B. M\c{e}dryk, On a result of
Flammenkamp-Luca concerning noncototient sequence,
{\it Tsukuba J. Math.} {\bf 29} (2005), 533--538.
\bibitem{riesel} H. Riesel, N\aa gra stora primtal,
{\it Elementa} {\bf 39} (1956), 258--260.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 11A51; Secondary 11A07, 11N25.
\noindent \emph{Keywords: } Riesel number, cototient.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence \seqnum{A101036}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 9 2021;
revised version received March 10 2021; October 15 2021.
Published in {\it Journal of Integer Sequences}, October 17 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}