elementary-number-theory - elementary set theory - Determine the number of subset mod 13 - answerstu - answerstu.com answerstu

# elementary set theory - Determine the number of subset mod 13

Let $x$ be the number of subsets of the set $A=\{1, 2, 3, ..., 28\}$ (including an empty set and the whole set $A$) such that there aren't such two numbers that their sum is divisible by 29. Determine $x$ mod $13$

Consider the elements of $[1,28]$ in couples: $(1,28),(2,27),(3,26),\ldots,(14,15)$.
It follows that there are $3^{14}$ subsets with the wanted property: for each couple, you have to choose among selecting the left element, the right element or none of them. At last, $$3^{14}\equiv 3^{2}\equiv\color{red}{9}\pmod{13}$$ by Fermat's little theorem.