The Euclidean algorithm is defined as:

Func gcd$($a$,$ b$)$:

if b $==0$:

return a

else:

return gcd$($b$,$ a $\%$ b$)$

$3$Consider the set of two nonnegative integer tuples $(,)$ where $.$ Define the relationship $$ as follows:

$(,)(,)$ means invoking the Euclidean algorithm with $(,)$ will lead to a recursive invocation of the

Euclidean algorithm with $(,).$

$1.$ Show that $$ is anti$-$symmetric. Please write a formal step$-$by$-$step proof and state your proof technique.

Note: anti$-$symmetry is defined as $,$ in $,==.$

$2.$ What is the transitive and symmetric closure of $?$ First, write down the definition, then prove it is

indeed true $($explain in English$)$