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$
  • $\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$ – Ofir Gorodetsky Jan 25 '18 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$ – Ofir Gorodetsky Jan 25 '18 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$ – Fedor Petrov Jan 25 '18 at 14:54
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$
  • 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$ – Fedor Petrov Jan 25 '18 at 14:20
  • $\begingroup$ @FedorPetrov: Indeed, this was my oversight. $2n$ was considered to enable the application of LTE. $\endgroup$ – Max Alekseyev Jan 25 '18 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$ – Fedor Petrov Jan 25 '18 at 14:45
  • $\begingroup$ @FedorPetrov: Yes, I forgot to enforce $n$ be even. Thanks! $\endgroup$ – Max Alekseyev Jan 25 '18 at 15:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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