For some reason, for my elementary number theory class, they want us do to stuff like writing the greatest common divisor of big numbers as a linear combination of them, or chinese remainder theorem with big numbers. This is a very tedious, long, frustrating and error-prone process.
For example, a question was to find integers $a,b$ such that $1680a+ 294b =\gcd(1680, 294)$. To apply euclidean algorithm, first you need to divide $1680$ by $294$. The only way i know to do this is by trial and error: $294$ is approximately $300$ so maybe $5$ or $6$ will work. Then i check if it works and continue.
Is there a more systematic faster way to do this? (methods both specific for this and for integer division are interesting).
Best Answer
The traditional way to do this is by Long division.
In this particular case, though (dividing $1680$ by $294$), the method that you have outlined is about as quick as you can get. Long division requires you to be able to calculate multiples of the divisor ($294$ in this case) up to $10\times$, by which point you'd already have surpassed $1680$.