First, assume not all digits are the same (since then this problem is trivial).
Now note what happens if you exahcnge the two least significant digits. You either add or subtract a certain number a 2-digit one). Now, if you have a divisor in both the number and the one obtained by exchanging these digits, then this is also a divisor in this 2-digit number, so you have severely reduced the problem. You can do this for any two distinct digits in the number, thus getting a set of -digit numbers, the gcd of the permutations of the original number will divide the gcd of these numbers. (note that all these 2-digit number will be divisible by 9, so you need to check if the original number is divisible by 9, but this property is not changed by permuting the number anyway).
Now the problem has been reduced to checking among some 2-digit numbers, but we might not be done yet, since the gcd of the permutations of the original numbers might be even smaller.
I will think a bit about how one can easily make sure to get the actual gcd.