Choosing primes in the Paillier cryptosystem
Since $p$ and $q$ are primes, the only factors you need to rule out are those two numbers.

Suppose $p$ divides $(p-1)(q-1)$. Then it divides either $p-1$ (clearly not true) or $q-1$. The latter means $q-1 = p \cdot x$, for some $x \ge 2$ (if $x = 1$ either $p$ or $q$ is even, which is only possible if the numbers are 2 and 3). However, then $q \ge 2p+1$, so its binary representation is longer.

A similar argument proves $q$ can't be a factor. Thus, the GCD must be $1$.
If you just pick a random $g$ modulo $n^2$ the odds that it is a good choice are high (for large primes), so you usually only have to verify once. However, like your Wikipedia link states, you can just choose $g=n+1$ (when your primes are as long).

For $r$ you are also likely to get a good number randomly, but there you do have to check that neither $p$ nor $q$ divides it.

  We know that product of two $s$-bit numbers gives a number whose number of bits is between $s+1$ to 2$s$ , Suppose we are taking the equal length primes to ensure the property $\operatorname{gcd}(pq,(p-1)(q-1))=1$, then it is necessary to take $k$-bit primes  since $m&lt;n$ .


If you multiply two $s$-bit numbers the product is always either a $2s-1$-bit number or a $2s$-bit number. (Here an $s$-bit number means one which has its $s$th bit set.)


To allow any $k$-bit messages, it is necessary that $2s-1&gt;k$, so $s=k/2+1$ is enough.