4.4: Relatively Prime numbers
- Page ID
- 7591
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Definition: Relatively prime or Coprime
Two integers are relatively prime or Coprime when there are no common factors other than 1. This means that no other integer could divide both numbers evenly. Two integers \(a, b\) are called relatively prime to each other if \(\gcd(a, b)=1\).
For example, \(7\) and \(20\) are relatively prime.
Theorem
Let \(a, b\in \mathbb{Z}\). If there exist integers \(x\) and \(y\) such that \(ax+by=1\) then \(\gcd(a, b)=1\).
Proof:
Let \(a, b\in \mathbb{Z}\), such that d= \(\gcd(a, b)\). Then d|a and d|b.
Hence \(d|(ax+by)\), thus \(d|1\). Which implies \(d=\pm 1\), since gcd is the greatest, \(d=1.\)
Example \(\PageIndex{1}\):
Suppose \(a\) and \(b\) are relatively prime integers. Prove that \( \gcd(a+b,a-b)=1,\) or \(2\).
Solution
Let \(a\) and \(b\) be relatively prime integers. Then \(\gcd(a,b)=1\). Suppose \( d=\gcd(a+b,a-b)\). Then \(d |(a+b)\) and \(d|(a-b)\). Then \(a+b=dm\) and \(a-b=dn\) for some \(m,n \in \mathbb{Z}\). Now \( 2a= d(m+n)\) and \(2b=d(m-n)\). Thus \(d|2a\) and \(d|2b\). Hence \(d |\gcd(2a,2b).\) Since \(gcd(2a,2b)=2 \gcd(a,b)\). \(d|2\). Thus \(d=1\) or \(2.\)
Example \(\PageIndex{2}\):
Suppose \(a\) and \(c\) are relatively prime integers and \(b\) is an integer such that \(b|c.\) Prove that \(gcd(a,b)=1.\)
Solution
Let \(a\) and \(c\) be relatively prime integers. Then \(\gcd(a,c)=1\). Thus there exist integers \(x\) and \(y\) such that \(ax+cy=1\). Suppose \(b\) is an integer such that \(b|c.\) Then \(c=bm\) for some \(m \in \mathbb{Z}\). Now \(ax+bmy=1\). Therefore, \(gcd(a,b)=1.\)
Multiplicative inverse modulo m
Let \(m \in \mathbb{Z}_+.\) Let \(a \in \mathbb{Z}\) such that \(a\) and \(m\) are relatively prime. Then there exist integers \(x\) and \(y\) such that \(ax+my=1.\) Then \(ax \equiv 1 ( mod \,m ) \). Note that \(1\) is the multiplicative identity on \(mod \,m \). In this case, \(x (mod \,m) \) is the inverse of \(a (mod \,m)\).
If possible, find multiplicative inverse of \( 2 (\mod 10).\)
Solution
Since \(\gcd(2,10)=2 \ne 1\), \(2\) has no multiplicative inverse modulo \(10.\)
If possible, find multiplicative inverse of \( 16 (\mod 35).\)
Solution
By using Euclidean Algorithm, we will find \(gcd(16,35)\).
\begin{eqnarray*}35&=(16)(2)+3\\16&=(3)(5)+1\\3 &=(1)(3)+0\end{eqnarray*}
Thus \(gcd(16,35)=1\). Hence multiplicative inverse of \( 16 (\mod 35)\) exists.
By using Bezout's algorithm,
\begin{eqnarray*}1&=16+(3)(-5)\\&=16+(35+(16)(-2)) (-5)\\&=(35)(-5)+(16)(11)\end{eqnarray*}
Thus \(gcd(16,35)=1=(35)(-5)+(16)(11).\) Hence the multiplicative inverse of \( 16 (\mod 35)\) is \(11\).