Counting the number of N-dimensional coprime integer vectors
For $N=2$, the problem is easy: count the number of non-coprime pairs, by expressing it as a union over all possible values for their common divisor.  In particular, a pair $(x_1,x_2)$ is not coprime if there exists a $d&gt;1$ such that $d|x_1$ and $d|x_2$; for fixed $d$, it's easy to count the number of such pairs, so now just sum over all possible values of $d$.

For $N=3$, you could try using the following characterization:


$\gcd(x_1,x_2,x_3)=1$ iff either (a) $\gcd(x_1,x_2)=1$, or (b) $\gcd(x_1,x_2)&gt;1$ (so define $d=\gcd(x_1,x_2)$) and $\gcd(d,x_3)=1$.


These two conditions are mutually exclusive, so you can count the number of type-(a) triples and the number of type-(b) triples and then sum those two numbers, to get the number of co-prime triples.

You can count the number of triples of type-(a) quickly (by reducing to the $N=2$ case).  You can also count the number of triples of type-(b) quickly, by summing over all possible values of $d$ (for fixed $d$, the number of type-(b) tuples with a particular value of $d$ reduces to a smaller version of your problem with $N=2$ and a smaller value of $K$).

I think you can probably see how to generalize this to larger $N$, giving you a recursive algorithm to solve your problem for general $N$.  I'll let you work out the details.