If $3^2$ divides $2^n-1$, then $n$ must be divisible by $6$

Question

I was riffling through some old posts (see the link at the bottom of this post) in which it was given as a fact that if $3^2$ divides $2^n-1$, then $n$ is divisible by $6$.

It was given in the post as a quick fact, so I wonder if there is an easy argument for this, or if my group theory argument below is probably the best way to go. The result isn't obvious to me anyway, but I might be rusty.

My own thoughts so far: Since $\varphi(3^2)=|\{1,2,4,5,7,8\}|=6$ (the Euler totient function), it follows from Euler-Fermat that

$$2^6\equiv 1\pmod{3^2}.$$

The order of (the residue class of) $2$ must divide the order of the multiplicative group $\left(\mathbb{Z}/(3^2\mathbb{Z})\right)^{\times}$, which is $6$ by the above, so at least we know that if $2^n\equiv 1\pmod{3^2}$, then $n\in\{1,2,3,6,12,18,\ldots\}$, and I have checked by hand that $n\not\in\{1,2,3\}$.

This proves it, but I'm unsure if I'm missing something. Surely there must be groups $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ in which $2$ has an order strictly smaller than $\varphi(n)$.

This is the post I was looking at, and the answer I was reading is Gottfried Helms' - the one that starts with "A modular view".

Answer 1

This can be readily explained without orders or multiplicative groups, just modular arithmetic. There is a much more obvious reason for this. First of all, knowing nothing else, there are only nine possibilities for $2^n \pmod 9$. As it turns out, three values are impossible:

• $3$ because that would mean $2^n$ is a multiple of $3$
• $6$ and $0$ for the same reason

Only six possibilities remain, and if they all occur, they must occur in a regularly repeating pattern.

The powers of $2$ modulo $9$ are $$2, 4, 8, 7, 5, 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, \ldots$$ When you subtract $1$ from each of these, you get a pattern that also repeats: $$1, 3, 7, 6, 4, 0, 1, 3, 7, 6, 4, 0, 1, 3, 7, \ldots$$

Answer 2

Hint : You can reduce $n$ modulo $\phi(9)=6$, if you want to calculate $2^n$ modulo $9$.

Answer 3

Firstly, $2^{n+6}-1=64\cdot 2^n-1=63\cdot2^n +2^n-1$, and $9|2^0-1$ and no other $1\le n\le5$.

Secondly, $2^k \mod 9$ only takes values $k$ where $(k,9)=1$, and so is period $\phi(9)=6$.

Answer 4

Another way:

1) $3 \mid 2^s -1$ iff $s$ is even. (This is the fact we will use).

2) $2^{2m}-1=(2^2-1)(1+2^2+2^4+\cdots+2^{2m-2})$.

3) $1+2^2+2^4+\cdots+2^{2m-2} \equiv 1+1+1+\cdots+1 \equiv m \mod 3$.

Hence $2^k-1 \equiv 0 \mod 9$ iff $k \equiv 0 \mod 6$.