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<kp^n. 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<kp^n. Then 1\le \frac{j}{kp^{n-1}}<p, 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



Filed under Algebra, Number theory

2 responses to “A generalisation of ‘lifting the exponent’

  1. Pingback: Some divisibility properties of Fibonacci-like sequences | Samin Riasat's Blog

  2. Pingback: Catalan-type diophantine equations | Samin Riasat's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s