2
$\begingroup$

This open-ended question was originally posted on Twitter here. Specifically,

Problem

Given $a,m \in \mathbb{N}$ with $a, m \gt 1$, find the minimal value $n \in \mathbb{N}$ such that $(a-1)^m \mid a^n - 1$.

Work So Far

Existence

Consider $\frac{a^n - 1}{(a-1)^m}$ and let $b = a - 1$. This gives us $\frac{(b + 1)^n - 1}{b^m} = ... = \sum_{i=1}^{n} {n \choose i} b^{i-m}$

Note that ${n \choose i} b^{i-m} \in\mathbb{N}$ for $i-m\geq0$, so it suffices to look at the range $i \in \{1,2,..,m-1\}$.

Recalling ${n \choose i} = \frac{n(n-1)\cdots(n-i+1)}{i!}$ we can bring the salient terms into the form

$\frac{n((m-1)! + (m-2)!b(n-1) + \cdots b^{m-2}(n-1)\cdots(n-m+2))}{(m-1)!\ b^{m-1}}$

by creating a common denominator and factoring. From this, we are able to deduce that $n=(m-1)!(a-1)^{m-1}$ is a satisfactory value.

Question

Minimality

The value above is not minimal from some simple checks with small values of $a,m$, but I am unable to make much headway into finding an analytical solution.The graph of $a=3$ below lends me to believe it may not be as complicated as I think however.

Graph of minimal n vs m for a = 3

The numbers get unwieldy quickly, so I'm not able to do much further numerical work unfortunately. Any ideas?

$\endgroup$
3
  • $\begingroup$ After seeing Max's nice solution, here is a 'shortcut' to obtain the upper bound $n=(a-1)^{m-1}$. As shown in Bryan's post, a sufficient condition for a given $n$ to work is that $\binom{n}{i} b^{i-m}$ will be an integer for any $1 \le i \le m-1$, where $b:=a-1$. As $\binom{n}{i} = \frac{n}{i} \binom{n-1}{i-1}$, $n$ will work if $\frac{n}{i} b^{i-m}$ will not have $p$ in the denominator, for any $p \mid b$. $\endgroup$ Jan 25, 2018 at 13:41
  • $\begingroup$ (cont.) If $n=b^{m-1}$ we have $v_p( \frac{n}{i} b^{i-m} ) = (m-1) v_p(b) -v_p(i) + v_p(b) (i-m) = v_p(b) (i-1) - v_p(i) \ge i-1 -v_p(i)$, which is non-negative since $v_p(i) \le \lfloor \log_p (i) \rfloor$ in general. To prove a lower bound one probably has to use lemmas of the sort used by Max. $\endgroup$ Jan 25, 2018 at 13:41
  • 1
    $\begingroup$ upper bound $(a-1)^{m-1}$ is proved by induction: if $(a-1)^m$ divides $a^k-1$, then $(a-1)^{m+1}$ divides $a^{k(a-1)}-1=(a^k-1)(1+a^k+a^{2k}+\dots +a^{k(a-2)})$ $\endgroup$ Jan 25, 2018 at 14:54

1 Answer 1

7
$\begingroup$

Lifting The Exponent Lemma is helpful here.

First notice that $(a-1)^m\mid a^n-1$ is equivalent to $\nu_p(a^n-1)\geq m\nu_p(a-1)$ for every prime $p\mid a-1$.

If $a$ is even, then by LTE for any prime $p\mid a-1$, we have $$\nu_p(a^n-1)=\nu_p(a-1)+\nu_p(n).$$ Hence, for each such $p$, we need $\nu_p(a-1)+\nu_p(n)\geq m\nu_p(a-1)$, i.e. $\nu_p(n)\geq (m-1)\nu_p(a-1)$. The minimum $n$ that satisfies these inequalities is $n = (a-1)^{m-1}$.

If $a$ is odd, things are more complicated because of presence of $p=2$. Still, if $a\equiv 1\pmod{4}$, everything is as above.

It remains to consider the case of $a\equiv 3\pmod{4}$. If $m\geq 2$, then $n$ is even (as pointed out by Fedor Petrov), and LTE gives $$\nu_2(a^n-1)=\nu_2(a-1)+\nu_2(a+1)+\nu_2(n)-1,$$ implying that $$\nu_2(n) \ge (m-1)\nu_2(a-1) - \nu_2(a+1) + 1.$$ The minimum (even) $n$ in this case equals $\frac{(a-1)^{m-1}}{2^k}$, where $k=\min\{\nu_2(a+1)-1,m-2\}$. (corrected per Fedor Petrov's comment)

$\endgroup$
4
  • 1
    $\begingroup$ If $a$ is odd and $(a-1)^2$ divides $a^n-1=(a-1)(1+a+\dots+a^{n-1})$, then $n$ is of course even and moreover divisible by $a-1$. And why do you care on $a^{2n}-1$ at all? $\endgroup$ Jan 25, 2018 at 14:20
  • $\begingroup$ @FedorPetrov: Indeed, this was my oversight. $2n$ was considered to enable the application of LTE. $\endgroup$ Jan 25, 2018 at 14:25
  • 2
    $\begingroup$ Your final expression still may be non integral, it should be $(a-1)^{m-1}2^{\max(2-m,-k)}$. $\endgroup$ Jan 25, 2018 at 14:45
  • $\begingroup$ @FedorPetrov: Yes, I forgot to enforce $n$ be even. Thanks! $\endgroup$ Jan 25, 2018 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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