1.Let u and v be two positive integers with u/3<v<u/2.Then u mod v = u−2v.
2.Let u and v be two positive integers with u>v and let gcd(u,v) represent the greatest common divisor of u and v. If u and v are both odd, then gcd(u,v)=gcd(u−v,v)
How do I solve these questions? Can you share the steps to these quiz problems?
Asked my prof and he says:In general, exercising in some rudimentary basic number theory, e.g. to see how modp behaves, helps. The simplest way is of course just to use the definition of remainder and quotient: For any two positive integers u and v there exist unique non-negative integers q and r such that u=qv+r and 0≤r<v. Just manipulating these q and r alone one can accomplish a lot (personal experience).
Split this into two inequalities.
$u/3<v$ which implies $u<3v$. The second inequality is $u/2>v$. Which implies $u>2v$. So you have $$2v<u<3v$$
If you can show that $0≤u−2v<v$ that proves it is the remainder when you divide u by v.
2.You're asked to show whether or not. $gcd(u,v) = gcd(u-v,v)$
So let $a=gcd(u,v)$. let $b=gcd(u-v,v)$.
Show that $a|u-v$. Then since $a|(u-v)$ and $a|v$, then we know that $a|b$.
Similarly prove that $b|a$. Since a and b are positive and since $a|b$ and $b|a$ we know that $a=b$. (There are a couple of ways to show this. One is using inequalities. Since $a|b$, $a \le b$. Since $b|a$, $b \le a$. $a \le b$ and $b \le a$ means $a=b$)