Help with finding subsets that are divisible by $3^k$

104 Views Asked by At

For positive integers $n$, let $v_3(n)$ denote the largest integer $k$ such that $3^k$ divides $n$. Find the number of subsets $S$ (possibly containing $0$ or $1$ elements) of $\{1, 2, \ldots ,81\}$ such that for any distinct $a, b \in S, v_3(a-b)$ is even.

So, I don't know how to start this problem, nor do I know what would consist of an answer - like what would a subset mean in this context? Any help with solving the problem would be much appreciated.

1

There are 1 best solutions below

13
On BEST ANSWER

A set with $0$ elements is an empty set, it is, a set with no elements. The empty set is usually denoted by $\emptyset$.

A set with $1$ element is a set of the form $\{a\}$ with $a$ being its only element. This kind of set is usally called a singleton.


Let's find which numbers $n$ have $v_3(n)$ even, and then you just has to express $n=a-b$ for $a,b\in S$. $v_3(n)$ even means that $n$ is divisible by one of the following (and not divisible by any larger power of $3$): $1$, $9$, $81$.

Every number is divisible by $1$, but you have to find those which are not divisible by any larger power of $3$. Here you've got $1$, $2$, $4$, $5$,... In general, the numbers of the form $1+3k$ or $2+3k$ with $k\in\mathbb{Z}$ small enough no stay in $\{0,1,\dots, 81\}$. Hence, you have the subsets $\{a,b\in \{0,1,\dots, 81\}: a\neq b,a-b=1+3k\}$ and $\{a,b\in \{0,1,\dots, 81\}: a\neq b,a-b=2+3k\}$.

Another way to write it, if you are familiar with congruences is $a-b\equiv 1\mod 3$ and $a-b\equiv 2\mod 3$ respectively.

Can you continue from here?