# Solutions of the equation $X^n-1\equiv 0$ (mod $m$)?

How many solutions does the equation $X^n-1\equiv 0$ (mod $m$) have? It is obvious that if $m$ and $n$ are primes with $n|m-1$ then there exist $n$ solutions, otherwise there is only one ($X=1$). Is there any similar result for arbitrary $m,n\in\mathbb{Z}$?

In order to solve this, I think it would be useful to know a result which is an inmediate consequence of the CRT, i.e.: If $m=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$, then $X^n-1\equiv 0$ (mod $m$) iff $X^n-1\equiv 0$ (mod $p_i^{\alpha_i}$) for each $i=1\cdots r$.

• I'm not sure if we can get a general formula... – Daniel May 10 '15 at 17:22
• Your idea will work, moduli that are powers of an odd prime can be dealt with, for such moduli have a primitive root. Powers of $2$ require special treatment. – André Nicolas May 10 '15 at 17:28
• Isn't this something like the sum of all primitive roots across divisors? – abnry Jun 1 '15 at 16:54

For the primefactors of $m$ this is a multiplicative function.

Consider the function $f_b(n) = b^n-1$ with some fixed given $b$ and varying $n$ and then divisibility $f_b(n) \equiv 0 \pmod p$ where $p$ is a prime and $\gcd(b,p)=1$. Then we know from Fermat and Euler that this is periodic with $n$ for each base $b$ and primefactor $p$ where also $\gcd(b,p)=1$. If the modular base is $m$ and not prime but composite, this requires a bit difficult notation so I introduce a handful of notational shortcuts.

Some notational utilities
So let's define a function: $$\lambda_b(p) = \text{least n \gt 0 such that f_b(n) is divisible by p }$$ For instance $\lambda_2(7) = 3$ because in $2^n-1 = 2^3-1 = 7$ the smallest $n$ making the expression divisible by $7$ is $n=3$.
For more compact notation I introduce alwo two "operators": $$\begin{array}{}[a:b] &= \left\{ \begin{array}{} 1 & \text{if b divides a} \\ 0 & \text{if b does not divide a} \end{array} \right. \\ \{a,p\} &= \text{exponent in highest power of p which divides a} \end{array}$$ (The latter is sometimes, for instance in the Pari/GP-software, called the (padic)-"valuation")
For example $\{2^{21}-1,7\} = 2$ because $2^{21}-1$ is divisible by $7^2$.

Next let's denote the exponent, to which the prime $p$ occurs in $f_b(n)$ where $n$ is such minimal value: $$\alpha_b(p) = \{b^{\lambda_b(p)}-1,p\}$$ So, for instance $\alpha_2(7) = \{2^3 - 1, 7\} = 1$ but $\alpha_3(11) = \{3^5 - 1, 11\} = 2$ and also $\alpha_2(1093) = \{2^{\lambda_2(1093)} - 1, 1093\} = 2$, the last equation refering to the so-called "Wieferich-prime" $p=1093$.

Then it can be proven, that for odd primes $p \gt 2$ $$\{b^n -1, p\}= [n:\lambda_b(p)]\left(\alpha_b(p) + \{ n, p \} \right) \tag 1$$

A version for your formula, $m$ odd, $\gcd(X,m)=1$ .

After that, it is easy to find an expression for your $X$ and (odd) $m$ as far as $\gcd(X,m)=1$. Let's write $m$ in its canonical prime-factor decomposition: $$m =p_1^{w_1} \cdot p_2^{w_2} \cdot ... \cdot p_h^{w_h} \tag {2.1}$$ On the other hand, by the canonical primefactor-decomposition of $f_b(n)$ we have $$X^n-1 = p_1^{u_1} \cdot p_2^{u_2} \cdot ... \cdot p_h^{u_h} \\ \qquad = p_1^{[n:\lambda_X(p_1)] \cdot( \alpha_X(p_1) + \{n,p_1\})} \cdot p_2^{[n:\lambda_X(p_2)] \cdot( \alpha_X(p_2) + \{n,p_2\})} \cdot ... \cdot p_h^{[...](...)} \tag {2.2}$$ So $n$ must, first, be a multiple of the least common multiple of the $\lambda$'s $$n = t \cdot \text{lcm} (\lambda_X(p_1), \lambda_X(p_2), ... ,\lambda_X(p_h)) \tag 3$$

Let's assume, that this is given by some suitable $n$.
Then moreover $n$ must also contain the primefactors $p_1$ to $p_h$ to such powers, that the exponents $w_1,w_2,w_3,...,w_h$ of the primefactors in $m$ are also at least equalled by the $u_1,u_2,u_3,...,u_h$. So for each primefactor $p_k$ we must have: $u_k \ge w_k$ and from $$u_k = [n : \lambda_X(p_k)] \cdot ( \alpha_X(p_k) + \{n,p_k\} ) \tag 4$$ we get the inequality $$\{n,p_k \} \ge w_k -\alpha_X(p_k) \tag 5$$

Example. Let $m=2835 = 3^4 \cdot 5 \cdot 7$ and $X = 26$ then from $m$ we have: $$\begin{array} {} w_1 = 4 & w_2 = 2 & w_3 = 1 \end{array} \\$$ The expression $X^n-1$ must contain (at least) the same prime-factors. Thus we get: $$\begin{array} {} p_1=3 & \lambda_X(3)=2 & \alpha_X(3)=3 \\ p_2=5 & \lambda_X(5)=1 & \alpha_X(5)=2 \\ p_3=7 & \lambda_X(7)=6 & \alpha_X(7)=1 \\ \end{array}$$ So $n$ must be (a multiple of) the lcm of all that $\lambda$'s: $$n = t \cdot \text{lcm}(2,1,6)=6$$ From this we know, that $n$ must be a multiple of $6$.

Next we must make sure, that $n$ is such that the primefactors shall occur in (at least) the required multiplicities: $$\begin{array} {} u_1 \ge w_1=4 & \to & 3+\{n,3\} \ge 4 & \to & \{n,3\} \ge 1 \\ u_2 \ge w_2=2 & \to & 2+\{n,5\} \ge 2 & \to & \{n,5\} \ge 0 \\ u_3 \ge w_3=1 & \to & 1+\{n,7\} \ge 1 & \to & \{n,7\} \ge 0 \\ \end{array}$$ From the first line of that last block we have that $n$ must also contain the primefactor $3$, but this is already given by the previous assumption. The primefactors $5$ and $7$ are automatically of sufficient exponents, so the example modular equation is valid for a minimal $n=6$ and we get indeed $$\{26^6 - 1 , 2835\} = 1$$ that $X^n -1$ is divisible by $m$.

For even $m$ (containing the primefactor 2) this requires a small tweak with an extension.

P.s. I've done this in a small study; unfortunately the text is not yet nicely finished, but it might be useful to understand the above. See here

• Thanks for your answer, it is a really nice approach. Also thanks for your notes, they are clear, but I'm still not sure how to apply all of that to answer the question. – Jose Paternina Jun 1 '15 at 23:35
• @Jose - Hmm, perhaps I've not yet correctly understood your question. For instance, since there are infinitely many primes which we could insert into $n$ and also into $m$ - in which way is the "number of solutions" finite at all? What I've tried to give so far is a general formula, because the simple least-common-multiple using the $\lambda$-function (which means also the "order of multiplicative cyclic group modulo m") does not suffice to describe the solutions. – Gottfried Helms Jun 2 '15 at 1:42
• There is a result regarding the existence of nontrivial solutions for this problem, which is: If we note by $f(m,n)$ the number of solutions of the equation $X^n-1\equiv0$ (mod $m$), then $f(m,n)=1$ iff $gcd(m,n)=1$. Otherwise, $f(m,n)>1$. Your approach can't be applied because it restricts the election of $m$ and $n$. – Jose Paternina Jun 2 '15 at 16:28

If $m,n$ are primes and $X$ isn't a multiple of $n$ you can use the Little Fermat's theorem $$X^{k(n-1)}-1\equiv 0 \pmod n$$ with $m=k(n-1)$ I don't think there exist a general formula.

• I think this is true if $X$ isn't a multiple of $n$, in order to apply FLT. – Jose Paternina May 10 '15 at 17:46
• yes I edited it – Domenico Vuono May 10 '15 at 17:53

Below all groups are finite and abelian. For a ring $R$ it's group of invertible elements we denote $R^*$. For any $n\in\mathbb{Z}$ and group $G$ we denote $e_n(G):=\{g\in G:g^n=1\}$. It is clear, that $e_n(G)\leq G$ and if $G\simeq G_1\times\ldots\times G_l$ for some groups $G_1,\ldots,G_l$, then $e_n(G)\simeq e_n(G_1)\times\ldots\times e_n(G_l)$. Since $\mathbb{Z}_m=\mathbb{Z}_{-m}$, it is enough to consider the case $m>0$. Further $n\in\mathbb Z$.

Lemma. Let $n\in\mathbb Z$ and $G$ be a finite cyclic group. Then $|e_n(G)|=\gcd(n,|G|)$.

Proof. Denote $d=\gcd(n,|G|)$, $E=e_n(G)$. As we know, $E\leq G$. Since $G$ is cyclic, then $E$ is cyclic too, hence $E=\langle a\rangle$ for some $a\in G$ and $|E|=|a|$. Since $a\in E$, then $a^n=1$, hence $|a|\shortmid n$. Since $a\in G$, then $a^{|G|}=1$, hence $|a|\shortmid |G|$. Therefore $|a|\shortmid\gcd(n,|G|)$. Since $G$ is cyclic and $d\shortmid |G|$, then there exists subgroup $E'\leq G$ of order $d$. If $g\in E'$, then $1=g^{|E'|}=g^d$, hence $g^n=1$, as $d\shortmid n$. We see, that $E'\leq E$, hence $d=|E'|\shortmid|E|=|a|$. So $|a|\shortmid d$ and $d\shortmid |a|$, thus $|E|=|a|=d$ $\Box$.

Note that number of solutions of the equation $x^n\equiv 1\pmod m$ is equal to $|e_n(\mathbb{Z}_m^*)|$. Let $m=p_1^{\alpha_1}\ldots p_l^{\alpha_l}$, where $p_i$ - distinct prime numbers, $p_1=2$, $\alpha_i\in \mathbb{Z}_{\geq 0}$. By the chinese remainder theorem $\mathbb{Z}_m\simeq\mathbb{Z}_{p_1^{\alpha_1}}\times\ldots\times\mathbb{Z}_{p_l^{\alpha_l}}$, hence $\mathbb{Z}_m^*\simeq\mathbb{Z}_{p_1^{\alpha_1}}^*\times\ldots\times\mathbb{Z}_{p_l^{\alpha_l}}^*$ and $e_n(\mathbb{Z}_m^*)\simeq e_n(\mathbb{Z}_{p_1^{\alpha_1}}^*)\times\ldots\times e_n(\mathbb{Z}_{p_l^{\alpha_l}}^*)$. In such a way $|e_n(\mathbb{Z}_m^*)|=\prod_{i=1}^l |e_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|$. It remains to find $|e_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|$ for all $i$. If $p_i\neq 2$, then group $\mathbb{Z}_{p_i^{\alpha_i}}^*$ is cyclic, hence $$|e_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|=\gcd(n,|\mathbb{Z}_{p_i^{\alpha_i}}^*|)=\gcd(n,\phi(p_i^{\alpha_i})).$$ Let $p_i=2$, i.e. $i=1$. If $\alpha_1\in\{0,1\}$, then $\mathbb{Z}_{2^{\alpha_1}}^*=\{1\}$ and $|e_n(\mathbb{Z}_{2^{\alpha_1}}^*)|=1$. If $\alpha_1=2$, then $\mathbb{Z}_{2^{\alpha_i}}^*$ is a cyclic group of order $2$, hence $|e_n(\mathbb{Z}_{2^{\alpha_i}}^*)|=\gcd(n,2)$. If $\alpha_i\geq 3$, then $\mathbb{Z}_{2^{\alpha_i}}^*\simeq\mathbb{Z}_2\times\mathbb{Z}_{2^{\alpha_i-2}}$ and $$|e_n(\mathbb{Z}_{2^{\alpha_i}}^*)|=|e_n(\mathbb{Z}_2)| |e_n(\mathbb{Z}_{2^{\alpha_i-2}})|=\gcd(n,2)\gcd(n,2^{\alpha_i-2}).$$

We have proved the following statement: Number of solutions of the equation $x^n\equiv 1\pmod m$ is equal to $c\prod_{i=2}^l \gcd(n,\phi(p_i^{\alpha_i}))$, where $c=1$ if $\alpha_1\in\{0,1\}$, $c=\gcd(n,2)$ if $\alpha_1=2$ and $c=\gcd(n,2)\gcd(n,2^{\alpha_1-2})$ if $\alpha_1\geq 3$.

• Why is it that $|e_n(\mathbb{Z}_{p^{\alpha_i}}^*)|=gcd(n,|\mathbb{Z}_{p^{\alpha_i}}^*|)$? Does it have something to do with the fact that if $|b|=n$ then $|b^k|=n/gcd(n,k)$? – Jose Paternina Jun 2 '15 at 20:25
• @JosePaternina I expanded my answer. – Alex W Jun 2 '15 at 21:15
• Thanks, do you have some reference in where this theory is developed? – Jose Paternina Jun 2 '15 at 21:20
• @JosePaternina This technique is often used in the theory of groups. As far as I remember similar arguments are used, for example, when analyzing the Miller–Rabin primality test. – Alex W Jun 2 '15 at 21:25
• @JosePaternina The theory that I used can be found in any good textbook on the theory of finite groups, for example Kurzweil, Stellmacher, The Theory of Finite Groups. – Alex W Jun 2 '15 at 21:29