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

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)



    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.


    Let \(a, b\in \mathbb{Z}\).  If there exist integers \(x\) and \(y\) such that \(ax+by=1\) then   \(\gcd(a, b)=1\).


    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=+/- 1, since gcd is the greatest, d=1.