5
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure if we can get a general formula... $\endgroup$ – Daniel May 10 '15 at 17:22
  • 4
    $\begingroup$ 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. $\endgroup$ – André Nicolas May 10 '15 at 17:28
  • $\begingroup$ Isn't this something like the sum of all primitive roots across divisors? $\endgroup$ – abnry Jun 1 '15 at 16:54
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jose Paternina Jun 1 '15 at 23:35
  • $\begingroup$ @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. $\endgroup$ – Gottfried Helms Jun 2 '15 at 1:42
  • $\begingroup$ 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$. $\endgroup$ – Jose Paternina Jun 2 '15 at 16:28
0
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Jose Paternina Jun 2 '15 at 20:25
  • $\begingroup$ @JosePaternina I expanded my answer. $\endgroup$ – Alex W Jun 2 '15 at 21:15
  • $\begingroup$ Thanks, do you have some reference in where this theory is developed? $\endgroup$ – Jose Paternina Jun 2 '15 at 21:20
  • $\begingroup$ @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. $\endgroup$ – Alex W Jun 2 '15 at 21:25
  • $\begingroup$ @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. $\endgroup$ – Alex W Jun 2 '15 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.