Skip to main content
Mathematics LibreTexts

4.4: Relatively Prime numbers

  • Page ID
    7591
  • This page is a draft and is under active development. 

    \( \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}}\)

    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)\).

    Example \(\PageIndex{3}\)

    If possible, find multiplicative inverse of \( 2 (\mod 10).\)

    Solution

    Since \(\gcd(2,10)=2 \ne 1\), \(2\) has no multiplicative inverse modulo \(10.\)

    Example \(\PageIndex{4}\)

    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\).

     


    4.4: Relatively Prime numbers is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by LibreTexts.

    • Was this article helpful?