1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Jun 8 '15 at 20:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 8 '15 at 20:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 8 '15 at 20:37
  • 1
    $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Jun 8 '15 at 20:53
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Jun 8 '15 at 21:17
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ – Carlos Toscano-Ochoa Jun 8 '15 at 20:55
  • $\begingroup$ 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$. $\endgroup$ – Carlos Toscano-Ochoa Jun 8 '15 at 21:00
  • $\begingroup$ 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. $\endgroup$ – Carlos Toscano-Ochoa Jun 8 '15 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.