<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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&gt;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&gt;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&lt;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&lt;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&lt;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}

                                                                                

</pre></body></html>