The divisors of 36 are 1,2,3,4,6,9,12,18,36

500 more than these are 

501,502,503,504,506,509,512,518,536

The LCM of n and 36 must be among these

All multiples of 36 end with an even digit, so that
narrows the LCM of n and 36 down to

502,504,506,512,518,536

504 is the only one of those which is a multiple of 36

So 4 must be the GCD and 504 must be the LCM.

the factors of 504 are  

2*2*2*3*3*7   

and the factor of 36 are

2*2*3*3

since the GCD of 36 and n is 4, n must have 2 factors of 2.

In addition to those two 2 factors that n has in common 
with 36, n must also have another 2 factor as well
as a 7 factor, since 504 does and 36 doesn't. n doesn't need any 3 
factors because 36 has two 3 factors.  So n has the two 2 factors 
in common with 36 and an additional 2 factor.  That's three factors of 
2 and one 7 factor, and so n = 2*2*2*7=56

Edwin