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

1 Answer

  1. John- Reply


    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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You can use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>