Accueil Math in English
Exercices about the greatest common divisor (gcd)

# Exercices about the greatest common divisor (gcd)

Let $\displaystyle{\displaylines{a,b,c \in \mathbb{Z}^{*}}}$ and $\displaystyle{\displaylines{n \in \mathbb{N}^{*}}}$ prove that :

$\displaystyle{\displaylines{\left\{\begin{matrix}\gcd(a, b) = 1 \\ \gcd(a, c) = 1\end{matrix}\right. \iff \gcd(a, bc) = 1}}$

$\displaystyle{\displaylines{\gcd(a, b) = 1 \iff \gcd(a^n, b^n) = 1}}$

$\displaystyle{\displaylines{\gcd(a^n, b^n) = \gcd(a, b)^n}}$

$\displaystyle{\displaylines{\left\{\begin{matrix}a | c\\ b | c\\ \gcd(a, b)=1\end{matrix}\right. \implies ab | c}}$

$\displaystyle{\displaylines{\gcd(a, b) = |a-b| \iff \exists (p, q) \in \mathbb{Z}^{*} \, : \, b = p (q-1) \ \text{and} \ a = pq }}$

$\displaystyle{\displaylines{ac \equiv bc[n] \iff a \equiv b \left[\dfrac{n}{\gcd(c, n)}\right]}}$
$\displaystyle{\displaylines{\Longrightarrow)}}$ :

Assume that : $\displaystyle{\displaylines{\gcd(a, b) = \gcd(a, c) = 1}}$

According to Bézout's theorem we have :

$\displaystyle{\displaylines{\left\{\begin{matrix}\exists (\alpha, \beta) \in \mathbb{Z}^2 \quad a \alpha + b \beta = 1\\ \exists (x, y) \in \mathbb{Z}^2 \quad a x + c y = 1\end{matrix}\right.}}$

Then : $\displaystyle{\displaylines{(\alpha a + \beta b) (xa + yc) = 1}}$

Then : $\displaystyle{\displaylines{(\alpha x a + \alpha y c + \beta b x) a + \beta bc = 1}}$

We put $\displaystyle{\displaylines{u = \alpha x a + \alpha y c + \beta b x}}$ and $\displaystyle{\displaylines{v = \beta y}}$

Then $\displaystyle{\displaylines{\exists (u, v) \in \mathbb{Z}^2 \ : \ ua + vbc = 1}}$

According to Bézout's theorem : $\displaystyle{\displaylines{\gcd(a, bc) = 1}}$

$\displaystyle{\displaylines{\Longleftarrow)}}$ :

Assume that $\displaystyle{\displaylines{\gcd(a, bc) = 1}}$

According to Bézout's theorem :

$\displaystyle{\displaylines{\exists (u, v) \in \mathbb{Z}^2 \ : \ ua + vbc = 1}}$

we have : $\displaystyle{\displaylines{ua + (vb)c = 1 \implies \gcd(a, c) = 1}}$

we have : $\displaystyle{\displaylines{ua + (vc)b = 1 \implies \gcd(a, b) = 1}}$

Conclusion :

$\displaystyle{\displaylines{\left\{\begin{matrix}\gcd(a, b) = 1 \\ \gcd(a, c) = 1\end{matrix}\right. \iff \gcd(a, bc) = 1}}$

$\displaystyle{\displaylines{\Longrightarrow)}}$ :

Assume that $\displaystyle{\displaylines{\gcd(a, b) = 1}}$

According to the first question we have : $\displaystyle{\displaylines{\gcd(a, b^2) = 1}}$

Always according to the first question: $\displaystyle{\displaylines{\gcd(a, b^3) = 1}}$

And so on until we get to : $\displaystyle{\displaylines{\gcd(a, b^n) = 1}}$

Likewise we show that : $\displaystyle{\displaylines{\gcd(a^n, b^n) = 1}}$

$\displaystyle{\displaylines{\Longleftarrow)}}$ :

Now we assume that : $\displaystyle{\displaylines{\gcd(a^n, c^n) = 1}}$

According to Bézout's theorem :

$\displaystyle{\displaylines{\exists (u, v) \in \mathbb{Z}^2 \quad u a^n + v b^n = 1}}$

Then :

$\displaystyle{\displaylines{\exists (u, v) \in \mathbb{Z}^2 \quad (u a^{n-1}) a + (v b^{n-1}) b = 1}}$

According to Bézout's theorem : $\displaystyle{\displaylines{\gcd(a, b) = 1}}$

We put : $\displaystyle{\displaylines{\gcd(a, b) = d}}$

We have :

$\displaystyle{\displaylines{\gcd(a, b) = d \iff \left\{\begin{matrix}\exists (\alpha, \beta) \in \mathbb{Z}^2 \ : \ a = \alpha d, \quad b = \beta d \\ \gcd(\alpha, \beta) = 1\end{matrix}\right.}}$

Then

$\displaystyle{\displaylines{\begin{array}{rcl}\gcd(a^n, c^n) & = & \gcd((\alpha d)^n, (\beta d)^n)\\ & = & |d|^n \gcd(\alpha^n, \beta^n) \\ & = & d^n \gcd(\alpha^n , \beta^n) \\\end{array}}}$

Note that $\displaystyle{\displaylines{\gcd(\alpha, \beta) = 1}}$, then according to the previous question :

$\displaystyle{\displaylines{\gcd(\alpha^n, \beta^n) = 1}}$

Then : $\displaystyle{\displaylines{\gcd(a^n, c^n) = d^n = \gcd(a, b)^n}}$

$\displaystyle{\displaylines{\Longrightarrow)}}$ :

Assume that $\displaystyle{\displaylines{a | c}}$ and $\displaystyle{\displaylines{b | c}}$ and $\displaystyle{\displaylines{\gcd(a, b) = 1}}$

We have $\displaystyle{\displaylines{a | c}}$ then exists $\displaystyle{\displaylines{k}}$ in $\displaystyle{\displaylines{\mathbb{Z}}}$ that : $\displaystyle{\displaylines{c = a k}}$

Since $\displaystyle{\displaylines{b | c}}$ we have $\displaystyle{\displaylines{b | a k}}$

We have : $\displaystyle{\displaylines{\gcd(a, b) = 1}}$ So according to Gauss's theorem $\displaystyle{\displaylines{b | k}}$

Then exists $\displaystyle{\displaylines{k_1}}$ in $\displaystyle{\displaylines{\mathbb{Z}}}$ that $\displaystyle{\displaylines{k = b k_1}}$

We substitute, we have : $\displaystyle{\displaylines{c = a b k_1}}$

Then $\displaystyle{\displaylines{ab | c}}$

$\displaystyle{\displaylines{\Longrightarrow)}}$ :

Assume that : $\displaystyle{\displaylines{\gcd(a, b) = |a - b|}}$

$\displaystyle{\displaylines{\gcd(a, b) = |a-b| \iff \left\{\begin{matrix}\exists (\alpha, \beta) \in \mathbb{Z}^{2} \ : \ a = \alpha |a-b|, \quad b = \beta |a-b| \\ \gcd(\alpha, \beta) = 1\end{matrix}\right.}}$

\displaystyle{\displaylines{\begin{align*}\begin{cases}a=\alpha|a-b| \\ b=\beta|a-b|\end{cases} & \implies a-b=\alpha|a-b|-\beta|a-b| \\& \implies a-b=(\alpha-\beta)|a-b| \\ & \implies \alpha-\beta=\begin{cases} +1\ \text{ if : } \ a>b \\ -1 \ \text{ if : } \ a<b \end{cases} \\ & \implies \begin{cases}\beta= \alpha-1\ \text{ if : } \ a>b \\ \beta=\alpha+1\ \text{ if : } \ a<b \end{cases}\end{align*}}}

We put:

$\displaystyle{\displaylines{\begin{cases}p=a-b \ \text{ and } \ q=+\alpha\quad \text{if : } \ a>b \\p=a-b \ \text{ and } \ q=-\alpha \quad \text{if : } \ a<b \end{cases}}}$

Then:

$\displaystyle{\displaylines{\text{if } \ a>b: \begin{cases}a=\alpha(a-b)=qp \\ b=\beta(a-b)=(q-1)p\end{cases}}}$

$\displaystyle{\displaylines{\text{if } \ a<b: \begin{cases}a=-\alpha(a-b)=qp \\ b=-\beta(a-b)=(q-1)p\end{cases}}}$

Then:
$\displaystyle{\displaylines{\gcd(a, b)=|a-b|\implies \exists p,q\in\mathbb{Z}^{*}: \begin{cases}a=pq \\ b=p(q-1) \end{cases}}}$

$\displaystyle{\displaylines{\Longleftarrow)}}$ :

Assume that:
$\displaystyle{\displaylines{\exists p,q\in\mathbb{Z}^{*}: \begin{cases}a=pq \\ b=p(q-1) \end{cases}}}$

Note that $\displaystyle{\displaylines{\gcd(q, q-1)=1}}$ Because they are two consecutive numbers. We have :

\displaystyle{\displaylines{\begin{align*} \gcd(q, q-1)=1 & \implies \gcd(pq, p(q-1))=|p| \\ & \implies \gcd(a, b)=|p| \end{align*}}}

And we have $\displaystyle{\displaylines{|a-b| = |pq-p(q-1)| = |p|}}$

Then:
$\displaystyle{\displaylines{\begin{cases}a=pq \\ b=p(q-1) \end{cases} \; , \; (p,q)\in(\mathbb{Z^*})^2 \implies \gcd(a, b)=|a-b|}}$

$\displaystyle{\displaylines{\boxed{\gcd(a, b)=|a-b| \iff \exists (p,q)\in(\mathbb{Z^*})^2:\begin{cases}a=pq \\ b=p(q-1) \end{cases} }}}$

$\displaystyle{\displaylines{\Longrightarrow)}}$ :

We assume that : $\displaystyle{\displaylines{ac \equiv bc[n]}}$, We have :

$\displaystyle{\displaylines{d=\gcd(c, n) \iff \left\{\begin{matrix}\exists (\alpha, \beta) \in \mathbb{Z}^{2} \ : \ c = \alpha d, \quad n = \beta d \\ \gcd(\alpha, \beta) = 1\end{matrix}\right.}}$

$\displaystyle{\displaylines{ac\equiv bc[n]\iff \exists k\in\mathbb{Z}:(a-b)c=kn}}$

$\displaystyle{\displaylines{\begin{array}{rcl}(a-b)c=kn & \iff & (a-b) \alpha d=k \beta d \\ & \iff & (a-b)\alpha=k\beta\end{array} \tag{1}}}$

We have $\displaystyle{\displaylines{\alpha|k\beta}}$ and $\displaystyle{\displaylines{\gcd(\alpha, \beta)=1}}$ Then using Gauss's theorem we have :$\displaystyle{\displaylines{\alpha|k}}$ ، then :

$\displaystyle{\displaylines{\exists k_1\in\mathbb{Z} \ : \ k=k_1 \alpha}}$

From $\displaystyle{\displaylines{(1)}}$ we have : $\displaystyle{\displaylines{(a-b) = k_1 \beta}}$, then:

$\displaystyle{\displaylines{a \equiv b \left[ \beta \right]}}$

Then :

$\displaystyle{\displaylines{a \equiv b \left[ \dfrac{n}{\gcd(c, n)}\right]}}$

$\displaystyle{\displaylines{\Longleftarrow)}}$ :

We put : $\displaystyle{\displaylines{d = \gcd(c, n)}}$

$\displaystyle{\displaylines{\begin{array}{rcl}a\equiv b\left[\dfrac{n}{d}\right] & \implies & \exists k\in\mathbb{Z} \ : \ a-b = k\dfrac{n}{d} \\ & \implies & (a-b)c=k\dfrac{c}{d}n \\ & \implies & (a-b)c = (kc_1)n , \quad (c = c_1 \times d) \\ & \implies & ac \equiv bc \left[n\right]\end{array}}}$

Conclusion:

$\displaystyle{\displaylines{\boxed{ac\equiv bc[n] \iff a\equiv b\left[\frac{n}{\gcd(c, n)}\right]}}}$
Accueil Math in English
Exercices about the greatest common divisor (gcd)
Les commentaires :
Ajouter un commentaire