Fdtxjr

I'm practicing for an exam and I'm stuck on one question. I hope I have translated this question properly, here it goes:

Question: How many subsets of the set $1,...,25$ have the property such that
no difference between two of its elements is divisible by $4$?

The solutions suggestions don't really suggest a solution on this, it just states the answer to be $8cdot7^3=2744.$ I don't even know to what chapter this question relates to in my discrete mathematics book.

If I understand this correctly, I should find subsets like these: $1,7,16$ since $4nmid (7-1), 4nmid (16-1)$ and $4nmid (16-7)?$

Well obviously it would take a long time to write them all up on an exam so I sense there is some nice trick to this?

There are $7$ integers in the set $S = 1,dots,25$ which are equal to $1$ modulo $4$, and there are $6$ integers in $S$ which are equal to $0$ modulo $4$, and similarly $6$ for $2$ modulo $4$ and $6$ for $3$ modulo $4$. A subset of $S$ has the desired property if and only if it contains at most one number from each of these four groups (any difference of them is then not equal to $0$ modulo $4$, i.e., not divisible by $4$; conversely, if two integers are included which are the same modulo $4$, their difference is divisible by $4$). So you have $8$ choices for the first group: $7$ to include one of the $7$ integers which are equal to $1$ modulo $4$ plus one choice to leave them out entirely; you have $7$ choices for the second group: $6$ to include one of the $6$ which are $0$ modulo $4$ plus one choice to leave them out entirely; and so on. That gives $8cdot 7cdot 7 cdot 7$ possibilities.

If no $2$ elements of a subset can have a difference divisible by $4$, those elements must belong to different remainder classes modulo $4$. The set $1,2,ldots,25$ contains $7$ elements $equiv 1 pmod 4$ , namly $1,5,9,ldots,25$ and $6$ elements $equiv 2,3,4 pmod 4$ each.

That means if we wanted to find all $4$-element subsets witht the required property, it would be $7cdot6^3$, because we need one element from each remainder class, and for $equiv 1 pmod 4$ there are 7 choices, for $equiv 2 pmod 4$ there are 6 choices a.s.o.

But since we are looking for arbitrary size subsets (well, arbitrary means size $le 4$, as otherwise 2 elements would be from the same remainder class), we use a trick. We add the numbers $26,27,28$ and $29$ to the set. If we have a subset of size smaller than $4$, we add the missing remainder classes from those 'new' numbers.

That is a one-to-one correspondence between all subsets of $1,2,ldots,25$ with the required property and all 4-element subsets of $1,2,ldots,29$ with the required property. Since we added 1 element to each remainder class, that number is $8cdot7^3$