Maximum subset pairwise not divisible by $K$

Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n_1$ and $n_2$, their sum is divisible to $K$, only if the sum of their remainder is divisible to $K$. In other words, $$K mid ( n_1 + n_2 ) ~~~~ Longleftrightarrow ~~~~ K mid left((n_1 ~mod ~K) + (n_2 ~mod ~K)right).$$ The second concept that you need to consider is that, the sum of two numbers $r_1 neq r_2$ is $K$, only if one of them is strictly smaller than $K/2$ and the other is no less than $K/2$. In other words, $$r_1 + r_2 = K ~~~Rightarrow~~~ r_1 <K/2, ~r_2 geq K/2~~~~~~ (r_1 neq r_2,~text{w.l.g.}~r_1 < r_2).$$ The third concept that you need to consider is that, if the sum of two numbers $r_1 neq r_2$ is $K$, they both deviate from $lceil K/2 rceil -1$ by a certain $k leq lceil K/2 rceil$, i.e., $$r_1 + r_2 = K ~~~Rightarrow~~~ exists_{k leq lceil K/2 rceil -1}~~~text{such that}~~~ r_1 = lceil K/2 rceil -1 -k, ~r_2 = lceil K/2 rceil +k.$$ So, for evey $k$ in the third concept, you need to put either $r_1$ or $r_2$ in the solution set, but not both of them. You are allowed to put one of the numbers that are actually divisible by $K$ and if $K$ is even, you can add only one number that its remainder is $K/2$. Therefore, here is the algorithm. Given a set ${cal N}={ n_1, n_2, cdots, n_N }$, let’s find the solution set ${cal S},$

1. Consider ${cal R} = { r_1=(n_1 ~mod ~K), r_2=(n_2 ~mod ~K), cdots, r_N=(n_N ~mod ~K) }$
2. ${cal S} gets emptyset$
3. for $k gets 1$ to $lceil K/2 rceil -1$:
4. $hspace{1.3em}$ if $count({cal R},k) geq count({cal R},K-k)$:
5. $hspace{2.6em}$ add all $n_i$ to ${cal S}$, such that $r_i=k$
6. $hspace{1.3em}$ else:
7. $hspace{2.6em}$ add all $n_i$ to ${cal S}$, such that $r_i=K-k$
8. add only one $n_i$ to ${cal S}$ such that $r_i=0hspace{1em}$// if exists
9. if $K$ is even:
10. $hspace{1.3em}$ add only one $n_i$ to ${cal S}$ such that $r_i=K/2hspace{1em}$// if exists
11. Output ${cal S}$

The algorithm is quite long, but the idea is very simple.