This open-ended question was originally posted on Twitter [here](https://twitter.com/AllenWebster4th/status/956352049121234950). 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](https://i.stack.imgur.com/VjS9q.jpg)


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



Minimal $n$ such that $(a-1)^m | a^n - 1$ for a given $a,m > 1$
[Lifting The Exponent Lemma](http://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYy82LzM3NWU4YzY0YWNhMDhhODExMWFlZDY1YzIwOTkwZmQ5NDIwNTcw&rn=TGlmdGluZyBUaGUgRXhwb25lbnQgLSBWZXJzaW9uIDYucGRm) 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)


