Find the number of elements in set $A=\{1,2,\ldots, N\}$ such that the element has multiples in each row of a $N \times N$ square matrix.

Question

For a given $N$, the $N \times N$ grid looks like :

$1$ $\qquad$ $N+1$ $\qquad$ $2N+1$ $\qquad$ $3N+1$ $\qquad$...$\qquad$ $N(N-1)+1$

$2$ $\qquad$ $N+2$ $\qquad$ $2N+2$ $\qquad$ $3N+2$ $\qquad$... $\qquad$ $N(N-1)+2$

$\vdots$

$k$ $\qquad$ $N+k$ $\qquad$ $2N+k$ $\qquad$ $3N+k$ $\qquad$... $\qquad$ $N(N-1)+k$

$\vdots$

$N$ $\qquad$ $N+N$ $\qquad$ $2N+N$ $\qquad$ $3N+N$ $\qquad$... $\qquad$ $N(N-1)+N$

upon observation,I can see that the number of elements in A is the number of elements coprime with $N$.

that is the $\varphi(N)$ But i am not able to prove this. if anyone could prove this?

For example $N=3$ we have

$1$ $\quad$ $4$ $\quad$ $7$

$2$ $\quad$ $5$ $\quad$ $8$

$3$ $\quad$ $6$ $\quad$ $9$

and $\varphi(3)$=$2$

Answer 1

For a given number $k \in A$, consider the elements in each row $\bmod k$.

If $k$ is coprime to $N$ we will have at least one with every residue in $\Bbb {Z/Z}_k$, so there will be a $0$ and $k$ will have a multiple in the row.

If $k$ is not coprime to $N$ there is a row where the left hand element is not a multiple of $(k,N)$. All the elements of the row will be equivalent to this $\mod (k,N)$, so will not be a multiple of $k$.

Hence the number of elements of $A$ that have a multiple in each row is $\varphi(N)$