Given the number $N=3^{12}-1$. Find how many even and odd divisors of $N$ exist, which divide $N$ but don't divide $3^k-1$, for $1\le k\le 11$

Question

Given the number $N=3^{12}-1$. Find how many even and odd divisors of $N$ exist, which divide $N$ but don't divide $3^k-1$, for $1\le k\le 11$

Initially I tried working out how many odds and evens divide $N$, without the extra restriction.

$3^{12}-1=(3-1)(3^2+3+1)(3+1)(3^2-3+1)(3^6+1)=2*13*4*7*730$

$=2^4*5*7*13*73$

Hence there are $16$ odd divisors and $64$ even divisors.

I don't know how to finish off the question with the extra condition, without exmining all $80$ possibilities individually. Could you please explain to me how to solve this question?

Also a solution to the question is the following, despite the fact that I have tried to understand it, but it is too complex for me:

If we have an integer $m$, $3^{12}\equiv 1\mod{m}$, then the smallest integer for which $d<12$ for which it holds true that $3^d\equiv 1\mod{m}$, must divide $12$, since if this is not true, then we can write $12=dp+r$, with $0<r<d$ and then we have $3^r\equiv 1\mod{m}$, which is not true, from the hypothesis that $d$ is the smallest number for which $3^d\equiv 1\mod{m}$.

Hence to be sure that $m$ does not divide $3^k-1$, for $1\le k\le 11$, we examine all values of $k$ which divide $12$, in other words $k=1,2,3,4,6, 3^1-1=2, 3^2-1=2^3,3^3-1=2*13, 3^4-1=2^4*5 and 3^6-1=2^3*7*13$.

Odd divisors of $N$ divide $N$ but do not divide $3^k-1$, for $1\le k \le 11$ is: $16-5=11$.

Even divisors of $N$ which divide $N$, but do not divide $3^k-1$ for $1\le k\le 11$, are: $64-17=47$

Answer 1

I think the "too-complicated" solution you cite would be more understandable if it were phrased constructively, for example:

For a given integer $m$ with $3\nmid m$, there is a smallest $k>0$ for which $3^{k}\equiv 1\bmod{m}$ - the multiplicative order of $3 \bmod m$. Then for any $j>0$, $3^j\equiv 1 \bmod m$ $\iff$ $k\mid j$. Thus any number $m$ which divides $3^{12}{-}1$ can only divide a smaller $3^i{-}1$ if $i\mid 12$.

Now we can assign factors of $3^k-1$ as being "primary" if they do not belong to a lower $k$ - we find these simply by subtracting off the primary factors of lower dividing powers. Then considering $k=1,2,3,4,6,12$:
$$\begin{array}{c} \hline k & 3^k-1 & \text{# factors}& \text{dividing } k & \text{# primary}& \\ & & \text{ odd + even} & & \text{ odd + even} \\ \hline 1 & 2 & 1+ 1& - & 1+ 1 \\ 2 & 2^3 & 1+ 3 & 1 & 0+ 2 \\ 3 & 2\cdot 13 & 2+ 2 & 1 & 1+ 1 \\ 4 & 2^4\cdot 5 & 2+ 8 & 1,2 & 1+ 5 \\ 6 & 2^3\cdot 7\cdot 13 & \;4+12 & 1,2,3 & 2+ 8 \\ 12 &\quad 2^4\cdot 5\cdot 7\cdot 13\cdot 73 & 16+ 64 & 1,2,3,4,6 & 11+ 47 \\ \end{array} $$

Answer 2

Let $d$ be a divisor of $3^{12}-1$. Note $d\neq3$. Call $d$ "bad" if $d$ divides some $3^k-1$ for $k\in\{1,2,\ldots,11\}$.

If $d$ divides $3^k-1$, then mod $d$: $3^k\equiv1\implies3^{12}\equiv3^{12-k}\implies1\equiv3^{12-k}$. So if $d$ is bad, then $d$ divides some $3^k-1$ for $k\in\{1,2,\ldots,6\}$.

If $d$ divides $3^k-1$, then mod $d$: $3^k\equiv1\implies3^{2k}\equiv1$. So if $d$ is bad, then $d$ divides some $3^k-1$ for $k\in\{4,6\}$.

So you only need examine divisors of $3^4-1=2^4(5)$ and $3^6-1=2^3(7)(13)$. From the odd divisors of $3^{12}-1$, exclude the subtree of $5$ (that is, $\{5,1\}$). And exclude the subtree of $(7)(13)$ (that is, $\{91,13,7,1\}$). That is five things to exclude, and leaves $16-5=11$ such odd divisors.

From the even divisors of $3^{12}-1$, exclude the supertree of $2$ within the divisor tree for $3^4-1$ (that is, $\{2^{\{1,2,3,4\}}5^{\{0,1\}}\}$). And exclude the supertree of $2$ within the divisor tree for $3^6-1$ (that is, $\{2^{\{1,2,3\}}7^{\{0,1\}}13^{\{0,1\}}\}$). That is 17 things to exclude, and leaves $64-17=47$ such even divisors.