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?

Improve this question
$\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$
    – Ofir Gorodetsky
    Commented 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$
    – Ofir Gorodetsky
    Commented 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$
    – Fedor Petrov
    Commented Jan 25, 2018 at 14:54

1 Answer 1

Reset to default
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)

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .