
# 4.4: Relatively Prime numbers


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