\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} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Note on a Theorem of Rotkiewicz } \vskip 1cm \large Gombodorj Bayarmagnai \\ Department of Mathematics \\ National University of Mongolia\\ Baga Toirog \\ Ulaanbaatar 14200\\ Mongolia\\ \href{mailto:bayarmagnai@smcs.num.edu.mn}{\tt bayarmagnai@smcs.num.edu.mn}\\ \end{center} \vskip .2 in \begin{abstract} In 1961, Rotkiewicz presented a generalisation of the well-known fact that $n$ divides $\varphi(a^n-1)$ for all positive integers $n$ and $a>1$, where $ \varphi$ is Euler's totient function. In this note, we extend his result to values of cyclotomic polynomials. \end{abstract} \section{Introduction} Let $ \varphi$ be the Euler's totient function. It is well known that $n \mid \varphi( a^n-1)$ for all positive integers $n$ and $a > 1$ (see, e.g., Gunderson \cite{Gud}). Let $ \Phi_k$ be the homogeneous cyclotomic polynomial of order $k$, and let $d(n)$ be the number of divisors of $n$. Rotkiewicz \cite{Ro} generalized the above result as follows: $$ n^{\frac{d(n)}{2}}\ \bigl|\ \varphi(\Phi_1(a^n,b^n)) $$ for all positive integers $a,b\ (a>b)$ and $n$. In this note we extend this result to values of cyclotomic polynomials. \begin{theorem} Let $n$ and $k$ be relatively prime positive integers. For all positive integers $a,b$ $(a>b)$ we have $$ k^{ \alpha } n^{ \frac{ d (n) }{2} } \mid \varphi( \Phi_k (a^n, b^n) ), $$ where \begin{displaymath} \alpha= \begin{cases} d(n)-1, & \text{if $a=2b$ and $ke=6$ for some $e\mid n$}; \\ d(n), & \text{otherwise.} \end{cases} \end{displaymath} \end{theorem} Note that the case of $k =2$ was discussed in Rotkiewicz \cite[Theorem 2]{Ro}. Fix positive integers $a, b$ $(a>b)$ and $k$, and define a sequence $( V_n^{ (k) } )_{n \geq 1}$ by setting $V_n^{(k)} = \Phi_k ( a^n, b^n )$. Since $\Phi_k$ is homogeneous, we may assume without loss of generality that $a$ and $b$ are relatively prime. For convenience, we recall the notion of arithmetic primitive factor introduced in Birkhoff-Vandiver \cite{BV} in the following way. A prime of $V_n^{ (k)}$ is called a primitive prime factor of the term if it does not divide any $V_m^{(k)}$ for proper divisors $m$ of $n$. We consider the arithmetic primitive factor of $V_n^{(k)}$ given by the product $$ P_n^{(k)}=\prod_pp^{v_p(V_n^{(k)})}, $$ where $p$ runs through all primitive prime factors of the term. Here, $v_p(n)$ denotes the exponent of $p$ in the decomposition of $n$. If $n$ and $k$ are relatively prime then it follows from the identity \begin{align}\label{identity} \Phi_k(a^n,b^n)=\prod_{e\mid n} \Phi_{ke}(a,b) \end{align} that $P_n^{(k)}$ divides $\Phi_{kn}(a,b)$. \section{Proof} Let $n$ be an integer relatively prime to a prime $p$, and let ${\rm ord}_p(n)$ be the order of $n$ modulo $p$. We now state the following useful lemma. \begin{lemma}\label{lemma} Let $p$ be a prime not dividing $b$. Then \begin{align*} &(a)\ \ v_p(\Phi_k(a,b))\ne 0\text{ if and only if } k=p^{v_p(k)}{\rm ord}_p(ab^{-1}), \\ &(b)\ \ \text{ if } v_p(k)\ne0 \text{ then } v_p(\Phi_k(a,b))\leq1\ (except\ k = p = 2). \end{align*} \end{lemma} \begin{proof} See Roitman \cite{Roi}. \end{proof} \begin{proof}[Proof of Theorem] Let $d$ be a divisor of $n$. The identity (\ref{identity}) implies that every primitive prime of $ V^{(1)}_{kd} $ is a factor of $P_d^{(k)}$. Hence, by Zsigmondy's theorem, $P_d^{(k)} \ne 1$ if \begin{align}\label{condition} (kd,a,b)\neq (6, 2, 1). \end{align} Under the condition (\ref{condition}), we claim that $P_d^{(k)}$ has a prime factor not dividing $kd$. Suppose that $p$ is a prime of $kd$ dividing $ \Phi_{kd} (a, b)$. Then Lemma~\ref{lemma}$(a)$ implies that $ kd/p^{v_p(kd)} < p$ and so $p$ is the largest prime of $kd$. Thus, by Lemma~\ref{lemma}$(b)$, $p$ is the greatest common divisor of $kd$ and $\Phi_{kd} (a, b)$. Hence, if the claim is not true, then it follows that $P_d^{ (k) }$ equals the largest prime of $kd$. Moreover, it also equals the primitive factor $P^{(1)}_{kd}$. But this contradicts to the fact that $P_n^{ (1) }$ is prime to $p$ if the largest prime $p$ of $n$ is a factor of $V_n^{ (1) }$ (see Birkhoff-Vandiver \cite[Theorem 4 ]{BV}). Next we have that the primitive factors $P_d^{(k)}$ are pairwise relatively prime. Indeed, if $p$ is a factor of $P_{d_1}^{(k)}$ and $P_{d_2}^{ (k)}$ then we may apply Lemma~\ref{lemma}$(a)$ to conclude that $d_1/d_2$ is a power of $p$. Hence, $p$ is not a primitive factor of one of $V_{ d_1}^{ (k) }$ and $V_{ d_2}^{ (k) }$. This is a contradiction. Assume that (\ref{condition}) holds for each factor $d$ of $n$. Let $q$ be a prime factor of $ P_d^{(k)}$ not dividing $kd$. Then it follows from Lemma~\ref{lemma}$(a)$ that $kd\mid q-1$. Hence we obtain \begin{align}\label{case} k^2n\ \bigl|\ \varphi\bigl(P_{d}^{(k)})\varphi(P_{\frac{n}{d}}^{(k)}\bigl) \end{align} for each $d$ such that $n\ne d^2$. Thus, it is now clear that the factor $\prod_{ d \mid n} \varphi(P_d^{(k)})$ of $\varphi(V_n^{(k)})$ is divisible by $k^{d(n)}n^{\frac{d(n)}{2}}$. It remains to consider only the case $(kd,a,b) = (6, 2, 1)$ with $d\mid n$. In this case we have \begin{displaymath} P^{(k)}_{\frac{6}{k}}= \begin{cases} 1, & \text{ if $k$ is 1 or 2; } \\ 3, & \text{ otherwise. } \end{cases} \end{displaymath} Thus, (\ref{case}) implies that $kn \bigl|\ \varphi\bigl(P_{\frac{6}{k}}^{(k)})\varphi(P_{\frac{nk}{6}}^{(k)}\bigl)$ for $k=3, 6$. When $k=2$, we combine (\ref{case}) with the fact that $2^3+1\mid V_n^{(2)}$. If $k=1$ then $P_{3}^{(1)}=7$ and so $$n^2 \bigl|\ \varphi(P_{3}^{(1)}P_{\frac{n}{3}}^{(1)})\varphi(P_{\frac{n}{6}}^{(1)}\bigl)$$ as in the previous case. This completes the proof. \end{proof} \section {Acknowledgment}\label{acknowledge} The author would like to thank the referee for carefully reading the paper and for some suggestions. \begin{thebibliography}{5} \bibitem{BV} G. D. Birkhoff and H. S. Vandiver, On the integral divisors of $a^n-b^n$, {\it Ann. of Math.} \textbf{5} (1904), 173--180. \bibitem{Gud} N. G. Gunderson, Some theorems on the Euler $\phi$-function, {\it Bull. Amer. Math. Soc.} \textbf{49} (1943), 278--280. \bibitem{Ro} A. Rotkiewicz, On the numbers $\varphi(a^n\pm b^n)$, {\it Proc. Amer. Math. Soc.} \textbf{12} (1961), 419--421. \bibitem{Roi} M. Roitman, On Zsigmondy primes, {\it Proc. Amer. Math. Soc.} \textbf{125} (1997), 1913--1919. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A25; Secondary 11B83. \noindent \emph{Keywords: } Euler's totient function, primitive factor, cyclotomic polynomial. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 25 2014; revised versions received February 4 2015; February 13 2015; February 14 2015. Published in {\it Journal of Integer Sequences}, February 14 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}