Shading the entire $i$-th row and $j$-th column of an $m\times n$ grid when $\gcd(i,m)>1$ and $\gcd(j,n)>1$, how many grids leave $x$ cells unshaded?

Question

Is there a way of cleverly counting the following scenario?

Given an $m\times n$ grid, with $m$ and $n$ relatively prime, imagine shading a subset of the squares of an $m\times n$ grid using this procedure:

• For each $i \in \{1,\dots,m\}$ such that $\gcd(i,m)>1$, shade all of the squares in the $i^\text{th}$ row.

• For each $j\in \{1,\dots,n\}$ such that $\gcd(j,n)>1$, shade all of the squares in the $j^\text{th}$ column.

Let $\sigma (x)$ be the number of ways to choose the ordered pair $(m,n)$ such $m$ and $n$ are relatively prime, and that there are exactly $x$ unshaded squares when you do this procedure.

Question: Is there a clever way to compute $\sigma(x)$?

For example $\sigma (8)$ represents the number of $m\times n$ squares such that it has $8$ holes. I can think of two grids which are in $\sigma(8$) and those are $3\times 5$ grids and the $4\times 5$ grids as drawn below (I shaded the third row and $5$th row for the $3\times 5$ grid as $3$ and $5$ are the only prime factors of the row and column numbers of $3$ and $5$ greater than $1$):

But there might be more than these two grids which are in $\sigma (8)$, so is there a formula for counting the total number of grids which fall under $\sigma(x)$ for any $0\le x $?

Answer 1

I do not think there is an explicit formula for this. However we can calculate it for a specific x. We find that the number of non shaded squares is $\phi(m) \phi(n)$. This is because $\phi(m)$ is the number of unshaded rows and $\phi(n)$ is the number of unshaded columns. We can simplify this to $\phi(mn)$ because they are relative prime. There is to my knowledge no explicit inverse function for $\phi$. In this link https://www.dcode.fr/euler-totient. It calculates it using an algoritm. (It also links how the algoritm works.) For example it gives for $x = 8$ the numbers $mn = 15,16,20,24,30$. We can find $\sigma(x)$ by finding al the different $m,n$ such that $m\times n = 15,16...30$ and counting these. (There are many ways to do this.) Thus for example is in this case $m = 4, n=4$ also a solution, because $4 \times 4 = 16$ and $\phi(16) = 8$. This is a long process, but I cannot make it easier.

Answer 2

As noted in the comment of @Mor A., the number $x$ of unshaded squares for given co-prime $m$, $n$ is $\phi(m)\phi(n)=\phi (mn)$. This product is always even. A brief table may help.

$$\begin{array}{c|clr} x & m\cdot n & \phi(m\cdot n) & \sigma(x) \\\hline 2 & 1\cdot3,1\cdot4,1\cdot6, 2\cdot3 & 1\cdot2 & 4\\4 & 1\cdot5,1\cdot8,1\cdot 10,1\cdot12,2\cdot5 & 1\cdot 4 & 5\\6 & 1\cdot7,1\cdot9,1\cdot14,1\cdot18,2\cdot7,2\cdot9 & 1\cdot6 & 6\\8 & 1\cdot15,1\cdot16,1\cdot20,1\cdot24,1\cdot30,2\cdot15;3\cdot5,3\cdot8,3\cdot10, 4\cdot5 & 1\cdot8;2\cdot4 & 10\\10 & 1\cdot11,1\cdot22, 2\cdot11 & 1\cdot10 & 3\\12 & 1\cdot13,1\cdot21,1\cdot26,1\cdot28,1\cdot36,1\cdot42, 2\cdot13,2\cdot21; 3\cdot7,3\cdot14,4\cdot7,4\cdot9,6\cdot7 & 1\cdot 12; 2\cdot 6 & 13\\14\\16 & 1\cdot17,1\cdot32,1\cdot34,1\cdot40,1\cdot48,1\cdot60, 2\cdot17;3\cdot16,3\cdot20 & 1\cdot16;2\cdot 8 & 9\\18 & 1\cdot19,1\cdot27,1\cdot38,1\cdot54, 2\cdot19,2\cdot27 & 1\cdot18 & 6\\20 & 1\cdot25,1\cdot33,1\cdot44,1\cdot66,2\cdot25,2\cdot33;3\cdot11,3\cdot22 & 1\cdot20;2\cdot 10 & 8\\ \end{array}$$To compute $\sigma (x)$ we must count all co-prime $(m,n)$ pairs for which $\phi(mn)=x$. This can be done, since for every (totient) even $x=ab$ there is a greatest integer $k$ such that $\phi(k)=ab$.

For example, in the array above, $x=1\cdot8=\phi(mn)$ only for$$mn=1\cdot15,1\cdot16,1\cdot20, 1\cdot24, 1\cdot30, 2\cdot15$$since $30$ is the greatest $n$ for which $\phi(n)=8$, and $2$ is the greatest $m$ for which $\phi(m)=1$.

Further, $x=2\cdot4=\phi(mn)$ only for$$mn=3\cdot5,3\cdot8,3\cdot10,4\cdot5$$since $10$ is the greatest $n$ for which $\phi(3)\phi(n)=2\cdot4$, and $3$ is the greatest odd $m$ for which $\phi(m)=2$.

Finally, $5$ is the greatest $n$ for which $\phi(4)\phi(n)=2\cdot4$. Thus for $x=8$,$$\sigma(x)=6+4+10$$[Note: There are no solutions for $x=14$ in the sample above, since ${14,26,34,38,50,62,…}$ (OEIS A005277), a subsequence of even $x$, are non-totients, i.e. are not $\phi(x)$ for any $x$, and thus like odd $x$ can be set aside.]

For a second, somewhat lengthier example, let $x=60$. Possible $2$-factor $x=ab=60$ are$$1\cdot60,2\cdot30,3\cdot20,4\cdot15,5\cdot12,6\cdot10$$However we can discard all pairs with an odd factor $>1$ since, except for $\phi(1)$ and $\phi(2)=1$, $\phi(mn)$ is always even $\times$ even. Accordingly we have$$\begin{array}{c|cl} 60 & m\cdot n & \phi(m\cdot n)\\\hline 1\cdot 60 & 1\cdot61,1\cdot77,1\cdot93,1\cdot99,1\cdot122,1\cdot124,1\cdot154,1\cdot186,1\cdot198 & 1\cdot 60\\2\cdot30 & 3\cdot31,3\cdot62, 4\cdot31, 6\cdot31 & 2\cdot30\\6\cdot10 & 7\cdot11,7\cdot22,9\cdot11,9\cdot22,14\cdot11,18\cdot11 & 6\cdot10\end{array}$$Thus for $x=60$,$$\sigma(x)=9+4+6=19$$

Although not a formula, and potentially time-consuming, this is a reliable method for computing $\sigma(x)$, given access to the Euler totient sequence for sufficiently large $x$ (OEIS A000010).