We explore a couple of examples that involve relatively prime integers and greatest common divisor (gcd).
We will make use of the following fact:
Let $a$ and $b$ be any two integers, not both zero. Then an integer $d\ge 1$ is called a greatest common divisor of $a$ and $b$ if the following properties hold:
(i) $d/a$ and $d/b$ (ii) For any integer $k$, if $k/a$ and $k/b$, then $k/d$
Problem 1
Prove that if $(a, \ b) = d$, and $a = qb + r$, then $d/r$.
Proof
If $d = (a, \ b)$, then $d/a$ and $d/b$.
So $a = md$, $b = nd$ for some $m, \ n \in \mathbb{Z}$.
We thus have $r = a - qb = md - qnd = (m-qn)d$, and hence $d/r$
Problem 2
Let $a \ \text{and} \ b$ are relatively prime integers and suppose that $a$ divides $bc$, where $c \in \mathbb{Z}$. Prove that $a$ divides $c$.
Proof
Since $a$ and $b$ are relatively prime, $\implies$ $(a,b) = 1$ $\implies$ $ma + nb = 1$ for some $m, n \in \mathbb{Z}$.
$a/bc$ $\implies$ $bc = ka$, $k \in \mathbb{Z}$.
We need to show that $a/c$ i.e., $c = ra$, $r \in \mathbb{Z}$.
Thus, $mac + nbc = c$
$mac + nka = c$
$(mc + nk)a = c$, which $\implies$ $a/c$
Problem 3
Let $a$, $b$ and $c$ be integers. Suppose that $a$ and $b$ relatively prime and that $a$ and $c$ are also relatively prime. Prove that $a$ and $bc$ relatively prime.
Proof
Since $a$ and $b$ are relatively prime, $ma + nb = 1$, $m, n \in \mathbb{Z}$
Since $a$ and $c$ are relatively prime, $ka + sc = 1$, $k, s \in \mathbb{Z}$
So, $mac + nbc = c$
$smac + snbc = sc = 1 - ka$
$smac + ka + snbc = 1$
$(smc + k)a + (sn)bc = 1$. Thus $(a, bc) = 1$
Problem 4
Show that $(ma, mb) = m(a,b), \ m>0, \ m, \ n \in \mathbb{Z}.$
Solution
For natural numbers $a, \ b, \ d, \ m \ne 0$, suppose $(a,b) = d$ which implies $d/a$ and $d/b$ and thus $d = na + kb$ for some integers $n, \ k.$
$\implies$ $dm/ma,$ and $dm/mb$ and $dm = nma + kmb = (ma, mb)$ for some integers $n, \ k.$
Since $d = (a,b)$,
Then $dm = m(a,b) = (ma, mb)$
-
- Active Topics
-
-
- by Eli 12 hours ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 328 Views 37858
- by Eli 12 hours ago Re: What is in Your Mind? View the latest post Replies 705 Views 303586
- by Eli 4 days ago Russia Invades Ukraine View the latest post Replies 663 Views 238579
- by Eli 6 days ago PySpark for Large Data Processing View the latest post Replies 1 Views 7939
- by Eli 1 week ago President Museveni's Speech During International Development Association (IDA) Summit View the latest post Replies 1 Views 325
- by Eli 1 week ago From Simple Linear Regression Analysis to Covariance & Correlation to Independent Determinant, and R-Squared View the latest post Replies 11 Views 24936
- by Eli 2 weeks ago Collection of Greatest Christian Hymns of all Times View the latest post Replies 34 Views 70560
- by Eli 2 weeks ago Pondering Big Cosmology Questions Through Lectures and Dialogues View the latest post Replies 34 Views 58520
- by Eli 2 weeks ago Programmatically Manipulate Files: Renaming, Reading, Writing, Deleting, and Moving Files Between Folders View the latest post Replies 7 Views 18655
- by Eli 3 weeks ago Iran Launches Retaliatory Attack Against Israel, and Israel Retaliates by Attacking Iranian Isfahan Millitary Base View the latest post Replies 28 Views 20964
-
Relatively Prime Integers and gcd - Solved Examples
-
- Information
-
Who is online
Users browsing this forum: No registered users and 0 guests