Find $GCD$ of $2021019$ and $1431471$
My solution:
$2021019 = 1\cdot(1431471) + 589548$
$1431471 = 2\cdot(589548) + 252375$
$589548 = 2\cdot(252375) + 84798$
$252375 = 2\cdot(84798) + 82779$
$84798 = 1\cdot(82779) + 2019$
$82779 = 41\cdot(2019)$
So $GCD$ of $2021019$ and $1431471$ is $2019$
Are there any other ways to solve this faster?
On
Here we avoid division by estimating the quotient and don't worry about negative residues.
We observe that
$\quad 2 \nmid 2021019 \land 2 \nmid 1431471$
and
$\quad 5 \nmid 2021019 \land 5 \nmid 1431471$
and this allows us some 'trick' flexibility in 'getting close to the modulus'.
Since $\frac{100}{14} \approx 7$ we can perform a trick and change the problem.
Problem: Find $\text{gcd}(2021019, 1431471) =$
$\quad\quad\quad \text{gcd}(5*2021019, 1431471) =$
$\quad\quad\quad \text{gcd}(10105095, 1431471)$.
Since $10105095 \approx 100 \cdot 10^5$ and $1431471 \approx 14 \cdot 10^5$ we (directly with quotient set to $7$) write
$\; 10105095 = (7)\cdot(1431471) + 84798$
New Problem: Find $\text{gcd}(1431471, 84798) =$
$\quad\quad\quad \text{gcd}(1431471, 42399)$
Since $1431471 \approx 143 \cdot 10^4$ and $42399 \approx 42 \cdot 10^3$ we estimate the quotient
(we've got an extra digit to use since $\Large \frac{10^4}{10^3} = 10$),
$\; \frac{143}{42} \approx 3.4$
and (directly with quotient set to $34$) write
$\; 1431471 = (34)\cdot(42399) - 10095$
New Problem: Find $\text{gcd}(42399, 10095) =$
$\quad\quad\quad \text{gcd}(42399, 2019)$.
When estimating the quotient it looks like $21$ works and we write
$\; 42399 = (21)\cdot(2019) + 0$
So
$\tag{ANSWER} \text{gcd}(2021019,1431471) = 2019$
Here is another method (using the tricks from the answer above) that is fast if you are an expert at subtraction and exact division with both $2$ and $10$.
$\quad\quad\quad \text{gcd}(2021019, 1431471) =$
$\quad\quad\quad \text{gcd}(2021019-1431471, 1431471) =$
$\quad\quad\quad \text{gcd}(589548, 1431471) =$
$\quad\quad\quad \text{gcd}(294774, 1431471) =$
$\quad\quad\quad \text{gcd}(147387, 1431471) =$
$\quad\quad\quad \text{gcd}(147387, 1431471-147387) =$
$\quad\quad\quad \text{gcd}(147387, 1284084) =$
$\quad\quad\quad \text{gcd}(147387, 642042) =$
$\quad\quad\quad \text{gcd}(147387, 321021) =$
$\quad\quad\quad \text{gcd}(147387, 321021-147387) =$
$\quad\quad\quad \text{gcd}(147387, 173634) =$
$\quad\quad\quad \text{gcd}(147387, 86817) =$
$\quad\quad\quad \text{gcd}(147387-86817, 86817) =$
$\quad\quad\quad \text{gcd}(60570, 86817) =$
$\quad\quad\quad \text{gcd}(6057, 86817) =$
$\quad\quad\quad \text{gcd}(6057, 86817-6057) =$
$\quad\quad\quad \text{gcd}(6057, 80760) =$
$\quad\quad\quad \text{gcd}(6057, 8076) =$
$\quad\quad\quad \text{gcd}(6057, 4038) =$
$\quad\quad\quad \text{gcd}(6057, 2019) =$
$\quad\quad\quad \text{gcd}(6057-2019, 2019) =$
$\quad\quad\quad \text{gcd}(4038, 2019) =$
$\quad\quad\quad \text{gcd}(2019, 2019)$
You can apply standard divisibility tests for certain prime factors, and thereby divide out any factors that "pass" to get smaller numbers. With base 10 representation we have reasonably easy tests for $2,3,5,7,11,13,37$. Letting $a=2021019$ and $b=1431471$ we apply these tests:
$2$ -> both odd final digits, both fail.
$3$ -> both give a digit sum divisible by $3$, divide both inputs by $3$ and note that the hlgcd willthen also be divided by $3$. Thus $a\to673673, b\to477157$.
$3$ again -> we see if we can extract another factor of $3$, but the sum of digits no longer passes for either input.
$5$ -> neither input ends in $0$ or $5$.
$11$ -> alternating sum of digits is divisible by $11$ for $a$ but not for $b$. Divide $a$ by $11$. $a\to61243,b=477157$.
$7,13$ -> alternating sum of three-digit groups is divisible by both of these factors for $a$ ($182=13×14$) but not for $b$. Divide $a$ by both factors or in one step by their product $91$. $a\to673,b=477157$.
$37$ -> sum of groups of three digits. This gives just $673$ back for $a$ but since that is $111×6+7$ it will not be divisible by $37$. For $b$ we get $634=111×6-32$, so this fails. Retain $a=673,b=477157$.
So we reduce to finding the gcd of 673 and 477157, then we have to multiply by $3$ because we commonly divided $a$ and $b$ by $3$ during the above reductions. It happens that $477157$ gives a zero remainder when divided by $673$, therefore render $673×3=2019$.