# 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$

## John-

2019-11-15

Consider the elements of $[1,28]$ in couples: $(1,28),(2,27),(3,26),\ldots,(14,15)$.

Every subset with the wanted property may contain at most one element from every couple.

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.