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

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