Let $\mathbb{N}\ni N>1$ and the set $\{1,2,\ldots ,N\}=:A$. For simplification purposes, we ask how many ordered pairs
$$(m,n)\in A\setminus\{1\}\times A\setminus\{1\}$$
there are such that $m,n$ are without common divisors i.e $(m,n)=1$. Omit the $1$, since we can add the $2N-1$ pairs after our work is finished.
Ties in with the original problem: Determine the probability that independently picked integers from set $A$ (repetition allowed), are without common divisors.
Since $N$ is fixed, we have some amount of primes
$$p_1 < p_2 < \ldots p_k \leq N $$
We also have for any $x\in A\setminus\{1\}$
$$x = p_1^{l_1}p_2^{l_2}\ldots p_k^{l_k} ,\quad l_i\geq 0$$
Now it gets rough: By fixing the pair $(m,n)$ we have:
$$m=p_1^{s_1}p_2^{s_2}\ldots p_k^{s_k},\ s_i\geq 0\qquad n=p_1^{t_1}p_2^{t_2}\ldots p_k^{t_k}, t_i\geq 0 $$
So we start counting powers
$$\left (\begin{array}{}s_1 & s_2 &\ldots & s_k\\t_1 & t_2 &\ldots &t_k \end{array}\right ) $$
For neither $m$ nor $n$ can we have all the primes represented with power $\geq 1$, since that immediately makes the other number equal to $1$, which we have omitted for now.
First, suppose only $t_1=0$, therefore we get $\prod_{j=2}^k t_j =: T_1$ possibilities for choice of $n$ and preserving desired property, another $s_1$ choices for $m$, making a total of $T_1\cdot s_1$ choices.
If we allow only one power to remain zero then the counting is simple.
Problems
As we increase the number of zero-th powers allowed we must start considering combinations and it's ugly because we have to consider Every case separately since we have no idea how the quantity of powers of $p_i$ behave.
Would this method guarantee that we have counted everything exactly once?
Is there an easier way of counting, for instance, would it be easier to count the complement of the set?
Another problem, the product needs to be $\leq N$, how do we know all the bounds? We don't.
I'm almost certain there's an embarrasingly simple solution to this problem.
Attempt at simplification
#1 Consider some small $N$, omit the $1$ and draw a grid, say, $\{2,3,4,5,6\}\times \{2,3,4,5,6\}$. Omit the diagonal automatically and consider only one half, since the relation is symmetrical. Get $6$ coprime pairs, total of 12 for this grid and for the whole of $A$ we get $11+12$ ordered pairs with desired property.
Good, right? NO! What if $N=100$? Ok, maybe $N=1000$? Definitely not.
#2
Can we set up a sieve? (work in progress)
The sieve would have to exclude all ordered pairs which are coprime (or with common divisor), but it's analogous to what I attempted earlier.
#3 something I remember from number theory:
$$(m,n)=1\iff \exists u,v\in\mathbb{Z}: um + vn =1 $$
Doesn't immediately seem helpful.
Let's try something different. Suppose we already know the function that counts these pairs. Let $N\in\mathbb{N}$ and define $f:\mathbb{N}\to\mathbb{N}$ such that
$$f(N) = |\{(m,n)\in A\times A : (m,n)=1\}| $$
where $A = \{1,\ldots ,N\}$
If we look at $f(N+1)$ we only need the pairs that contain coprimes to $N+1$:
$$f(N+1) = f(N) + 2\varphi (N+1) $$
where $\varphi$ is the Euler totient function.
but now due to this inductive definition, we can retrace our steps:
$$f(N+1) = f(N)+2\varphi (N+1) = \left [f(N-1)+2\varphi (N)\right ]+2\varphi (N+1) $$
etc.
Eventually we would arrive at:
$$f(N+1) = f(1) + 2\varphi (2)+2\varphi (3)+\ldots +2\varphi (N)+2\varphi (N+1) $$
Considerable improvement, but relevant only for small $N$, since how do we efficiently compute $$\sum_{j=k}^{k+l}\varphi (j) $$?. However, all things considered, I'd say this is the best I can achieve and it's far superior to counting powers as I attempted earlier.
Best Answer
Problem solved. The number of pairs is for any $1<N\in\mathbb{N}$ $$f(N) =1+2\sum_{j=2}^N \varphi (j) $$ Alternative approaches are also welcome.