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$ 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$

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.
