Timeline for Minimal $n$ such that $(a-1)^m | a^n - 1$ for a given $a,m > 1$

9 events

when toggle format	what		by	license	comment
Jan 25, 2018 at 15:12	vote	accept	Bryan Bush
Jan 25, 2018 at 14:54	comment	added	Fedor Petrov		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)})$
Jan 25, 2018 at 13:41	comment	added	Ofir Gorodetsky		(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.
Jan 25, 2018 at 13:41	comment	added	Ofir Gorodetsky		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$.
Jan 25, 2018 at 13:19	answer	added	Max Alekseyev		timeline score: 7
Jan 25, 2018 at 7:42	history	edited	Martin Sleziak		added (divisors-multiples) tag
Jan 25, 2018 at 7:39	history	edited	Bryan Bush	CC BY-SA 3.0	Title change to keep notation consistent with question.
Jan 25, 2018 at 7:33	review	First posts
Jan 25, 2018 at 8:26
Jan 25, 2018 at 7:32	history	asked	Bryan Bush	CC BY-SA 3.0