الرياضيات بالعربية

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

site lagrida الرياضيات بالعربية نظرية الأعداد Théorie des nombres تمارين حول القاسم المشترك الأكبر
لتكن $a,b,c$ أعداد من $\mathbb{Z}^{*}$ و $n \in \mathbb{N}^{*}$ بين الآتي :

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


$a \wedge b = 1 \Leftrightarrow a^n \wedge b^n = 1$


$a^n \wedge b^n = (a \wedge b)^n$


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


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


$ac \equiv bc[n] \Leftrightarrow a \equiv b [\dfrac{n}{c \wedge n}]$
نفرض ان : $a \wedge b = a \wedge c = 1$

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

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

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

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

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

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

حسب مبرهنة Bézout دائما : $a \wedge bc = 1$.

------------------------

نفترض أن $a \wedge bc = 1$.

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

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

لدينا : $ua + (vb)c = 1 \Rightarrow a \wedge c = 1$.

لدينا : $ua + (vc)b = 1 \Rightarrow a \wedge b = 1$.


نفترض أن $a \wedge b = 1$

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

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

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

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

------------------------

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

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

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

ومنه لدينا :

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

ومن حسب مبرهنة Bézout : $a \wedge b = 1$.


نضع $a \wedge b = d$

لدينا :

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


إذن

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


لاحظ أن $\alpha \wedge \beta = 1$ إذن حسب السؤال الثاني لدينا :

$\alpha^n \wedge \beta^n = 1$

إذن $a^n \wedge b^n = d^n = (a \wedge b)^n$.


نفترض أن $a | c$ و $b | c$ و $a \wedge b = 1$.

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

وبما ان $b | c$ فإن $b | a k$.

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

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

نعوض في الأول, لدينا : $c = a b k_1$.

إذن $ab | c$.


نفترض أن $a \wedge b = |a - b|$.

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

$\begin{align*}\begin{cases}a=a'|a-b| \\ b=b'|a-b|\end{cases} & \implies a-b=a'|a-b|-b'|a-b| \\& \implies a-b=(a'-b')|a-b| \\ & \implies a'-b'=\begin{cases} +1\; si \; a>b \\ -1\; si \; a<b \end{cases} \\ & \implies \begin{cases}b'= a'-1\; si \; a>b \\ b'=a'+1\; si \; a<b \end{cases}\end{align*}$

بوضع
$\begin{cases}p=a-b \; et \; q=+a'\quad si\; a>b \\p=a-b \; et \; q=-a' \quad si \; a<b \end{cases}$

نجد:
$si\; a>b: \begin{cases}a=a'(a-b)=qp \\ b=b'(a-b)=(q-1)p\end{cases}$

$si\; a<b: \begin{cases}a=-a'(a-b)=qp \\ b=-b'(a-b)=(q-1)p\end{cases}$

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


------------------------

الاستلزام العكسي:
نفرض أن:
$\exists p,q\in\mathbb{Z}^{*}: \begin{cases}a=pq \\ b=p(q-1) \end{cases}$

لاحظ أن $q\wedge (q-1)=1$ لأنهما عددين متتابعين. لدينا:
$\begin{align*}q\wedge (q-1)=1 & \implies pq\wedge p(q-1)=|p| \\ & \implies a\wedge b=|p|=|a-b| \end{align*}$

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

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



نضع $d=c\wedge n$ ومنه:

$\exists c',n'\in\mathbb{Z}:\begin{cases}c=c'd \\ n=n'd \\ c'\wedge n'=1\end{cases}$

الإستلزام الأول : نفترض أن $ac \equiv bc[n]$.

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

$(a-b)c=kn \iff (a-b)c'd=kn'd \iff (a-b)c'=kn'\quad ...(1)$

نلاحظ أن $c'|kn'$ لكن $c'\wedge n'=1$ ومنه $c'|k$ ، إذن $\exists k'\in\mathbb{Z}:k=k'c'$

$\begin{align*} (1)&\iff(a-b)c'=k'c'n' \\ &\iff a-b =k'n' \\ &\iff a\equiv b[n'] \\ &\iff a\equiv b\left[\frac{n}{d}\right] \end{align*}$

------------------------

الاستلزام العكسي:

$\begin{align*} a\equiv b\left[\frac{n}{d}\right] & \iff \exists k\in\mathbb{Z}:a-b=k\frac{n}{d} \\ & \iff \exists k\in\mathbb{Z}:(a-b)c=k\frac{c}{d}n=(kc')n \\ &\iff ac\equiv bc[n]\end{align*}$

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