If we have a number of the form $3^{n}-1$, how can we know in general what is the greatest power of $2$ that can divide it if we only know the value of $n$ without having to find the value of $3^{n}-1$?
Asked
Active
Viewed 106 times
1
-
2Welcome to Mathematics Stack Exchange. Surround mathematical expressions with $s. It depends if $n$ is odd or even – J. W. Tanner Jun 09 '20 at 13:53
-
1For $n$ odd the greatest power is $2^1$. For a general answer see this MO-post. On this site it has been shown at this duplicate, take $b=1$. – Dietrich Burde Jun 09 '20 at 13:55
-
If $n$ is odd, then $3^n-1=2(3^{n-1}+3^{n-2}+\cdots+3^2+3+1)$ with the quantity in parentheses being odd – J. W. Tanner Jun 09 '20 at 13:57
-
2See OEIS sequence A090740. – Robert Israel Jun 09 '20 at 14:13
-
If $n = 2^e m$ with $m$ odd and $e \ge 1$, the greatest power is $2^{e+2}$. – Robert Israel Jun 09 '20 at 14:16
-
1$3^{n-1}\ne3^n-1$. – Angina Seng Jun 09 '20 at 14:23
-
See also here – Bill Dubuque May 04 '22 at 14:19
1 Answers
1
You can usually use the LTE Lemma for such problems.
Using the notation used by the provided document you get by Theorem 4 (even $n$):
$$v_2(3^n-1^n)=v_2(3-1)+v_2(3+1)+v_2(n)-1=v_2(n)+2$$
So you have to know what is the largest $\alpha$ so that $2^\alpha | n$ (also written as $2^\alpha || n$), hence the largest power of $2$ that divides $3^n-1$ is $\alpha+2$.
For odd $n$ we can use the last equation in the summary, since $\gcd(2,n)=1$:
$$v_2(3^n-1)=v_2(3^n+(-1)^n)=v_2(3+(-1))=v_2(2)=1$$ Hence if $2\nmid n$, $2^1$ is the largest power to divide $3^n-1$. To prove this, you can also look the the factorisation of the expansion and counting how many of powers of $3$ you have (which is odd).
Proofs are also provided in the document.
CryoDrakon
- 3,392
-
-
Sorry, never learned spanish... Maybe you can use Google Translate or DeepL – CryoDrakon Jun 09 '20 at 14:41
-
-
-
I have extended the answer for odd n. It is some time since I used LTE, hence I forgot it is only for even n. – CryoDrakon Jun 09 '20 at 15:26