تمارين حول القاسم المشترك الأكبر

لتكن $\displaystyle{\displaylines{a,b,c}}$ أعداد من $\displaystyle{\displaylines{\mathbb{Z}^{*}}}$ و $\displaystyle{\displaylines{n \in \mathbb{N}^{*}}}$ بين الآتي :

$\displaystyle{\displaylines{\left\{\begin{matrix}a \wedge b = 1 \\ a \wedge c = 1\end{matrix}\right. \iff a \wedge bc = 1}}$

$\displaystyle{\displaylines{a \wedge b = 1 \iff a^n \wedge b^n = 1}}$

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

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

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

$\displaystyle{\displaylines{ac \equiv bc[n] \iff a \equiv b \left[\dfrac{n}{c \wedge n}\right]}}$

* الإتجاه $\displaystyle{\displaylines{\Longrightarrow)}}$ :

نفرض ان : $\displaystyle{\displaylines{a \wedge b = a \wedge c = 1}}$

لدينا حسب مبرهنة Bézout :

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

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

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

نضع $\displaystyle{\displaylines{u = \alpha x a + \alpha y c + \beta b x}}$ و $\displaystyle{\displaylines{v = \beta y}}$

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

حسب مبرهنة Bézout : $\displaystyle{\displaylines{a \wedge bc = 1}}$

* الإتجاه $\displaystyle{\displaylines{\Longleftarrow)}}$ :

نفترض أن $\displaystyle{\displaylines{a \wedge bc = 1}}$

حسب مبرهنة Bézout لدينا :

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

لدينا : $\displaystyle{\displaylines{ua + (vb)c = 1 \implies a \wedge c = 1}}$

لدينا : $\displaystyle{\displaylines{ua + (vc)b = 1 \implies a \wedge b = 1}}$

خلاصة :

$\displaystyle{\displaylines{\left\{\begin{matrix}a \wedge b = 1 \\ a \wedge c = 1\end{matrix}\right. \iff a \wedge bc = 1}}$

* الإتجاه $\displaystyle{\displaylines{\Longrightarrow)}}$ :

نفترض أن $\displaystyle{\displaylines{a \wedge b = 1}}$

لدينا حسب السؤال الأول : $\displaystyle{\displaylines{a \wedge b^2 = 1}}$

حسب السؤال الأول دائما : $\displaystyle{\displaylines{a \wedge b^3 = 1}}$

وهكذا حتى نصل إلى : $\displaystyle{\displaylines{a \wedge b^n = 1}}$

وبالمثل نبين $\displaystyle{\displaylines{a^n \wedge b^n = 1}}$

* الإتجاه $\displaystyle{\displaylines{\Longleftarrow)}}$ :

الآن نفترض أن $\displaystyle{\displaylines{a^n \wedge b^n = 1}}$

لدينا حسب مبرهنة Bézout :

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

ومنه لدينا :

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

حسب مبرهنة Bézout : $\displaystyle{\displaylines{a \wedge b = 1}}$

نضع $\displaystyle{\displaylines{a \wedge b = d}}$

لدينا :

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

إذن

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

لاحظ أن $\displaystyle{\displaylines{\alpha \wedge \beta = 1}}$ إذن حسب السؤال السابق لدينا :

$\displaystyle{\displaylines{\alpha^n \wedge \beta^n = 1}}$

إذن $\displaystyle{\displaylines{a^n \wedge b^n = d^n = (a \wedge b)^n}}$

* الإتجاه $\displaystyle{\displaylines{\Longrightarrow)}}$ :

نفترض أن $\displaystyle{\displaylines{a | c}}$ و $\displaystyle{\displaylines{b | c}}$ و $\displaystyle{\displaylines{a \wedge b = 1}}$

لدينا $\displaystyle{\displaylines{a | c}}$ وبالتالي توجد $\displaystyle{\displaylines{k}}$ من $\displaystyle{\displaylines{\mathbb{Z}}}$ بحيث : $\displaystyle{\displaylines{c = a k}}$

وبما ان $\displaystyle{\displaylines{b | c}}$ فإن $\displaystyle{\displaylines{b | a k}}$

لدينا $\displaystyle{\displaylines{a \wedge b = 1}}$ إذن حسب مبرهنة Gauss $\displaystyle{\displaylines{b | k}}$

إذن توجد $\displaystyle{\displaylines{k_1}}$ من $\displaystyle{\displaylines{\mathbb{Z}}}$ بحيث $\displaystyle{\displaylines{k = b k_1}}$

نعوض في الأول, لدينا : $\displaystyle{\displaylines{c = a b k_1}}$

إذن $\displaystyle{\displaylines{ab | c}}$

* الإتجاه $\displaystyle{\displaylines{\Longrightarrow)}}$ :

نفترض أن $\displaystyle{\displaylines{a \wedge b = |a - b|}}$

$\displaystyle{\displaylines{a \wedge b = |a-b| \iff \left\{\begin{matrix}\exists (\alpha, \beta) \in \mathbb{Z}^{2} \ : \ a = \alpha |a-b|, \quad b = \beta |a-b| \\ \alpha \wedge \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{ si : } \ a>b \\ -1 \ \text{ si : } \ a<b \end{cases} \\ & \implies \begin{cases}\beta= \alpha-1\ \text{ si : } \ a>b \\ \beta=\alpha+1\ \text{ si : } \ a<b \end{cases}\end{align*}}}$

بوضع:

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

نجد:

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

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

ومنه:

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

* الإتجاه $\displaystyle{\displaylines{\Longleftarrow)}}$ :

نفرض أن:

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

لاحظ أن $\displaystyle{\displaylines{q\wedge (q-1)=1}}$ لأنهما عددين متتابعين. لدينا:

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

ولدينا $\displaystyle{\displaylines{|a-b| = |pq-p(q-1)| = |p|}}$

ومنه:

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

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

* الإتجاه $\displaystyle{\displaylines{\Longrightarrow)}}$ :

نفترض أن $\displaystyle{\displaylines{ac \equiv bc[n]}}$, لدينا :

$\displaystyle{\displaylines{d=c\wedge n \iff \left\{\begin{matrix}\exists (\alpha, \beta) \in \mathbb{Z}^{2} \ : \ c = \alpha d, \quad n = \beta d \\ \alpha \wedge \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}}}$

لدينا $\displaystyle{\displaylines{\alpha|k\beta}}$ و $\displaystyle{\displaylines{\alpha\wedge \beta=1}}$ إذن حسب مبرهنة Gauss :$\displaystyle{\displaylines{\alpha|k}}$ ، وبالتالي :

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

انطلاقا من $\displaystyle{\displaylines{(1)}}$ لدينا $\displaystyle{\displaylines{(a-b) = k_1 \beta}}$, وبالتالي فإن :

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

إذن :

$\displaystyle{\displaylines{a \equiv b \left[ \dfrac{n}{c\wedge n}\right]}}$

* الإتجاه $\displaystyle{\displaylines{\Longleftarrow)}}$ :

نضع : $\displaystyle{\displaylines{d = c \wedge 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}}}$

خلاصة :

$\displaystyle{\displaylines{\boxed{ac\equiv bc[n] \iff a\equiv b\left[\frac{n}{c\wedge n}\right]}}}$