Regular integers modulo n

László Tóth

Published 2007-10-10, updated 2008-09-01Version 3

Let $n=p_1^{\nu_1}... p_r^{\nu_r} >1$ be an integer. An integer $a$ is called regular (mod $n$) if there is an integer $x$ such that $a^2x\equiv a$ (mod $n$). Let $\varrho(n)$ denote the number of regular integers $a$ (mod $n$) such that $1\le a\le n$. Here $\varrho(n)=(\phi(p_1^{\nu_1})+1)... (\phi(p_r^{\nu_r})+1)$, where $\phi(n)$ is the Euler function. In this paper we first summarize some basic properties of regular integers (mod $n$). Then in order to compare the rates of growth of the functions $\varrho(n)$ and $\phi(n)$ we investigate the average orders and the extremal orders of the functions $\varrho(n)/\phi(n)$, $\phi(n)/\varrho(n)$ and $1/\varrho(n)$.