An interesting question from my discrete math textbook:
Does the information
$\bullet$ $a * (21) + b * (-33) = 18$
$\bullet$ $a$ and $b$ are positive integers
suffice to find $gcd(a,b)$?
My immediate answer upon seeing the second bullet point was yes, since by Bezout's Theorem, if $a$ and $b$ are positive integers, then there must be some integers $s$ and $t$ such that $gcd(a,b) = sa + bt$, but how would I go about finding $gcd(a,b)$ in this case?
It seems I would need two specific values of $a$ and $b$, so I tried to "reverse engineer" a diophantic equation problem solving process to get some, beginning by simplifying the given equation:
$a * 21 + b * (-33) = 18 \rightarrow a * 7 + b * (-11) = 6$
But I'm not sure where to go from here.
You should start by finding the full set of solutions, which is not too difficult: $$ 7a - 11b = 6 $$ Let $b=7n+r$ and work in modulo $7$ to get $$ -4b = 6 \pmod 7 \implies 3b = 6 \pmod 7 \implies b=7n+2 $$ And then $$ 7a - 11 (7n+2)=6 \implies 7(a-11n) = 28 \implies a=4+11n $$ $n$ can be any non-negative integer (if $n<0$ then $b<0$ which is not allowed).
Now that we know what the solutions look like, plug in $n=1$ and $n=2$ and you will find that $$ \mbox{gcd}(a = 15, b=9) = 3\\ \mbox{gcd}(a = 26, b=16) = 2 $$ so the information is insufficient to determine $\mbox{gcd}(a, b) $$