# 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?

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$$?

• For the $4 \times 5$ grid, shouldn't we only shade the $2$nd row and the $5$th column? Why is the $4$th row shaded, even though $4$ is not a prime number? Jan 24, 2023 at 16:40
• For the row number in $4\times 5$ grid its 4. So 4 has a prime factor of 2. So from the row number 1,2,3,4 the only ones which has a prime factor of 2 is 2,4 so I shaded 2 and 4. Let me correct the problem. Jan 24, 2023 at 17:11
• Note that the number of unshaded squares is exactly $\phi(m)\phi(n)$ where $\phi$ is the Euler Totient function, and in fact is equal to $\phi(mn)$ since $m,n$ are coprime. So the question is equivalent to finding numbers $t$ such that $\phi(t)=x$ and looking at decompositions of $t$ into two coprime factors. Jan 24, 2023 at 17:30
• Could you kindly give me an example of how to use the totient function for a specific value of $x$ ? Jan 24, 2023 at 17:55
• You should add restriction $m<n$. Jan 24, 2023 at 22:06

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.

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).