4.4: Relatively Prime numbers

Definition: Relatively prime or Coprime

Two integers are relatively prime or Coprime 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 $d |\gcd(2a,2b).$ Since $gcd(2a,2b)=2 \gcd(a,b)$. $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.$

Multiplicative inverse modulo m

Let $m \in \mathbb{Z}_+.$  Let $a \in \mathbb{Z}$ such that $a$ and $m$ are relatively prime. Then there exist integers $x$ and $y$ such that $ax+my=1.$ Then  $ax \equiv 1 ( mod \,m )$. Note that $1$ is the multiplicative identity on $mod \,m$. In this case, $x (mod \,m)$ is the inverse of $a (mod \,m)$.

Example $\PageIndex{3}$

If possible, find multiplicative inverse of $2 (\mod 10).$

Solution

Since $\gcd(2,10)=2 \ne 1$, $2$ has no multiplicative inverse modulo $10.$

Example $\PageIndex{4}$

If possible, find multiplicative inverse of $16 (\mod 35).$

Solution

By using Euclidean Algorithm, we will find $gcd(16,35)$.

$$\begin{eqnarray*}35&=(16)(2)+3\\16&=(3)(5)+1\\3 &=(1)(3)+0\end{eqnarray*}$$

Thus $gcd(16,35)=1$. Hence multiplicative inverse of $16 (\mod 35)$ exists.

By using Bezout's algorithm,

$$\begin{eqnarray*}1&=16+(3)(-5)\\&=16+(35+(16)(-2)) (-5)\\&=(35)(-5)+(16)(11)\end{eqnarray*}$$

Thus $gcd(16,35)=1=(35)(-5)+(16)(11).$ Hence the multiplicative inverse of $16 (\mod 35)$ is $11$.