Quote by Petek
kingwinner,
"Upon further review", your solution is correct and yes, the key was to express n as a linear combination of (n + 1)! + 1 and n! + 1.
Petek

Hrm. I think simply using the Euclidean algorithm (or a very slight adjustment) to compute the GCD works out to doing the same thing.