One more nitpick on the upper bound of the GCD: since we know that 0 is going to be in every column, one of the row numbers must start with a 0 and will be an 8-digit number (0 in the first cell). The GCD can't be larger than the smallest row number.

The GCD search should start at 098,765,432 and then go down from there.