1. Let us prove $g \leq n^2 - n$. The number of elements $m \in M$ such that $\gcd(m,n^2) = 1$ is $\varphi(n^2) \geq n$, since for $n = \prod_{k=1}^s p_k^{\alpha_k}$, with $p_k$ primes and $\alpha_k \geq 1$, we have $\varphi(n^2) = \prod_{k=1}^s (p_k -1) \cdot \prod_{k=1}^s p_k^{2\alpha_k - 1} \geq \prod_{k=1}^s p_k^{\alpha_k} = n$. To these elements $m$ thus correspond at least $n-1$ elements $a = m+1 \in M$ (since $n^2-1$ is one of those elements $m$, unavailable for $a$). As $ab - b = b(a-1)$, when $\gcd(a-1,n^2)=1$ we would need $n^2 \mid b$ in order to have $n^2 \mid ab - b$, impossible since $1\leq b \leq n^2-1$. Therefore the number of good elements is $g \leq (n^2-1) - (n-1) = n^2 -n$ (with equality reached for $n=2$). Moreover, any time $\gcd(a-1,n^2)=d > 1$, the element $a$ is good, since $b = n^2/d$ is then available, so in conclusion $a$ is good if and only if $\gcd(a-1,n^2) > 1$.

2. Let $a$ be a very good element, so $n^2 \mid a^2 - a = a(a-1)$. Since $\gcd(a,a-1) = 1$, it follows that we must have $a=\alpha x^2$ and $a-1 = \beta y^2$, with $\gcd(x,y) = 1$, $n=xy$ (and also some other restrictions, which are irrelevant). Now assume another very good element $a'$ induces the representation $a'=\alpha' x^2$ and $a'-1 = \beta' y^2$ (using the same $x$ and $y$; if one of them is the same, then the other one needs also be the same). Then $x^2 \mid a - a'$ and $y^2 \mid (a-1) - (a'-1) = a - a'$, so $n^2 = x^2y^2 \mid |a-a'| < n^2$, therefore $a=a'$, contradiction. As a consequence, the representations of the very good elements $a$ use distinct $x$'s and $y$'s. Let now $a_1,a_2,\ldots,a_v$ be the $v$ very good elements, with representations $a_k = \alpha_k x_k^2$, indexed such that $1 < x_1 < x_2 < \cdots < x_v$ (we cannot have $x_1 = 1$ since that would imply $y_1 = n$, and so $a_1 - 1 \geq n^2$; and we have seen that the $x_k$ need be distinct). It immediately follows $x_v \geq v+1$. But then, fixing $b = a_v = \alpha_vx_v^2$, we may choose $a = 1 + \lambda y_v^2$ for all $1 \leq \lambda \leq x_v^2 - 1$, since then $a \leq 1 + (x_v^2 - 1)y_v^2 < n^2$. Moreover, we have $b(a-1) = \alpha_v \lambda x_v^2 y_v^2 = \alpha_v \lambda n^2$, whence $n^2 \mid b(a-1)$. It means all these $a$'s are good, and there are $x_v^2 - 1 \geq (v+1)^2 - 1 = v^2 + 2v$ of them. This means $v^2 + 2v \leq g$, an improvement on the bound asked (and even more maybe could be garnered by considering the other $a_k$ elements, for $1\leq k<v$).

A small correction (needed, since we may have the case with $v=1$, $g=2$, for example for $n=2$, when $v^2 + v = g$). For an understandable reason (!?!), having reached the crux of the problem, I overlooked that in fact always $x_1 = 1$, since for $a_1 = 1$ we have $n^2 \mid 1(1-1) = 0$. The following fixes this oversight. In general we have $v\geq 1$ ($1$ is very good) and $g \geq 2$ ($1$ and $n+1$ are good). For $v = 1$ therefore we have $v^2 + v \leq g$ (with equality actually occuring for $n=2$, when $g=2$). If $v>1$, let us analyze when can we have (in the notations of above) $x_2=2$, i.e. $a_2 = \alpha_2\cdot 4$. This implies $n^2 \mid \alpha_2\beta_2 \cdot 4y_2^2$, thus $n^2 = 4y_2^2$, implying $n=2m$ ($m = y_2$). Then either $a_2 = m^2 + 1$, with $4 \mid m^2+1$, but then $4 \mid 3m^2 - 1$, so $a = 3m^2 > a_2$ is very good, contradiction, or $a_2 = 3m^2 + 1$, with $4 \mid 3m^2+1$, but then $4 \mid m^2 - 1$, so $1 < a = m^2 < a_2$ is very good, contradiction. Therefore, when $v>1$, we must have $x_2 > 2$, therefore (by the reasoning in the above) $x_v \geq v+1$, with the above proof leading to the conclusion $v^2 + v < v^2 + 2v \leq g$.

We will prove that g=n^2-f(n^2),where f denotes Euler's totient function. It is very easy to see that ab-b is div. by n^2( a,b are inM) <=>gcd(a-1,n^2)>1.Such that if gcd(a-1,n^2)=1=> b is div.by n^2,contradiction. And if gcd(a-1,n^2)=d>1,then we can take b=(n^2)/d<=(n^2)/2<=n^2-1 ,such that n>1.Thus b is in M and ab-b is div.by n^2. Thus we get that g is the number of a's in M s.t. gcd(a-1,n^2)>1.And this number equals to g=(n^2-1)-(f(n^2)-1)=n^2-f(n^2) =n^2-n*f(n)<=n^2-n and equality holds if and only if n=2. Let find the upper bound of v. if n=(product) p^a .a^2-a is div by n^2 implies that a=(u^2)*s ,and a-1=(v^2*t) ,with gcd (u,v)=1 ,n=uv, s is natural and t is nonnegative.s<v^2,and t<u^2. Thus u =(prod1)p^a, v=(prod2)p^a ,where the set od prime divisors of u and don't intersect and their union is the set of prime divisors of n. So we get that (u^2)*s-(v^2)*t=1,it has at most one solution in N,such that if there are 2 such solutions (s,t) and (p,q),then (u^2)*s-(v^2)*t=(u^2)*p-(v^2)*q=>(s-p) is div by v^2. which is impossible ,s.t 1<=s,p<v^2. Such that for each factoring of n=uv ,we get at most one solution ,then the number of very good elements is at most the number of such factorings.If the number of prime factors of n is k,then we get that this number is 2^k-2.So v<=2^k-2 where v is the number of very good elements. So v^2+v<=<4^k . Let prove that g>=4^k). Such that g=n^2-f(n^2)=n^2-nf(n)>=n^2-n(n-1)=n. And let prove that n>=4^k. The last one is true,because we can prove that only finitely many numbers don't satisfy to this inequality.For them we can calculate the value of g .This numbers are 2*3*5 and 2*3*7. So g>=v^2+v.

More,we can prove that lim(v/g)=0

Indeed, $g(n) = n^2 - \varphi(n^2)$, where $\varphi$ is the Euler totient, while $v(n) = 2^{\omega(n)} -1$, where $\omega$ is the arithmetic function counting the distinct primes dividing $n$.

i want to prove that if $n=p_1^{a_1}....P_k^{a_k}$ Then $v=2^k-1$ and $g=n^{2}-\varphi(n^{2})$ then it's easy to prove the inequlity. $x(x-1)\equiv 0\pmod{p^{2a_i}}$so this equality have to roots so the equality$x(x-1)\equiv 0\pmod{n^2}$have $2^k$roots(by chinese remainder) but $n^2$ is one of the roots so$v=2^k-1$ so we can prove the inequality.

Here is a solution, expanding upon mavropnevma's spoilers. Regarding $n^2 \mid b(a-1)$, if $\mbox{gcd}((a-1),n^2) = 1$, then $n^2 \mid b$, which is impossible for $1\leq b \leq n^2$; and if $\mbox{gcd}((a-1),n^2) = d>1$, then picking $b=\frac{n^2}{d}$ works. Hence $g$ is equal to $n^2-1$ minus the number of integers in $\{0,1,\ldots,n^2-2\}$ coprime with $n^2$, which is $n^2 - 1 - (\varphi(n^2) - 1) = n^2 - \varphi(n^2)$, where $\varphi$ is the Euler totient. In particular $g\leq n^2 - n$ is equivalent to $\varphi(n^2) \geq n$ which is provable in many ways - either by proving $\varphi(p^{2k}) \geq p^k$ for prime $p$ or just observing that $kn-1$, $k=1,2,\ldots,n$ are coprime with $n$. Regarding $n^2 \mid a^2 - a$, let $n = \prod_{i=1}^k p_i^{\alpha_i}$ - we equivalently want $p_i^{2\alpha_i} \mid a(a-1)$ for all $i$. As $a$ and $a-1$ are relatively prime, either $a\equiv 0 \pmod {p_i^{2\alpha_i}}$ or $a\equiv 1 \pmod {p_i^{2\alpha_i}}$. So for each $i$ there are two choices for the remainder of $a$ - hence by the Chinese Remainder Theorem there are $2^k$ choices for $a$ modulo $n^2$ overall. As we have to exclude the possibility $a=0$, we deduce $v = 2^k - 1$ and so $v^2 + v = 2^{2k} - 2^k$. To finish off, we will prove $4^k + \varphi(n^2) \leq n^2$ for $k\geq2$ (for $k=1$ we want $2+\varphi(n^2) \leq n^2$ which is true since $1$ and $n^2-1$ are coprime with $n^2$). Clearly $\varphi(n^2) \leq n^2-n$ (as multiples of $n$ are not coprime with $n$) and so if $n\geq 4^k$ we are done; this certainly holds when $3\nmid n$, as then (recall that $n$ is odd) $n = \prod_{i=1}^k p_i^{\alpha_i} \geq 5^k$. Now suppose $n=3^{\alpha}m$ and $m=\prod_{i=2}^k p_i^{\alpha_i}$. Then we want $4^k + 2\cdot 3^{2\alpha-1}\varphi(m^2) \leq 3^{2\alpha}m^2$ - equivalently, $\frac{4^k}{3^{2\alpha}} + \frac{2}{3}\varphi(m^2) \leq m^2$. With $\varphi(m^2) \leq m^2 - m$ we reduce to $\frac{4^k}{9} \leq \frac{m^2+2m}{3}$, which follows by $m=\prod_{i=2}^k p_i^{\alpha_i} \geq 5^{k-1}$.

My solution (beautiful problem): Consider a good number $a$, there exists $b\in M$ which satisfies $n^2\;|\;b(a-1)$ If $(a-1,n^2)=1$ then $n^2\;|\;b$ (contradiction since $1\leq b\leq n^2-1$) So we must have $(a-1,n^2)>1$ If $(a-1,n^2)=d>1$, choose $b=\frac{n^2}{d}$ then $n^2\;|\;b(a-1)$ So $a$ is good if and only if $(a-1,n^2)>1$ So we get the number of good numbers $a$ which is $n^2-1-(\varphi(n^2)-1)=n^2-\varphi(n^2)$ Notice that: $\varphi(n^2)=\displaystyle n^2\prod_{p\in\wp,p|n}\left(1-\frac{1}{p}\right)=n.n\prod_{p\in\wp,p|n}\left(1-\frac{1}{p}\right)=n\varphi(n)$ So we have $g=n^2-\varphi(n^2)=n^2-n\varphi(n)\leq n^2-n$ Consider the left inequality Consider a very good number $a$ $p$ is a prime factor of $n$, we have $p^{v_p(n^2)}\;|\;a(a-1)$ But $(a,a-1)=1$ so $p^{v_p(n^2)}\;|\;a$ or $p^{v_p(n^2)}\;|\;a-1$ If $p^{v_p(n^2)}\;|\;a$ for all $p|n$ then $n^2\;|\;a$ (contradiction since $1\leq a\leq n^2-1$) So we must have $a$ is very good if and only if for all prime factor $p$ of $n$ then $p^{v_p(n^2)}\;|\;a$ or $a-1$, also there must exists a prime factor $p$ of $n$ such that $p^{v_p(n^2)}\;|\;a-1$ Call $r$ the number of distinct prime factor of $n$ We can evaluate $v=2^r-1$ (simple counting) The problem becomes: Prove that $2^r(2^r-1)\leq n^2-\varphi(n^2)$ Induction on $r$. For $r=1$ the problem is trivial If the problem is true for some $r$, then $2^r(2^r-1)\leq n^2-\varphi(n^2)$, for all positive integer $n$ which have $r$ distinct prime factors Consider a prime number $q$ with $(q,n)=1$ We need to prove that $2^{r+1}(2^{r+1}-1)\leq q^{2\alpha}n^2-\varphi(q^{2\alpha}n^2)$ with some $\alpha\in\mathbb Z^+$, but it is true since $ q^{2\alpha}n^2\left(1-\prod_{p\in\wp,p|qn}\left(1-\frac{1}{p}\right)\right)\geq q^{2}n^2\left(1-\prod_{p\in\wp,p|qn}\left(1-\frac{1}{p}\right)\right)$ $=q^2n^2-\varphi(q^2n^2)$ $=q^2(n^2-\varphi(n^2))+q^2\varphi(n^2)-q(q-1)\varphi(n^2)$ $\geq q^2.2^r(2^r-1)+q\varphi(n^2)$ $\geq 4.2^r(2^r-1)+2n\varphi(n)$ $\geq 4.2^r(2^r-1)+2^{r+1}$ (since $n$ has $r$ distinct prime factors) $=2^{r+1}(2^{r+1}-1)$ Combining the 2 inequalities we have $m^2+m\leq k\leq n^2-n$, as desired The equality happens, for example $n=2$