Skip to main content
\(\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}}\)
Mathematics LibreTexts

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

    Definition

    Two integers are relatively prime 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 we have the following cases:

    Case I: \(d|a\) and \(d|b\)

    Then \(d=1\).

    Case II: \(d|a\) and \(d|2\)

    Then \(d=2\).

    Case III: \(d|2\) and \(d|b\)

    Then \(d=2\).

    Case IV:  \(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.\)