# A generalisation of ‘lifting the exponent’

Lifting the exponent is a popular result in elementary number theory. It basically says that if $\alpha,\beta\in\mathbb Z$ and $a_n=(\alpha^n-\beta^n)/(\alpha-\beta)$, then for an odd prime $p$ coprime to $\alpha,\beta$ and for $r\ge 1$,

Theorem 1. (Lifting the exponent) $p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0$.

Here, as usual, $p^r\parallel x$ means that $p^r\mid x$ but $p^{r+1}\nmid x$.

We shall generalise this to general rings of algebraic integers. In the following, $K$ will denote an algebraic number field and $\mathcal O_K$ its ring of integers. Let $\alpha,\beta\in\mathcal O_K$ such that the ideals $(\alpha), (\beta)$ are coprime to $(p)$, and $a_n\in\mathbb Z\ \forall n$.

Theorem 2. $p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0$.

Proof. We proceed by induction on $n$. The base case $n=0$ is clear. Suppose that the assertion holds for $n-1$. We want to show that $p^{n+r}\parallel a_{kp^n}$, that is,

$\displaystyle p^{n+r}\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha-\beta}=a_{kp^{n-1}}\cdot\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}$

By hypothesis, $p^{n+r-1}\parallel a_{kp^{n-1}}$. So we need to show that $\displaystyle p\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}$.

Let $c=\alpha^{kp^{n-1}}, d=\beta^{kp^{n-1}}$. We want to show that $\displaystyle p\parallel\frac{c^p-d^p}{c-d}$.

Since $p\mid a_k$, we have $a_k\in (p)$. Hence $\alpha^k-\beta^k=(\alpha-\beta)a_k\in (p)$, i.e. $\alpha^k\equiv\beta^k\pmod p$. Hence $c\equiv d\pmod p$. Let $c=d+\mu p$ for some $\mu\in\mathcal O_K$. Then

$\displaystyle\frac{c^p-d^p}{c-d}=\frac{(d+\mu p)^p-d^p}{\mu p}=\frac{p\cdot d^{p-1}\mu p+\ldots}{\mu p}\equiv pd^{p-1}\pmod{p^2}.$

If this is $0$, then $(p)\mid (d)^{p-1}$, which is impossible by unique factorisation as $(p)$ and $(d)$ are coprime. $\square$

Corollary. Let $\{F_n\}$ be the Fibonacci sequence. Then

$p^r\parallel F_{k(p)}\Rightarrow k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}$

(Refer to this post for notation.)

Proof. Take $\alpha=\varphi=\frac{1+\sqrt 5}{2}, \beta=\bar\varphi=\frac{1-\sqrt 5}{2}$ (with $K=\mathbb Q(\sqrt 5)$ and $\mathcal O_K=\mathbb Z[\varphi]$) and let $k=k(p)$. We proceed by induction on $n$. Suppose $p^{n+r}\mid F_j$ for some $j. By hypothesis, $k(p^{n+r-1})=kp^{n-1}$ so $p^{n+r-1}\mid p^{n+r}\mid F_j\Rightarrow kp^{n-1}\mid j. Then $1\le \frac{j}{kp^{n-1}}, so $\gcd(\frac{j}{kp^{n-1}},p)=1$, i.e. $\gcd(j,kp^n)=kp^{n-1}$. Hence $\gcd(F_{kp^n},F_j)=F_{kp^{n-1}}$ which implies $p^{n+r}\mid F_{kp^{n-1}}$, a contradiction. $\square$