Not gonna lie

Since $G$ is a factor of $a$ and $a$ is a factor of $L$ , so $G$ is a factor of $L$ , if $G$ does not divide $L$ , then $N_{G,L}$ would be $0$ .

Lemma: The value of $N_{G,L}$ is the same as the number of pairs of positive integers $(a,b)$ such that $a$ and $b$ are relatively prime and their Least Common Multiple is $\frac{L}{G}$ .

Proof: We would establish a bijection between sets A, that consists of the pairs of positive integers $(a,b)$ such that $G=gcd(a,b)$ and $L=lcm(a,b)$ and set B, that consists of the pairs of positive integers such that $a$ and $b$ are relatively prime and their Least Common Multiple is $\frac{L}{G}$ .

We consider a certain ordered pair in $A$ . We divide both $a$ and $b$ by $G$ to get an ordered pair in $B$ . Likewise, if we consider an ordered pair in $B$ , we multiply both $a$ and $b$ by $G$ to get an ordered pair in $A$ . Hence we have established a bijection.

Now we find the number of pairs of positive integers $(a,b)$ such that $a$ and $b$ are relatively prime and their Least Common Multiple is $\frac{L}{G}$ .

Since $a$ and $b$ are relatively prime, they do not share any prime factor, so for each prime factor in $\frac{L}{G}$ , it would exist either in $a$ in $b$ , but not in both, and obviously, not in none of them. Hence, there are $2$ ways to choose (the exponent would be the same as the one in $\frac{L}{G}$ . Thus, the number of such ordered pairs is the $2$ raised to the number of prime factors in $\frac{L}{G}$ .

Now $\frac{L}{G}$ is at most $500$ . It could have at most $4$ different prime factors because the product of the first $5$ prime numbers is $(2)(3)(5)(7)(11)=2310$ , which is greater than $500$ . Hence, the maximum possible value of $N_{G,L}$ is $2^4=16$

Now if we let $L=420$ and $G=2$ , we would have $\frac{L}{G}=210$ , which has $4$ different prime factors: $2, 3, 5, 7$ . In this case, $N_{G,L}=2^4=16$ .

Thus, the largest possible value of $N_{G,L}$ is $\boxed{16}$ .

Since $G$ is the $\gcd$ , we can uniquely write: $a = GA \\ b=GB$ for some coprime integers $A,B$ . Then $L = GAB$ , from the definitions of $\gcd$ and $\mbox{lcm}$ .

So we need to find the maximum number of ways that a value $AB$ can be broken up into a pair of coprime factors, subject to the constraint that $GAB \le 1000$ .

Note that $G$ doesn't have to be coprime to $A,B$ . So we may as well go with the smallest possible value $G = 2$ .

If we have $AB = 2 \times 3 \times 5 \times 7 \\ G=2$ then $GAB = 420$ which is good; and since $AB$ has four prime factors then we can split it into a coprime pair in $2^4 = \boxed{16}$ ways - each prime factor is either in $A$ or in $B$ .

If we introduce a fifth distinct prime factor, the smallest possible is $11$ but that busts $GAB \gt 1000$ . Or if we introduce a power to the prime factors of this example, it gains nothing because of the requirement that $A,B$ be coprime - all powers of that factor would have to stay together.

So there is no way we can expand on this solution, which is $N_{2,420}$ .

NB. There is another value of $ab$ with the same $N_{G,L}$ value if we take $G=3$ , i.e. $N_{3, 630}$ .

Let the prime decomposition of $G$ be $p_1^{a_1} p_2^{a_2} \cdots p_n ^{a_n}$ and that of $L$ be $p_1^{b_1} p_2^{b_2} \cdots p_n ^{b_n}$ , where the $p_i$ s are prime and $a_i$ s and $b_i$ s are non-negative integers. It is obvious that $b_i \geq a_i$ for all $i$ . Note that $n$ is the number of primes in the prime decomposition of $L$ . If a prime $p_k$ is not present in the prime decomposition of $G$ , then we have $a_k=0$ (it was pretty obvious from the definition, but I thought it is better to clarify).

Let $a= p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}$ and $b= p_1^{d_1} p_2^{d_2} \cdots p_n^{d_n}$ . Then, note that $\gcd (a,b)= p_1^{min(c_1, d_1)} p_2^{min(c_2, d_2)} \cdots p_n^{min(c_n, d_n)}$ $lcm (a,b)= = p_1^{max(c_1, d_1)} p_2^{max(c_2, d_2)} \cdots p_n^{max(c_n, d_n)}$ Matching powers, we obtain $min(c_i,d_i) = a_i$ and $max(c_i, d_i)= b_i$ for all $i$ .
Let us determine how many possibilities this gives rise to for the $c_i$ s and $d_i$ s. If there are $k_i$ possibilities for $(c_i, d_i)$ for all $i$ , then by the multiplication principle we have $N_{G,L}= \prod \limits_{i=0}^{n} k_i$ Note that if we have $a_m= b_m$ for some $m$ , then there is only one possibility for $(c_m, d_m)$ : $c_m= d_m= a_m= b_m$ This implies that $N_{G,L}$ does not change if we remove all the primes from $G$ and $L$ that appear the same number of times in both $G$ and $L$ . So let us assume $a_i \neq b_i$ for all $i$ , thus $a_i > b_i$ .
Note that $min(c_i, d_i)= a_i$ and $max(c_i, d_i)= b_i$ , $b_i>a_i$ gives two possibilities for $(c_1,d_i)$ , as $c_i$ can take two values: $a_i$ or $b_i$ , and $d_i$ must take the other value. Then by the multiplication principle, we have $N_{GL}= 2^n$ .

We wish to find the largest possible value of $n$ for which we can find two integers lying in the range $[2, 1000]$ , of which the larger one has exactly $n$ prime divisors, and there exists no prime which appears a same number of times in both the integers. Note that if we set $G=2$ , $L= 2^2 \cdot 3 \cdot5 \cdot 7$ , then $n=4$ and $N_{G,L}= 2^4= 16$ . Note that this is the largest possible value of $n$ we can obtain, as we are trying to maximize the number of prime divisors of $L$ while minimizing the number of prime divisors of $G$ keeping the condition that no prime appears the same number of times in $G$ and $L$ . So we can conclude that our answer is $\boxed{16}$ .

Note: if the $1000$ was replaced by some larger positive integer $k$ , then our optimal choice of $(G,L)$ would be $(G,L)= (2, 2^2 \cdot 3 \cdot 5 \cdots p_x )$ , where $p_i$ is the $i_{th}$ prime and $x$ is the largest integer satisfying $2^2 \cdot 3 \cdot 5 \cdots p_x \leq k$ .

For largest possible value of $N_{G,L}$ , observe that we would need the GCD $G$ to be small, so that we can have more multiple-pairs of it.

Suppose we have positive integers $(a,b)$ st $a=Gh,b=Gk$ with $(h,k)=1$ . Note that $L=Ghk$ .

For $L \leq 1000$ & get more pairs, the greatest as such would occur for $G=2$ (& possibly for other values,but for 2 is sure,since it is the smallest prime). Then $hk \leq 500$ .

To have more pairs of $(h,k)$ , $(h,k)$ assume values divisible by single powers of primes only(observe that by allowing any of them to be a multiple of any higher power of a prime, number of pairs will fall as $hk$ increases but it is bounded above),

we know $2 \times 3 \times 5 \times 7 = 210 < 500$ , so we put $hk = 2\cdot 3\cdot 5\cdot 7$ , thereby furnishing $2^4 = 16$ ordered values for $(h,k)$ & in turn for $(a,b)$ .