Let $m,n$ be an integer. Denote by ${\rm O}\_n(m)$ be the multiplicative order of $m$ modulo $n$. I want to know what is the possible values of $\frac{m^{{\rm O}\_n(m)}-1}{n}$. Is it true that for fixed $m$, for any integer $N$, we can find $n=n(m,N)$ such that $N$ is a factor of $\frac{m^{{\rm O}\_n(m)}-1}{n}$?


Thanks.



The multiplicative order of $m$ modulo $n$
If $m$ and $N$ are not coprime, then $n=n(m,N)$ does not exist. Indeed, $m^{{\rm O}\_n(m)}\equiv 1\pmod{nN}$ implies that $m$ and $N$ are coprime.


If $m$ and $N$ are coprime, then $n=n(m,N)$ exists. To see this, we shall use [Zsigmondy's theorem](https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem): for any $\ell>6$ there exists a primitive prime divisor $p\mid m^\ell-1$, where primitive means that $p\nmid m^k-1$ for any integer $0<k<\ell$. In particular, the primitive prime divisors corresponding to the exponents $\ell=j\varphi(N)$ for $j\in\{7,8,\dots,N+7\}$ are all distinct, hence the largest of them exceeds $N$. So there exists a prime number $p>N$ and a positive integer $j$ such that $p\mid m^{j\varphi(N)}-1$ and $p\nmid m^k-1$ for any integer $0<k<j\varphi(N)$. In particular, ${\rm O}\_p(m)=j\varphi(N)$, and $m^{{\rm O}\_p(m)}-1=m^{j\varphi(N)}-1$ is divisible by $N$. As $p$ is coprime to $N$, we conclude that $(m^{{\rm O}\_p(m)}-1)/p$ is also divisible by $N$. That is, $n:=p$ has the required property.


