# Discrete math: proving gcd's and other fomulas

I have two questions:

• Suppose $a,b,s,t,u,v ∈ \mathbb{Z}$ such that $sa + tb = 21$ and $ua + vb = 10$. Show that $gcd(a,b) = 1.$

I feel like I'm going about this one in the wrong way. We haven't covered this material in class yet, all I know is that when $gcd(a,b) = 1$, it means that $a$ and $b$ are coprime. I tried substituting parts of each equation into each other but I don't really get any meaningful progress that way.

• given $p ∈ PRIME$, $gcd(a, p^2) = p$ and $gcd(b, p^3) = p^2$, find:

a. $gcd(a+b, p^4)$

b. $gcd(ab, p^4)$

• The gcd is the smallest linear combination that two numbers may have. Since $sa+tb = 21$ and $ua+vb=10$ we have $(s-2u)a+(t-2v)b = 1$. Thus the $gcd(a,b)=1$.
– Joel
Commented Feb 28, 2014 at 15:05

The GCD of a and b divides $sa + tb = 21$ and also $ua + vb = 10$. So the only such number is 1.

Indeed if $d$ divides $a$ and $b$, then it also divides $sa+tb=21$ and $ua+vb=10$, so it must divide $21-2\cdot10 = 1$.

The second question just says $p$ divides $a$, but $p^2$ does not and $p^2$ divides $b$, but $p^3$ does not, so it should be easy to see that $\gcd(a+b,p^4) = p$ and $\gcd(ab, p^4) = p\cdot p^2=p^3$.

I'll give you three hints, let me know if you can work out the solution:

$1^°$ HINT: look careful at the definition of gcd of two integers. Lots of exercises are only direct application of this definition

$2^°$ HINT: Try to prove this lemma, given $a,b,c \in \mathbb{Z}$ there exists $x,y \in \mathbb{Z}$ such that $$ax+by=c$$ if and only if gcd$(a,b) \mid c$

Even if you never see this kind of things, you basically need two results, the first hint and Bezout Identity which are essential in studying this kind of topics.

$3^°$ HINT if $p \mid a$ and $p \mid b$ then $p |a+b$. But now your other hypothesis should lead you to the right solution. To help you, $c \mid d \Leftrightarrow \exists u \in \mathbb{Z}$ such that $cu=d$

• I'm looking at bezout's identity, and I think I get most of it, except for this: is c the gcd, or some other number? Commented Feb 28, 2014 at 14:57
• my $c$ is a generic $c$ in Z :) Commented Feb 28, 2014 at 14:58
• in fact the power of the lemma is that it states whenever ax+by=c has solutions for arbitrary c Commented Feb 28, 2014 at 15:00
• @Kestrel In the first part, I recommend that you do not use Bezout's Lemma to deduce that $\,d\mid a,b\,\Rightarrow\, d\mid ax+by.\,$ Doing that is like using an atomic bomb to kill a mosquito (to borrow Arturo's words). Instead, this basic fact follows more simply and directly from basic properties of divisibility, i.e. $\,d\mid a\,\Rightarrow\,d\mid an,\,$ and $\,d\mid m,n\,\Rightarrow\, d\mid m+n.\,$ These are bread and butter of number theory. One must know them intimately to be proficient in number theory. Commented Feb 28, 2014 at 15:15

Hint $\$ For the first, use $\ c\mid a,b\,\Rightarrow\, c\mid ja+kb,\,$ for all $\,j,k\in\Bbb Z,\$ and $\, c \mid d,e\,\Rightarrow\,c\mid\gcd(d,e)$

For the second, show $\ \gcd(n,p^{j+1}) = p^j\Rightarrow\, n = \bar n\, p^j,\,\ p\nmid \bar n,\,$ then apply this to the given gcds with $\,n = a,b,\,$ then substitute the resulting factorizations of $\,a,b\,$ into the latter gcds, then pull out common factors, all using the gcd distributive law, or using (unique) prime factorizations.