\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \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} \newtheorem{openproblem}[theorem]{Open Problem} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Extremal Orders of Certain Functions \\ \vskip .1in Associated with Regular Integers (mod $n$) } \vskip 1cm \large Br\u adu\c t Apostol\\ ``Spiru Haret" Pedagogical High School \\ 1 Timotei Cipariu St. \\ RO --- 620004 Foc\c sani \\ Romania\\ \href{mailto:apo_brad@yahoo.com}{\tt apo\_brad@yahoo.com}\\ \ \\ Lucian Petrescu\\ ``Henri Coand\u a" Technical College\\ 2 Tineretului St. \\ RO --- 820235 Tulcea \\ Romania\\ \href{mailto:petrescuandreea@yahoo.com}{\tt petrescuandreea@yahoo.com}\\ \end{center} \vskip .2 in \def\be{\begin{equation}} \def\ee{\end{equation}} \def\bp{\begin{proof}} \def\ep{\end{proof}} \newcommand{\f}{\frac} \newcommand{\q}{\quad} \newcommand{\bc}{\begin{center}} \newcommand{\ec}{\end{center}} \newcommand{\sse}{\subseteq} \begin{abstract} Let $V(n)$ denote the number of positive regular integers (mod $n$) that are $\leq n$, and let $V_k(n)$ be a multidimensional generalization of the arithmetic function $V(n)$. We find the Dirichlet series of $V_k(n)$ and give the extremal orders of some totients involving arithmetic functions which generalize the sum-of-divisors function and the Dedekind function. We also give the extremal orders of other totients regarding arithmetic functions which generalize the sum of the unitary divisors of $n$ and the unitary function corresponding to $\phi(n)$, the Euler function. Finally, we study extremal orders of some compositions, involving the functions mentioned previously. \end{abstract} \section{Introduction}\label{Intro} Let $n>1$ be an integer. An integer $a$ is called regular (mod $n$) if there exists an integer $x$ such that $a^2x \equiv a$ (mod $n$) (sequence \seqnum{A143869} in Sloane's {\it Encyclopedia of Integer Sequences}). Several authors investigated properties of regular integers (mod $n$). Alkam and Osba \cite{oA07}, using ring-theoretic considerations, rediscovered some of the statements proved by Morgado \cite{jM74, jM72}, who showed that $a>1$ is regular (mod $n$) if and only if $\gcd(a,n)$ is a unitary divisor of $n$. T\'oth \cite{lT08} gave direct proofs of some properties, because the proofs of \cite{jM74, jM72} were lengthy and those of \cite{oA07} were ring-theoretical. Let $ \text{Reg}_n=\lbrace{a: 1\leq a \leq n \text{ and $a$ is regular (mod $n$)}}\rbrace$, and $V(n)=\#\text{Reg}_n$. The function $V$ is multiplicative and $V(p^{\alpha})=\phi(p^{\alpha})+1=p^{\alpha}-p^{\alpha-1}+1$, where $\phi$ is the Euler function. Consequently, $ V(n)=\sum_{d\parallel n} \phi(d)$, for every $n\geq 1$, where $d\parallel n$ means that $d$ is a unitary divisor of $n$, that is, $d\mid n$ and $ \gcd(d,\frac{n}{d})=1$. Also $\phi(n)1$, and $V(n)=n$ if and only if $n$ is a squarefree; see \cite{jM72, lT08, oA07}. Thus, the function $V(n)$ is an analogue of the Euler function $\phi(n)$. The function $\phi(n)$ is the sequence \seqnum{A000010} in Sloane's On-Line Encyclopedia of Integer Sequences. Also, the function $V(n)$ is the sequence \seqnum{A055653}; see \cite{Sl}. Apostol and T\'oth \cite{bA12} considered the multidimensional generalization of the function $V(n)$, $V_k(n)$, where $k\geq 1$ is a fixed integer. The function $V_k(n)$ is multiplicative and $V_k(p^{\alpha})=\phi_k(p^{\alpha})+1=p^{\alpha k}-p^{(\alpha -1)k}+1$, where $\phi_k$ is the Jordan function of order $k$. Consequently, $ V_k(n)=\sum_{d\parallel n}\phi_k(d)$, for every $n\geq 1$. Also $\phi_k(n)1$ and $V_k(n)=n^k$ if and only if $n$ is squarefree; see \cite{bA12}. T\'oth \cite{lT08} proved results concerning the minimal and maximal orders of the functions $V(n)$ and $ V(n)/\phi(n)$. Alkam and Osba \cite{oA07} investigated the minimal order of $V(n)$. S\'andor and T\'oth \cite{jS08} and Apostol \cite{Brad1} studied the extremal orders of compositions of certain functions. In Section \ref{Prel} we present some notation and results involving arithmetical functions. Section \ref{Dir} is devoted to the study of the Dirichlet series of $V_k(n)$. Extremal orders of the function $V_k(n)$ in connection with $\sigma_k(n)$ and $\psi_k(n)$ are given in Section \ref{ExtrOrd}. In Section \ref{UnAnalog} we prove some results regarding $V_k(n)$ and unitary analogues of the functions $\sigma_k(n)$ and $\phi_k(n)$. In Section \ref{Comp} we give the extremal orders of some compositions of functions from above. Section \ref{OpProb} provides other limits of compositions of arithmetical functions. We also present some open problems regarding extremal orders of these compositions. \section{Preliminaries}\label{Prel} In what follows let $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}>1$ be a positive integer and let $k\geq 1$ be an integer. Throughout the paper we will use the following notation: \begin{itemize} \item $ p_1, p_2, \ldots$ --- the sequence of the primes; \item $ \sigma_k(n)$ --- the generalization of $\sigma(n)$, defined by $ \sigma_k(n)=\prod_{i=1}^r\frac{p_i^{(\alpha_i+1)k}-1}{p_i^k-1}$ ; \item $ \psi_k(n)$ --- the generalization of $\psi(n)$, defined by $ \psi_k(n)=n^k\prod_{p\mid n}(1+\frac{1}{p^k})$ ; \item $ \zeta(s)$ --- the Riemann zeta function, $ \zeta(s)=\prod_p \biggl(1-\frac{1}{p^s} \biggr)^{-1}$, $s=\sigma+it\in \mathbb{C}$ and $\sigma>1$; \item $ \phi(n)$ --- the Euler function, $ \phi(n)=n\prod_{p\mid n}\biggl(1-\frac{1}{p}\biggr)$; \item $ \phi_k(n)$ --- the Jordan function of order $k$, $ \phi_k(n)=n^k\prod_{p\mid n}\bigl(1-\frac{1}{p^k}\bigr)$; \item $ \gamma$ --- the Euler constant, $\gamma= \lim_{\substack{n \to \infty}}(1+\frac{1}{2}+\ldots +\frac{1}{n}-\log n)$; \item $ \phi^{*}(n)$ --- the unitary analogue of $\phi(n)$, $ \phi^{*}(n)=\prod_{i=1}^{k}(p_i^{\alpha_i}-1)$; \item $ \sigma^{*}(n)$ --- the unitary analogue of $\sigma(n)$, $ \sigma^{*}(n)=\prod_{i=1}^{k}(p_i^{\alpha_i}+1)$. \end{itemize} For other arithmetic functions defined by regular integers modulo $n$ we refer to the papers \cite{hT12, lT09}. Let $f(n)$ be a nonnegative real-valued multiplicative arithmetic function. Let $$ L=L(f):= \limsup_{n\to \infty}\frac{f(n)}{\log \log n}$$ and $$ \rho(p)=\rho(p,f):=\sup_{\alpha \geq 0}f(p^{\alpha})$$ for primes $p$, and consider the product $R=R(f):=\prod_p(1-\frac{1}{p})\rho(p)$. In order to prove the properties below we apply the following results: \begin{lemma}\label{L:1.1}{\rm(T\'oth and Wirsing \cite[Corollary 1]{lT03}).} If $f$ is a nonnegative real-valued multiplicative arithmetic function such that for each prime $p$, \begin{itemize} \item[(i)] $ \rho(p)=\sup_{ \alpha \geq 0}(f(p^{\alpha}))\leq \biggl(1-\frac{1}{p}\biggr)^{-1} $, and \item[(ii)] there is an exponent $e_p=p^{o(1)} \in\mathbb{N}$ satisfying $ f(p^{e_p})\geq 1+\frac{1}{p}$, \end{itemize} then $ \limsup_{n \to \infty}\frac{f(n)}{\log \log n}=e^{\gamma}\prod_p\biggl(1-\frac{1}{p}\biggr)\rho(p).$ \end{lemma} \begin{lemma}\label{L:1.2}{\rm(T\'oth and Wirsing \cite[Theorem 1]{lT03}).} Suppose that $\rho(p)<\infty$ for all primes $p$ and the product $R$ converges unconditionally (i.e., irrespectively of order), improper limits being allowed, then $L\leq e^{\gamma}R$. \end{lemma} \begin{lemma}\label{L:1.3}{\rm(T\'oth and Wirsing \cite[Theorem 3]{lT03}).} Suppose that $\rho(p)<\infty$ for all primes $p$, that for each prime $p$ there is an exponent $e_p=p^{o(1)}\in \mathbb{N}$ such that $ \prod_pf(p^{e_p})\rho(p)^{-1}>0$ and that the product $R$ converges, improper limits being allowed. Then $L\geq e^{\gamma}R$. \end{lemma} \section{Dirichlet series of $V_k(n)$}\label{Dir} Apostol and Petrescu \cite{aB11} studied the Dirichlet series of $V_1(n):=V(n)$. In what follows we give the Dirichlet series of $V_k(n)$ for $k\geq 2$ and some results involving the M\"obius function. \begin{proposition}\label{P:2.1} For every $s=\sigma+it \in \mathbb{C}$ with $\sigma>k+1$, $$\sum_{n\geq 1}\frac{V_k(n)}{n^s}= \zeta(s-k)\zeta(s)\prod_p\bigl (1-\frac{p^{2s-k}+p^s-p^{s-k}}{p^{3s-k}}\bigr ).$$ \end{proposition} \bp Let $ f(n)=\frac{V_k(n)}{n^s}$. We have $$ \sum_{n\geq 1}|f(n)|\leq \sum_{n\geq 1}\frac{1}{n^{\sigma-k}}<\infty,$$ so the series $ \sum_{n\geq 1}\frac{V_k(n)}{n^s}$ converges absolutely for $\sigma >k+1$. Since $V_k$ is multiplicative, $$ \sum_{n\geq 1}\frac{V_k(n)}{n^s} =\prod_p\frac{1}{1-\frac{1}{p^{s-k}}}\cdot \prod_p\frac{1}{1-\frac{1}{p^s}}\cdot \prod_p\bigl (1-\frac{p^{2s-k}+p^s-p^{s-k}}{p^{3s-k}}\bigr ),$$ and the claim follows. \ep \begin{corollary}\label{C: 2.2} Let $s=\sigma+it \in \mathbb{C}$, $\sigma>k+1$. Then $$ \sum_{n\geq 1}\frac{\mu(n)V_k(n)}{n^s}= \prod_p\biggl(1-\frac{1}{p^{s-k}}\biggr)=\frac{1}{\zeta(s-k)}.$$ Also, $$ \sum_{n\geq 1}\frac{\vert\mu(n)\vert V_k(n)}{n^s}= \prod_p\biggl(1+\frac{1}{p^{s-k}}\biggr)=\frac{\zeta(s-k)}{\zeta(2s-2k)}.$$ \end{corollary} \bp For$ f(n)=\frac{\mu(n) V_k(n)}{n^s}$ the series $ \sum_{n\geq 1}\lvert f(n)\rvert$ converges absolutely, so $$ \sum_{n\geq 1}\frac{\mu(n)V_k(n)}{n^s}= \prod_p\biggl(1-\frac{1}{p^{s-k}}\biggr)=\frac{1}{\zeta(s-k)}.$$ For the second assertion take $ f(n)= \frac{\lvert \mu(n)\rvert V_k(n)}{n^s}$. \ep \section{Extremal orders concerning classical generalized arithmetic functions}\label{ExtrOrd} For the quotient $ \frac{\sigma_k(n)}{V_k(n)}$, we notice that $ \frac{\sigma_k(n)}{V_k(n)}\geq1$ for every $n\geq 1$. Since $$\lim_{\substack{p \to \infty\\ p\text{ prime}}}{\frac{\sigma_k(p)}{V_k(p)}}= \lim_{\substack{p \to \infty\\ p\text{ prime}}}\frac{p^k+1}{p^k}=1,$$ we get $$\liminf_{n \to \infty}\frac{\sigma_k(n)}{V_k(n)}=1;$$ hence the minimal order of $ \frac{\sigma_k(n)}{V_k(n)}$ is 1. Now consider the quotient $$\frac{\psi_k(n)}{V_k(n)}.$$ Since $$\frac{\psi_k(n)}{V_k(n)}\geq 1$$ for every $n\geq 1$ and $$ \frac{\psi_k(p)}{V_k(p)}=\frac{p^k+1}{p^k}$$ for every prime $p$, it is immediate that $$ \liminf_{n \to \infty}\frac{\psi_k(n)}{V_k(n)}=1 .$$ Thus, the minimal order of $\frac{\psi_k(n)}{V_k(n)}$ is 1. It is known that $$ \limsup_{n \to \infty}\frac{\sigma(n)}{V(n)(\log \log n)^2}=e^{2\gamma}$$ and $$ \limsup_{n \to \infty}\frac{\psi(n)}{V(n)(\log \log n)^2}=\frac{6}{\pi^2}e^{2\gamma} ;$$ see \cite{Brad1}. Proposition \ref{P:3.1} shows that the maximal order of $ \frac{\sigma_k(n)}{V_k(n)}$ and $ \frac{\psi_k(n)}{V_k(n)}$ is $ \frac{6}{\pi^2}e^{2\gamma}(\log \log n)^2$. \begin{proposition}\label{P:3.1} For $k\geq 2$, $$ \limsup_{n \to \infty}\frac{\sigma_k(n)}{V_k(n)(\log \log n)^2}= \limsup_{n \to \infty}\frac{\psi_k(n)}{V_k(n)(\log \log n)^2}=\frac{6}{\pi^2}e^{2\gamma}.$$ \end{proposition} \bp Take $ f(n)=\sqrt{\frac{\sigma_k(n)}{V_k(n)}}$. Then $$ f(p^{\alpha})=\sqrt\frac{p^{(\alpha+1)k}-1}{(p^k-1)(p^{\alpha k}-p^{(\alpha-1)k}+1)} \leq \sqrt{\frac{p+1}{p-1}}=\rho(p) < \biggl(1-\frac{1}{p}\biggr)^{-1}$$ and $$ f(p^2)=\sqrt \frac{p^{3k}-1}{(p^k-1)(p^{2k}-p^k+1)}\geq 1+\frac{1}{p}$$ for every prime $p$, so $(ii)$ in Lemma \ref{L:1.1} is satisfied. We obtain $$ \limsup_{n \to \infty}\frac{\sqrt{\sigma_k(n)}}{\sqrt{V_k(n)}\log \log n}= \prod_p{\sqrt{1-\frac{1}{p^{2}}}}e^{\gamma}=\sqrt\frac{6}{\pi^2}e^{\gamma},$$ so $$ \limsup_{n \to \infty}\frac{\sigma_k(n)}{V_k(n)(\log \log n)^2}=\frac{6}{\pi^2}e^{2\gamma}.$$ Since $\psi_k(n)\leq \sigma_k(n)$ and for the primes $p$ we have $\psi_k(p)=\sigma_k(p)=p^k+1$, the result for $ \frac{\psi_k(n)}{V_k(n)(\log \log n)^2}$ follows from the previous one. \ep \section{Extremal orders concerning unitary analogues of $\sigma_k$ and $\phi_k$}\label{UnAnalog} In what follows we consider the functions $\sigma_k^{*}(n)$ and $\phi_k^{*}(n)$, representing the generalizations for the sum of the unitary divisors of $n$ and the unitary analogue Euler function, respectively. Let $k\geq 1$ be a fixed integer. We have $ \sigma_k^{*}(n)=\sum_{d\parallel n}d^k$ and $\sigma_k^{*}(p^{\alpha})=p^{\alpha k}+1$. Also, $$ \phi_k^{*}(n):=\sum_{\substack{\gcd(a_1,\ldots,a_k)\in \lbrace{1,2,\ldots,n\rbrace}^k\\\gcd(\gcd(a_1,a_2,\ldots,a_k),n)_{*}=1}}1 =\sum_{d\parallel n}d^k\mu^{*}(\frac{n}{d}),$$ and hence $\phi_k^{*}(p^{\alpha})=p^{\alpha k}-1$. Note that $$\gcd(a,b)_{*}=\max\lbrace d: d\vert a, d\parallel b \rbrace$$ and $\mu^{*}(n)$ is the unitary analogue of the M\"obius function, given by $\mu^{*}(n)=(-1)^{\omega(n)}$, where $\omega(n)$ is the number of distinct prime factors of $n$. The functions $\sigma_k^{*}(n)$ and $\phi_k^{*}(n)$ are multiplicative. Let $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ be the prime factorisation of $n>1$. We obtain $$\phi_k^{*}(n)=(p_1^{\alpha_1 k}-1)\cdots(p_r^{\alpha_r k}-1)\quad \text{and}\quad \sigma_k^{*}(n)=(p_1^{\alpha_1 k}+1)\cdots(p_r^{\alpha_r k}+1).$$ Observe that $\sigma_k^{*}(n)=\sigma_k(n)$ and $\phi_k^{*}(n)=\phi_k(n)$ for all squarefree $n$. Furthermore, for every $n\geq 1$, $$\phi_k(n)\leq \phi_k^{*}(n)\leq n^k\leq \sigma_k^{*}(n)\leq \sigma_k(n).$$ Recall that an integer $n>1$ is called powerful if it is divisible by the square of each of its prime factors. A powerful integer is also called a squarefull integer. We give extremal orders for the quotients $\frac{\sigma_k^{*}(n)}{V_k(n)}$ and $\frac{\phi_k^{*}(n)}{V_k(n)}$, the minimal order of $\frac{\phi_k^{*}(n)}{V_k(n)}$ being studied for powerful numbers. Since $\frac{\sigma_k^{*}(n)}{V_k(n)}\geq 1$ for every $n\geq 1$ and $ \lim_{p \to \infty}\frac{\sigma_k^{*}(p)}{V_k(p)}= \lim_{p \to \infty}\frac{p^k+1}{p^k}=1$ for prime numbers $p$, it follows that $ \liminf_{n \to \infty}\frac{\sigma_k^{*}(n)}{V_k(n)}=1$. If $n$ is powerful, it is easy to see that $ \frac{\phi_k^{*}(n)}{V_k(n)}\geq 1$, taking into account that $ \frac{\phi_k^{*}(p^{\alpha})}{V_k(p^{\alpha})}\geq 1$ for $\alpha\geq 2$. For prime numbers $p$, we notice that $$ \lim_{p \to \infty}\frac{\phi_k^{*}(p^2)}{V_k(p^2)}= \lim_{p\to \infty}\frac{p^{2k}-1}{p^{2k}-p^k+1}=1,$$ which implies that $$ \liminf_{n\to \infty}\frac{\phi_k^{*}(n)}{V_k(n)}=1,$$ so the minimal order of $ \frac{\phi_k^{*}(n)}{V_k(n)}$ is 1. For the maximal orders of these quotients we have \begin{proposition}\label{P:4.1} For $k\geq 1$, $$\limsup_{n\to \infty}\frac{\sigma_k^{*}(n)}{V_k(n)\log \log n}=\limsup_{n\to \infty}\frac{\phi_k^{*}(n)}{V_k(n)\log \log n}=e^{\gamma}.$$ \end{proposition} \bp Take $ f(n)=\frac{\sigma_k^{*}(n)}{V_k(n)}$ in Lemma \ref{L:1.2}, which is a nonnegative real-valued multiplicative arithmetic function. We have $$ f(p^{\alpha})=\frac{p^{\alpha k}+1}{p^{\alpha k}-p^{(\alpha-1)k}+1}\leq \biggl(1-\frac{1}{p}\biggr)^{-1}=\rho(p)<\infty$$ and $R=1$, so $$ \limsup_{n\to \infty}\frac{\sigma_k^{*}(n)}{V_k(n)\log \log n}\leq e^{\gamma}.$$ Now let $ g(n)=\frac{\phi_k^{*}(n)}{V_k(n)}$. Here $$ g(p^{\alpha})=\frac{p^{\alpha k}-1}{p^{\alpha k}-p^{(\alpha-1)k}+1}\leq \biggl(1-\frac{1}{p}\biggr)^{-1}=\rho(p),$$ and $$ R=\prod_p g(p^1)(\rho(p))^{-1}=\prod_p(p^k+1)\cdot \frac{p-1}{p}>0.$$ Hence, by Lemma \ref{L:1.3} we have $$ \limsup_{n\to \infty}\frac{\phi_k^{*}(n)}{V_k(n)\log \log n}\geq e^{\gamma}.$$ It is obvious that $ \phi_k^{*}(n)\leq \sigma_k^{*}(n)$ for every $n\geq 1$. We obtain $$ e^{\gamma}\leq \limsup_{n\to \infty}\frac{\phi_k^{*}(n)}{V_k(n)\log \log n}\leq \limsup_{n\to \infty}\frac{\sigma_k^{*}(n)}{V_k(n)\log \log n}\leq e^{\gamma},$$ which shows that $$\limsup_{n\to \infty}\frac{\sigma_k^{*}(n)}{V_k(n)\log \log n}=\limsup_{n\to \infty}\frac{\phi_k^{*}(n)}{V_k(n)\log \log n}=e^{\gamma},$$ as desired. \ep \begin{corollary}\label{C: 4.2} The maximal order of both $\frac{\sigma_k^*(n)}{V_k(n)}$ and $\frac{\phi_k^*(n)}{V_k(n)}$ is $e^{\gamma}\log\log n$. \end{corollary} \section{Extremal orders regarding compositions of arithmetical functions}\label{Comp} We now move to the study of extremal orders of some composite arithmetic functions. We start with $V_k(V_k(n))$ and $\phi_k(V_k(n))$. We know that $V_k(n)\leq n^k$ for every $n\geq 1$, so $$ \frac{V_k(V_k(n))}{n^{k^2}}\leq \frac{(V_k(n))^k}{n^{k^2}}\leq\frac{(n^k)^k}{n^{k^2}}=1$$ and $$ \lim_{\substack{p \to \infty\\ p\textrm{ prime}}}\frac{V_k(V_k(p))}{p^{k^2}}= \lim_{\substack{p \to \infty\\ p\textrm{ prime}}}\frac{V_k(p^k)}{p^{k^2}}= \lim_{\substack{p \to \infty\\ p\textrm{ prime}}}\frac{p^{k^2}-p^{(k-1)k}+1}{p^{k^2}}=1,$$ so the maximal order of $V_k(V_k(n))$ is $n^{k^2}$. Since $\phi_k(n)\leq n^k$ and $V_k(n)\leq n^k$ for any $n\geq 1$, we have $ \frac{\phi_k(V_k(n))}{n^{k^2}}\leq \frac{(V_k(n))^k}{n^{k^2}}\leq 1$. But $ \lim_{\substack{p \to \infty\\ p\text{ prime}}}\frac{\phi_k(V_k(p))}{p^{k^2}}= \lim_{p \to \infty}\frac{p^{k^2}-p^{(k-1)k}}{p^{k^2}}=1$, so the maximal order of $\phi_k(V_k(n))$ is $n^{k^2}$. The maximal order of $V(\phi(n))$ was investigated in \cite{Brad1}. Using the general idea of that proof, we show \begin{proposition}\label{P:5.1} The maximal order of $V_k(\phi_k(n))$ is $n^{k^2}$. \end{proposition} \bp We will use Linnik's theorem which states that if $\gcd(t,\ell)=1$, then there exists a prime $p$ such that $p \equiv \ell$ (mod $t$) and $p\ll t^c$, where $c$ is a constant (one can take $c\leq 11$). Let $A= \prod_{\substack{kk$. Since $V_k(n)$ is multiplicative, we have \be\label{Eq:1} \frac{V_k(\phi_k(q))}{q^{k^2}}=\frac{V_k(AB)}{(AB+1)^k}=\frac{V_k(A)}{A^k}\cdot \frac{V_k(B)}{B^k}\cdot \frac{(AB)^k}{(AB+1)^k}. \ee Here $ \frac{(AB)^k}{(AB+1)^k}\to 1$ as $x \to \infty$, so it is sufficient to study $ \frac{V_k(A)}{A^k}$ and $ \frac{V_k(B)}{B^k}$. Clearly, \be\label{Eq:2} \frac{V_k(A)}{A^k}=1. \ee We have $ A=\prod_{k(\log x)\sum_{i=1}^{r}b_i$ for sufficiently large $x$. But $ \sum_{i=1}^{r}b_i\geq r$, so $\log B>k\log x$, implying that $ r<\frac{\log B}{\log x}\ll \frac{x}{\log x}$ (by (\ref{Eq:3})). Since $$ \frac{V_k(B)}{B^k}> \prod_{i=1}^{r}\biggl(1-\frac{1}{q_i^k} \biggr)\geq \prod_{i=1}^{r}\biggl(1-\frac{1}{q_i} \biggr)>\biggl(1-\frac{1}{x}\biggr)^r\geq \biggl(1-\frac{1}{x}\biggr)^{O(\frac{x}{\log x})},$$ We obtain \be\label{Eq:4} \frac{V_k(B)}{B^k}>1+O\biggl (\frac{1}{\log x} \biggr). \ee By \eqref{Eq:1}, \eqref{Eq:2}, \eqref{Eq:4} and $ \frac{(AB)^k}{(AB+1)^k}\to 1$ as $x\to \infty$, we obtain \be\label{Eq:5} \frac{V_k(\phi_k(q))}{q^{k^2}}>1+O\biggl (\frac{1}{\log x} \biggr). \ee By relation \eqref{Eq:5}, and since $ \frac{V_k(\phi_k(n))}{n^{k^2}}\leq \frac{(\phi_k(n))^k}{n^{k^2}}\leq 1$, the claim follows. \ep The maximal order of $V(\phi^{*}(n))$ is $n$ (see \cite{Brad1}). For the maximal order of $V_k(\phi^{*}(n))$ we give \begin{proposition}\label{P:5.2} $$\limsup_{n\to \infty}\frac{V_k(\phi^*(n))}{n^k}=1.$$ \end{proposition} \bp We apply the following lemma: If $a$ is an integer, $a>1$, $p$ is a prime number and $f(n)$ is an arithmetical function satisfying $\phi(n)\leq f(n)\leq \sigma(n)$, one has \be\label{Eq:6} \lim_{p\to \infty}\frac{f(N(a,p))}{N(a,p)}=1, \ee where $ N(a,p)=\frac{a^p-1}{a-1}$ (see, e.g., Suryanarayana \cite{dS77}). Since $\phi^{*}(n)\leq n$, it follows that $V_k(\phi^{*}(n))\leq (\phi^{*}(n))^k\leq n^k$, so \be\label{Eq:7} \frac{\sqrt[k]{V_k(\phi^{*}(n))}}{n}\leq 1. \ee Obviously, $ \sqrt[k]{V_k(n)}$ meets the conditions of the lemma. We have \be\label{Eq:8} \lim_{\substack{p \to \infty\\p\text{ prime}}}\frac{\sqrt[k]{V_k(\phi^{*}(2^p)})}{2^p}= \lim_{\substack{p \to \infty\\p\text{ prime}}}\frac{\sqrt[k]{V_k(2^p-1)}}{2^p-1}= \lim_{\substack{p \to \infty\\p\text{ prime}}}\frac{\sqrt[k]{V_k(N(2,p))}}{N(2,p)}=1. \ee Now \eqref{Eq:7} and \eqref{Eq:8} imply $ \limsup_{n\to \infty}\frac{\sqrt[k]{V_k(\phi^{*}(n))}}{n}=1$, and we are done. \ep Apostol \cite{Brad1} proved that \[ \limsup_{n\to \infty}\frac{\sigma(\phi^{*}(n))}{V(\phi^{*}(n))(\log \log n)^2}= \limsup_{n\to \infty}\frac{\sigma(\phi^{*}(n))}{V(\phi^{*}(n))(\log \log \phi^{*}(n))^2}=e^{2\gamma}\] and \[ \limsup_{n\to \infty}\frac{\psi(\phi^{*}(n))}{V(\phi^{*}(n))(\log \log n)^2} \limsup_{n\to \infty}\frac{\psi(\phi^{*}(n))}{V(\phi^{*}(n))(\log \log \phi^{*}(n))^2}=\frac{6}{\pi^2}e^{2\gamma}.\] The maximal orders of $ \frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))}$ and $ \frac{\psi_k(\phi^{*}(n))}{V_k(\phi^{*}(n))}$ are given by \begin{proposition}\label{P:5.3} For $k\geq 2$ we have \begin{itemize} \item[(i)] $ \limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log n)^2}$= $ \limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log \phi^{*}(n))^2}=\frac{6}{\pi^2}e^{2\gamma}$, \item[(ii)] $ \limsup_{n\to \infty}\frac{\psi_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log n)^2}$= $ \limsup_{n\to \infty}\frac{\psi_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log \phi^{*}(n))^2}=\frac{6}{\pi^2}e^{2\gamma}$. \end{itemize} \end{proposition} \bp \noindent (i) Let $$l_1:=\limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log n)^2} \textrm { and } l_2:= \limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log \phi^{*}(n))^2}.$$ Since $\phi^{*}(n)\le n$ for every $n \ge 1$, we have \begin{eqnarray*} l_1 &= &\limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log n)^2} \\ &\le & l_2= \limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log \phi^{*}(n))^2} \\ & \le & \limsup_{m\to \infty}\frac{\sigma_k(m)}{V_k(m)(\log \log m)^2}=\frac{6}{\pi^2}e^{2\gamma}, \end{eqnarray*} by Proposition \ref{P:3.1}. Since $\gcd(n,1)=1$, by Linnik's theorem, there exists a prime number $p$ such that $p \equiv 1$ (mod $n$) and $p\ll n^c$. Let $p_n$ be the least prime such that $p_n \equiv 1$ (mod $n$), for every $n$. Then $n\mid p_n-1$ and $p_n\ll n^c$, so $\log \log p_n\sim \log \log n$. Observe that $a\mid b$ implies $ \frac{\sigma_k(a)}{V_k(a)}\leq \frac{\sigma_k(b)}{V_k(b)}$. If $p^{\beta}\mid p^{\alpha}$ $(\beta\leq \alpha)$, it is easy to see that $ \frac{\sigma_k(p^{\beta})}{V_k(p^{\beta})}\leq \frac{\sigma_k(p^{\alpha})}{V_k(p^{\alpha})}$. The general case follows, taking into account that $ \frac{\sigma_k(n)}{V_k(n)}$ is multiplicative. So, \[ \frac{\sigma_k(\phi^{*}(p_n))}{V_k(\phi^{*}(p_n))(\log \log p_n)^2}= \frac{\sigma_k(p_n-1)}{V_k(p_n-1)(\log \log p_n)^2}\sim \frac{\sigma_k(p_n-1)}{V_k(p_n-1)(\log \log n)^2}.\] On the other hand, $$\frac{\sigma_k(p_n-1)}{V_k(p_n-1)(\log \log n)^2}\geq \frac{\sigma_k(n)}{V_k(n)(\log \log n)^2}.$$ Therefore, $$ \limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))(\log \log n)^2}\geq \limsup_{n\to \infty}\frac{\sigma_k(\phi^{*}(p_n))}{V_k(\phi^{*}(p_n))(\log \log p_n)^2}$$ $$\geq\limsup_{n\to \infty}\frac{\sigma_k(n)}{V_k(n)(\log \log n)^2}=\frac{6}{\pi^2}e^{2\gamma}.$$ We obtain $ \frac{6}{\pi^2}e^{2\gamma}\leq l_1\leq l_2\leq \frac{6}{\pi^2}e^{2\gamma}$, and hence $ l_1=l_2=\frac{6}{\pi^2}e^{2\gamma}$.\\[12 pt] \noindent (ii) The proof is similar to the proof of (i), taking into account that $a\mid b$ implies $ \frac{\psi_k(a)}{V_k(a)}\leq \frac{\psi_k(b)}{V_k(b)}$ and $ \limsup_{n \to \infty}\frac{\psi_k(n)}{V_k(n)(\log \log n)^2}=\frac{6}{\pi^2}e^{2\gamma}$, by Proposition \ref{P:3.1}. \ep So, the maximal orders of both $ \frac{\sigma_k(\phi^{*}(n))}{V_k(\phi^{*}(n))}$ and $ \frac{\psi_k(\phi^{*}(n))}{V_k(\phi^{*}(n))}$ are $ \frac{6}{\pi^2}e^{2\gamma}(\log\log n)^2$. In a similar manner, since $$ \limsup_{n\to \infty}\frac{\sigma_k^{*}(n)}{V_k(n)\log \log n}= \limsup_{n\to \infty}\frac{\phi_k^{*}(n)}{V_k(n)\log \log n}=e^{\gamma}$$ (using Proposition \ref{P:4.1}), the fact that $a\mid b$ implies $ \frac{\sigma_k^{*}(a)}{V_k(a)}\leq \frac{\sigma_k^{*}(b)}{V_k(b)}$ and $ \frac{\phi_k^{*}(a)}{V_k(a)}\leq \frac{\phi_k^{*}(b)}{V_k(b)}$, respectively, it can be shown that $$ \limsup_{n\to \infty}\frac{\sigma_k^{*}(\phi^{*}(n))}{V_k(\phi^{*}(n))\log \log n}= \limsup_{n\to \infty}\frac{\sigma_k^{*}(\phi^{*}(n))}{V_k(\phi^{*}(n))\log \log \phi^{*}(n)}=e^{\gamma}$$ and $$ \limsup_{n\to \infty}\frac{\phi_k^{*}(\phi^{*}(n))}{V_k(\phi^{*}(n))\log \log n}= \limsup_{n\to \infty}\frac{\phi_k^{*}(\phi^{*}(n))}{V_k(\phi^{*}(n))\log \log \phi^{*}(n)}=e^{\gamma}.$$ \section{Open Problems}\label{OpProb} \begin{openproblem} \text{Note that} $$ \liminf_{n\to \infty}\frac{V_k(\phi(n))}{n^k}= \liminf_{n\to \infty}\frac{V_k(\phi^{*}(n))}{n^k}=\liminf_{n\to \infty}\frac{\phi_k^{*}(V(n))}{n^k}=0.$$ For $n_k=p_1\cdots p_r$ (the product of the first $r$ primes), we have $$ \frac{V_k(\phi(n_r))}{n_r^k}= \frac{V_k((p_1-1)\cdots (p_r-1))}{p_1^k\cdots p_r^k}\leq \frac{(p_1-1)^k\cdots (p_r-1)^k}{p_1^k\cdots p_r^k}=\bigl ((1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r})\bigr)^k,$$ so $$ \lim_{r\to \infty}\frac{V_k(\phi(n_r))}{n_r^k}= \lim_{r\to \infty}\bigl((1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r})\bigr)^k=0,$$ similarly the other relations. What are the minimal orders for the $V_k(\phi(n))$, $V_k(\phi^{*}(n))$, and $\phi_k^{*}(V(n))$ ? \end{openproblem} \begin{openproblem} Taking $n_r=p_1\cdots p_r$ (the product of the first $r$ primes), $$ \frac{\sigma_k^{*}(V(n_r))}{n_r^k}=\frac{\sigma_k^{*}(p_1\cdots p_r)}{p_1^k\cdots p_r^k}= \frac{(p_1^k+1)\cdots (p_r^k+1)}{p_1^k\cdots p_r^k}=\bigl((1+\frac{1}{p_1})\cdots (1+\frac{1}{p_r})\bigr)^k\to \infty$$ as $r\to \infty$, so $ \limsup_{n\to \infty}\frac{\sigma_k^{*}(V(n))}{n^k}=\infty$. What is the maximal order for $\sigma_k^{*}(V(n))$ ? \end{openproblem} \section{Acknowledgments} The authors would like to thank the referees for helpful suggestions. \begin{thebibliography}{99} \bibitem{oA07} O. Alkam and E. Osba, On the regular elements in $\mathbb{Z}_n$, {\it Turk. J. Math.} \textbf{32} (2008), 1--9. \bibitem{Brad1} B. Apostol, Extremal orders of some functions connected to regular integers modulo $n$, {\it An. \c Stiin\c t. Univ. ``Ovidius" Constan\c ta, Ser. Mat.} \textbf{21} (2013), to appear. \bibitem{aB11} B. Apostol and L. Petrescu, On the number of regular integers (mod $n$), {\it J. Algebra Number Theory Acad.} \textbf{2} (2012), 337--352. \bibitem{bA12} B. Apostol and L. T\'oth, Some remarks on regular integers modulo $n$, preprint, \url{http://arxiv.org/abs/1304.2699}. \bibitem{hT12} P. Haukkanen and L. T\'oth, An analogue of Ramanujan's sum with respect to regular integers (mod $r$), {\it Ramanujan J.} \textbf{27} (2012), 71--88. \bibitem{jM74} J. Morgado, A property of the Euler $\phi$-function concerning the integers which are regular modulo $n$, {\it Portugal. Math.} \textbf{33} (1974), 185--191. \bibitem{jM72} J. Morgado, Inteiros regulares m\'odulo $n$, {\it Gazeta de Matematica} \textbf{33} (1972), 1--5. \bibitem{jS02} J. S\'andor, {\it Geometric Theorems, Diophantine Equations, and Arithmetic Functions}, American Research Press, 2002. \bibitem{sC04} J. S\'andor and B. Crstici, {\it Handbook of Number Theory II}, Kluwer Academic Publishers, 2004. \bibitem{jS08} J. S\'andor and L. T\'oth, Extremal orders of compositions of certain arithmetical functions, {\it Integers} \textbf{8} (2008), \# A34. \bibitem{rS89} R. Sivaramakrishnan, {\it Classical Theory of Arithmetic Functions}, Marcel Dekker, 1989. \bibitem{Sl} N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}. \bibitem{dS77} D. Suryanarayana, On a class of sequences of integers, {\it Amer. Math. Monthly} \textbf{84} (1977), 728--730. \bibitem{lT09} L. T\'oth, A gcd-sum function over regular integers modulo $n$, {\it J. Integer Seq.} \textbf{12} (2009), Article 09.2.5. \bibitem{lT08} L. T\'oth, Regular integers (mod $n$), {\it Annales Univ. Sci. Budapest., Sect Comp.} \textbf{29} (2008), 263--275. \bibitem{lT03} L. T\'oth and E. Wirsing, The maximal order of a class of multiplicative arithmetical functions, {\it Annales Univ. Sci. Budapest., Sect Comp.} \textbf{22} (2003), 353--364. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A25; Secondary 11N37. \noindent {\it Keywords}: arithmetical function, composition, regular integer (mod $n$), extremal order. \bigskip \hrule \bigskip \noindent(Concerned with sequences \seqnum{A000010}, \seqnum{A000203}, \seqnum{A055653}, and \seqnum{A143869}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 25 2013; revised versions received July 9 2013; July 30 2013; August 5 2013. Published in {\it Journal of Integer Sequences}, August 8 2013. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}