2

I would like to find the greatest k such that $p=\frac{3^n - 1}{2}$ is divisible by $2^k$.

Since $p$ is the repunit number in base 3 it is already clear that if $n$ is even, $p$ would be divisible by 4 (since we could write $p/2 = 2020...202$ in base 3).

Thus, $p/4 = 1010...101$ which is divisible by 8 only if there is an even number of $1$ wich is equivalent to $n$ being divisible by 4.

Starting from here the pattern gets longer and longer, and I'm not able to generalize for any given $k$. Would someone have an idea?

kronenbouh
  • 65

1 Answers1

4

If $n=2^m q$ where $q$ is odd, let $\nu_2(n)=m$. The answer to the question is $$\nu_2\left(\frac{3^k-1}{2}\right) = \nu_2(k)+\frac{1+(-1)^k}{2}$$. To prove this, first prove that $$\nu_2\left(\frac{3^k+1}{2}\right) =\begin{cases} 1 & \mbox{ if $k$ is odd}\\ 0 & \mbox{ if $k$ is even}\end{cases}.$$ Then use the identity $$3^{2^m q}-1 = \left(3^{q2^{m-1}}-1\right)\left(3^{q2^{m-1}}+1\right)$$ and induction on $m$.

Valerio
  • 370
  • 1
  • 6
  • This is quite a surprising answer! – Vincent May 04 '22 at 10:03
  • 1
    @Vincent Actually it is common to find formulas for the 2-adic valuations of a sequence $a(k)$ in terms of the 2-adic valuation of $k$. You may want to look at the work of Victor Moll and his collaborators on the topic, see for example this video: https://www.youtube.com/watch?v=DPLOsfL8sCo – Valerio May 04 '22 at 10:11
  • Thank you ! How would you prove that $$\nu_2\left(\frac{3^k+1}{2}\right) =\begin{cases} 1 & \mbox{ if $k$ is odd}\ 0 & \mbox{ if $k$ is even}\end{cases}.$$ I studied the congruence modulo 8 of $3^k + 1$ to do so but would there be a more elegant way? – kronenbouh May 04 '22 at 10:43
  • look at the numerator modulo 8 – razivo May 04 '22 at 13:30