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}}\)
[ "stage:draft", "article:topic", "calcplot:yes", "license:ccbyncsa", "showtoc:yes", "transcluded:yes" ]
Mathematics LibreTexts

4.4 Relatively Prime numbers

  1. Last updated
  2. Save as PDF
  • Page ID
    7591

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

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

    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=+/- 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\).

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