Remainder when $2^{55}+1$ is divided by $33$

Question

There's this problem I encountered in a math Olympiad for my country.

Find the remainder when $2^{55}+1$ is divided by $33$.

My approach was to consider $2^{55}$ as the sum of numbers in the 56th row of Pascal's triangle. Then I showed that apart from 1 and 55, all other numbers have at least one factor of 11 and 3 to spare, so one would consider only 1 and 55 for the answer. Doing this leads to $113 \mod 33=14$. But the choices for that question were between 0 and 5.

Is my reasoning wrong? Or am I missing something?

Answer 1

Using binomial theorem

$$2^{55}= 32^{11} = (33-1)^{11} = $$$${11\choose 0}33^{11}-{11\choose 1}33^{10}+...+{11\choose 10}33-1=$$

$$ =33\underbrace{(\dots )}_{\in\mathbb{Z}}-1$$

So the remainder is $0$.

Answer 2

I think you will find for example that ${55 \choose 11}$ and ${55 \choose 22}$ are not multiples of $33$. Instead

• $2^5=32\equiv -1 \pmod {33}$
• $2^{55} = (2^5)^{11}\equiv (-1)^{11} \equiv -1 \pmod {33}$
• $2^{55}+1 \equiv 0 \pmod {33}$

Answer 3

${55\choose 11k + i;0\le i <11}= \frac {(55-11k-i+1)....(55-11k).....(55-11(k-1))....(55-11)...55}{1*2*....*11*....*22*...*11k*...(11k+i)}$... $11^{k+1}$ divides the numerator unless $i=0$ in which case $11^{k}$ divides the numerator. $11^k$ divides then denominator, so $11|{55\choose n}$ unless $n$ is a multiple of $11$.

So $2^{55}=\sum {55\choose k} = \sum {55\choose 11k} = 2(1+\frac {55\choose 11} + \frac {55\choose 11})\equiv 10\pmod 11$. (Let's just say, thank goodness for calculators.)

So ${55\choose 11} = \frac {45*....*55}{1*....*11} = \frac{45*....*54*5}{10!}$ is not divisible by $11$ nor is ${55\choose 22} = \frac {35*....*43*4*45*.....*54*5}{10!*12*....*21}$ nor is ${55\choose 33}={55\choose 22}$ and nor is ${55\choose 11}$.

I thought you were correct about the $3$s though.

I thought we could say that $2^{55} \equiv 2(1+55+ {55 \choose 11}+{55\choose 22})\pmod {33}$ but I don't want to calculate that. My calculater says... ${55\choose 11} = 119653565850\equiv 27\pmod {33}$ and an ${55\choose 22} = 1300853625660225\equiv 21\pmod {33}$ (weird... I got a rounding error) so $2(1+55+27+21) \equiv 10\pmod 33$ but $2^{55}\equiv 2^{15}\equiv 32\pmod {33}$ (but $2^{55}\equiv 10\pmod {11}$. so no.... I guess not. Not sure why not. I guess there must be some ${55 \choose k}; 1 < k < 54$ that is not divisible by $3$.

Actually ${55\choose 27}\equiv \frac{28*.....*55}{27!}$ will have a high power of $3$ in the denominator not in the numerator. And.... thank goodness for calculators. $3$ does not divide ${55\choose 28}$ and indeed $2(1+55 + 21+27 + {55\choose 28})\equiv 2(1+55+21+27+11)\equiv 32\pmod {33}$ which seems to be the correct ansswer.

Answer 4

We have

$\tag 1 (1 + 1)^{55} = \sum_{k = 0}^{55} \binom{55}{k} = 2 \times \sum_{k = 0}^{27} \binom{55}{k} $

and

$\quad \binom{55}{2} \equiv 5 \times 3^3 \times 11 \equiv 0 \pmod{33}$

What we have to be concerned about is that while 'moving along' the Pascal half-row we might 'lose' the factor of $33$ in a binomial coefficient. This is a matter of accounting.

Whenever you have three consecutive integers $3$ divides at most one of them and you can inspect the integer for multiplicity. Considering the factors of the demoninator (there are corresponding factors in the numerator where you are gaining factors of $3$),

$\quad 3,4,5 \quad 6,7,8 \quad 9,10,11 \quad 12,13,14 \quad 15,16,17 \quad 18,19,20 \quad 21,22,21 \quad 24,25,26 \quad 27$

you know that you have to calculate $\binom{55}{27} \pmod{33}$ ($27 = 3^3$ is 'killing off' the $33$ factor),

$\quad \binom{55}{27} \equiv 11 \pmod{33}$

Similarly, you get a 'new' $11$ right after you 'lose it' with $44$ (and again with $33$) in the numerator, so you calculate $\binom{55}{11} \pmod{33}$ and $\binom{55}{22} \pmod{33}$,

$\quad \binom{55}{11} \equiv 27 \pmod{33}$
$\quad \binom{55}{22} \equiv 21 \pmod{33}$

So plugging into $\text{(1)}$,

$\tag 2 (1 + 1)^{55} \equiv 2 \times (1 + 55 + 27 + 21 + 11) \equiv 2 \times 16 \equiv 32 \pmod{33}$

So adding $1$ we can write the answer,

$\tag {ANS} 2^{55}+1 \equiv 0 \pmod{33}$

Answer 5

Sticking to Pascal's triangle, you can just start calculating $2^k \pmod{33}$ row by row until you see a 'pattern' and can then get lazy.

$\quad 2^0 \equiv \;\,1 \pmod{33}$
$\quad 2^1 \equiv \;\,2 \pmod{33}$
$\quad 2^2 \equiv \;\,4 \pmod{33}$
$\quad 2^3 \equiv \;\,8 \pmod{33}$
$\quad 2^4 \equiv 16 \pmod{33}$
$\quad 2^5 \equiv 32 \pmod{33}$
$\quad 2^6 \equiv 31 \pmod{33}$
$\quad 2^7 \equiv 29 \pmod{33}$
$\quad 2^8 \equiv 25 \pmod{33}$
$\quad 2^9 \equiv 17 \pmod{33}$

and then repeats since

$\quad 2^{10} \equiv \;\,1 \pmod{33}$

So the pattern repeats after a cycle of length $10$.

We want to get to the $56^{th}$ row ($0 \le k \le 55$), and since $56 = 5 \times 10 + 6$, we use the $6^{th}$ entry of the cycle, $2^5 \equiv 32 \pmod{33}$, so that also

$\tag 1 2^{55} \equiv 32 \pmod{33}$

and adding $1$ we can write the answer,

$\tag {ANS} 2^{55}+1 \equiv 0 \pmod{33}$

Answer 6

Note that $2^5 \equiv -1 \pmod{33}$. So $(2^5)^{11} \equiv (-1)^{11} \pmod{33}$, that is equivalent to $2^{55} \equiv -1 \pmod{33}$.

Hence, $2^{55}+1$ is divided by $33$.