## Bernoulli Battalions

The country of Bernoulli has a standing army of 809,957 soldiers. It has a trained reserve of 3,149,796 soldiers. Both the active and reserve forces are organized into battalions. All battalions are of the same size (standing army or reserve), and every battalion has its full complement of soldiers (every soldier is in a battalion).  What is the greatest number of soldiers in a Bernoulli Battalion?
Source: mathcontest.olemiss.edu 3/1/2010

SOLUTION
We want to find the greatest common divisor (GCD) of 809957 and 3149796.
$809957=331\times 2447$
$3149796=2^2\times 3\times 13\times 61\times 331$
GCD = 331.