# Finding GCD of all permutations of a decimal number [duplicate]

Possible Duplicate:
Computing GCD of all permutations (of the digits) of a given number.

How can we find the greatest common divisor (GCD) of all numbers that can be obtained by permuting the digits in the given number?

-

## marked as duplicate by Ross Millikan, Arturo Magidin, Akhil MathewMar 18 '11 at 13:49

Possible duplicate:math.stackexchange.com/questions/8943/… – Quixotic Feb 20 '11 at 12:50

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.

-

This has a weaker version which might give some hint as far as I am concerned.
In any case, thanks for paying attention and if I make some mistakes, please inform me.

-
That's a bit of too much mathematics for me :| – Quixotic Feb 16 '11 at 10:19
Maybe you can view numbers as values of polynomials at 10 with coefficients in the residue class ring $Z/(10)$, sorry for being unclear before. – awllower Feb 16 '11 at 13:26