Odd prime power congruent to 1 modulo large powers of 2 Let $p$ be an odd prime, $n$ an integer. What can we say about the largest integer $k$ such that $p^n \equiv 1 \mod 2^k$? Equivalently, the largest $k$ such that $2^k \mid (p^n - 1)$.
I remember reading somewhere that this should be bounded in terms of the largest integer $k$ such that $2^k \mid n$ but cannot find the precise statement or the proof anymore.
 A: As Gerry Myerson points out in a comment, this has nothing to do with $p$ being prime, but everything to do with $p$ being odd (which makes it a $2$-adic unit). So let's call it $u$ instead, and you're asking for $v_2(u^n-1)$ for an odd number $u$. Now the neat thing is that $u^n-1=u^n-1^n$ which makes this a special case ($x=u, y=1$) of the "LTE" (Lifting The Exponent) Lemma, cf. here or here, and What can I do with the lifting the exponent lemma?. The result in general is a very easy formula in $v_2(u-1)$ and $v_2(n)$, however in the case $v_2(u-1)=1$ and $n$ even it suddenly turns into a formula in $v_2(u\color{red}{+}1)$ and $v_2(n)$. Find it for yourself or look at the spoiler below:

 If $v_2(u-1)=1$ and n is even, $$v_2(u^n-1)=v_2(u+1)+v_2(n).$$


 In all other cases (i.e. $v_2(u-1) \ge 2$ and/or $n$ is odd), $$v_2(u^n-1)=v_2(u-1) +v_2(n).$$

If you want to phrase that not in tedious binomial calculations, but in a cool theory, where one can also see why a) the LTE Lemma is a bit different for the prime $2$ than for other primes, and b) why the case $v_2(u-1)=1$ is different from $v_2(u-1)\ge 2$: Remember that the $2$-adic units $\mathbb Z_2^\times$ have, on the one hand, a natural filtration
$\mathbb Z_2^\times =U^{(1)} \supsetneq U^{(2)} \supsetneq ...$
with $U^{(i)} := \{u \in \mathbb Z_2^\times: v_2(u-1) \ge i\}$;
on the other hand, actually we have
$\mathbb Z_2^\times = \{\pm 1\} \times U^{(2)} \stackrel{2-\text{adic log}}\simeq \{\pm 1\} \times (4\mathbb Z_2, +)$
and the logarithm respects the filtration, i.e. maps $U^{(i)}$ onto $2^i \mathbb Z_p$ for all $i\ge 2$.
(And this is a bit different for primes other than $2$, where already the first principal units $U^{(1)}$ are isomorphic to the additive group $p\mathbb Z_p$).
Now we see why the case $u \in U^{(2)}$ i.e. $v_2(u-1) \ge 2$ i.e. $4 \mid (u-1)$ is so easy:
$\begin{align}
v_2(u^n-1) &= v_2(log(u^n)) \\
&= v_2(n\cdot log(u)) \\
&= v_2(n) + v_2(log(u)) \\
&= v_2(n) +v_2(u-1) \end{align}$
where the first and last equality are due to the fact that the logarithm respects the filtrations. And so I know that $2^{4+v_2(4)} = 64$ is the highest power of $2$ which divides $17^4-1= (1+2^4)^4-1$, without doing any computations. But the same is true if instead of $u=17$ I take $u=145$, $v_2(145^4-1) = 6$, regardless of $145$ not being prime: it only matters in which filtration step $U^{(i)} \setminus U^{(i+1)}$ it sits, here $i=4$.
Finally, how does this $2$-adic view explain what happens in case $v_2(u-1)=1$? Well, $$u \in U^{(1)} \setminus U^{(2)} \Leftrightarrow -u \in U^{(2)}$$
and hence for even $n$ (where $(-1)^n=1$) we get
$$v_2(u^n-1)= v_2((-u)^n-1) = v_2(-u-1)+v_2(n) = v_2(u+1)+v_2(n)$$
where the second equality just applies the other case, and the third one is due to $v_2(-1)=0$;  whereas for odd $n$, we just see that
$$u \in U^{(1)} \setminus U^{(2)} \implies u= -u_2 \text{ for } u_2 \in U^{(2)} \implies u^n = - (u_2)^n \in (-1) \times U^{(2)} = U^{(1)} \setminus U^{(2)}$$
i.e. $$v_2(u^n-1) = v_2(u-1) +\underbrace{0}_{v_2(n)} =1.$$
