# Tools for dealing with a divisibility problem with powers of 2 and 3?

I'm trying to solve an equation with congruences:

$$\sum_{i=1}^{N}2^{\sum_{j=1}^{i} n_j}3^{N-i} \equiv 0 \; (\text{mod} \; 2^{\sum_{j=1}^{N}}-3^N)$$

The unpacked version (assuming $\sum_{j=1}^{N}n_j= \hat{N}$):

$$2^{n_1} 3^{N-1}+2^{n_1+n_2}3^{N-2} + 2^{n_1+n_2+n_3}3^{N-3}+ \; ...+2^{\hat{N}-n_N}3+2^{\hat{N}} \equiv 0 \; (\text{mod} \; 2^{\hat{N}}-3^N)$$

The only thing that you have to know is that the $n_j$ are natural numbers (1, 2, 3...) and that it doesn't matter how, you are always going to have at least one $n_j=1$. Other interesting fact is that if you ignore the last thing I've said, is that if you set all $n_j = 2 \; \; \forall j$ then I think it is always divisible no matter how big is N.

And now, I have no idea about how to continue from this point. How should I continue?? Any hint or clue??

Thanks!!!

• Just trying to unpack this further with an example of $N=3$, $n_1=1$, $n_2=2$, $n_3=3$, so $\hat N=6$. We have $2^{\hat N}-3^N=64-27=37$. But the sum is $$2^1\cdot3^2+2^3\cdot 3^1+2^6=18+24+64=106.$$ This is $\not\equiv 0\pmod{37}$. Did I misunderstand something? – Jyrki Lahtonen Jun 8 '15 at 20:20
• Ok. So the $n_i$:s are the variables, and the (hoped for) claim is that there are no solutions to the congruence such that at least one of the $n_i$:s is equal to one. – Jyrki Lahtonen Jun 8 '15 at 20:30
• Unless I made a mistake the case with $n_j=2$ for all $j$, is always a solution. Confirming your conjecture. Then the sum is geometric making it easier to handle. – Jyrki Lahtonen Jun 8 '15 at 20:37
• Now I'm thinking that the calculation in the answer shows that if all $n_j$ are equal, we always have a solution. They don't need to be equal to two. Is that bad news? – Jyrki Lahtonen Jun 8 '15 at 20:53
• That extra was premature, sorry. We do get a geometric sum whenever all the $n_j$ are equal, but we do not get a solution to the congruence unless they are all equal to $1$ or $2$. That extra $2^n-3$ is a non-trivial factor, when $n>2$. – Jyrki Lahtonen Jun 8 '15 at 21:17

## 1 Answer

Settling the simple case of $n_j=2, j=1,2,\ldots,N$, $\hat N=2N$, to get it out of the way.

The sum on the l.h.s. is then $$S=4\cdot3^N+4^2\cdot3^{N-1}+\cdots+4^N.$$ This is a geometric sum as the next term is always gotten from the previous one by multiplying it with $4/3$. Therefore \begin{aligned} S&=4\cdot3^N\cdot\frac{1-(4/3)^N}{1-4/3}=4\cdot3^{N+1}\left[(4/3)^N-1\right]\\ &=4^{N+1}\cdot3-4\cdot3^{N+1}. \end{aligned} Let $M=4^N-3^N$ be our modulus. We have $$S=4^{N+1}\cdot3-4\cdot3^{N+1}=12\cdot4^N-12\cdot 3^N=12M\equiv0\pmod M.$$

We get a geometric sum whenever all the $n_j$ are equal. Call that common value $n$. Now $\hat N=nN$, and the modulus is $M=2^{nN}-3^N$. The sum is $$S=2^n\cdot3^N+\cdots+2^{nN}=\frac{2^{n(N+1)}-2^n3^{N+1}}{2^n-3}=\frac{2^n\cdot3M}{2^n-3}.$$ It is tempting to conclude that this is divisible by $M$, but that is premature (and actually false). Clearly $2^n-3$ is a factor of $M$. Unlike in the case $n=2$ this factor is $>1$. It is not a factor of $3\cdot2^n$ either, so in this case we do NOT have a solution.

• AMAZING. So... always you set all $n_j=k$, being k any natural number, you can deal with the sum. The divisibility problem is other thing in each case, but at least is a fantastic starting point. Thanks, Jyrki! – Carlos Toscano-Ochoa Jun 8 '15 at 20:55
• An important constrain is that the denominator must be positive, so $2^{\hat{N}}>3^{N}$. This avoids setting all $n_j=1$, but you are right, it could be interesting to set all $n_j \geq 3$. – Carlos Toscano-Ochoa Jun 8 '15 at 21:00
• Wonderful answer. I suspect that the only case in which you obtain divisibility is when all $n_j = 2$, but this is something I have to work in. Thank you so much. If you'd have anything else to comment, feel free. – Carlos Toscano-Ochoa Jun 8 '15 at 21:55