Remainder when $2^{55}+1$ is divided by $33$ 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?
 A: 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$.
A: 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}$
A: 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$.
A: 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}$
A: 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}$
