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

# 4.4: Relatively Prime numbers

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