Lagrida

درس الحسابيات في Z


قابلية القسمة في Z

ليكن $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ و $\displaystyle{\displaylines{n}}$ أعدادا من $\displaystyle{\displaylines{\mathbb{Z}^{*}}}$.

  • نقول أن $\displaystyle{\displaylines{a}}$ يقسم $\displaystyle{\displaylines{b}}$ ونكتب $\displaystyle{\displaylines{a|b}}$ إذا وفقط إذا وجد $\displaystyle{\displaylines{k \in \mathbb{Z}}}$ بحيث : $\displaystyle{\displaylines{b = a \, k}}$.


  • لدينا $\displaystyle{\displaylines{a}}$ قاسم لــ$\displaystyle{\displaylines{b}}$ و $\displaystyle{\displaylines{b}}$ مضاعف لــ$\displaystyle{\displaylines{a}}$


  • لدينا $\displaystyle{\displaylines{1|n}}$ و $\displaystyle{\displaylines{n|n}}$, نقول أن القواسم $\displaystyle{\displaylines{1,n}}$ أنها بديهية.


  • إذا وجد $\displaystyle{\displaylines{a | n}}$ و $\displaystyle{\displaylines{a \notin \{1,n\}}}$ نقول أن $\displaystyle{\displaylines{a}}$ قاسم فعلي.

مثال : لدينا $\displaystyle{\displaylines{3 | 15}}$ و $\displaystyle{\displaylines{5 | 35}}$, لكن $\displaystyle{\displaylines{6 \nmid 14}}$.

الموافقة بترديد

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

$\displaystyle{\displaylines{a \equiv b [n]}}$

و نقرأ "a يوافق b بترديد n". وتعني أن $\displaystyle{\displaylines{n}}$ يقسم $\displaystyle{\displaylines{a-b}}$.لدينا :

$\displaystyle{\displaylines{a \equiv b [n] \iff n | (a-b) \iff \exists k \in \mathbb{Z} \, : \, a = k \, n + b}}$.


إذا كان $\displaystyle{\displaylines{0 \leq b < n}}$ يمكننا أن نكتب أن $\displaystyle{\displaylines{a}}$ يوافق $\displaystyle{\displaylines{b}}$ بترديد $\displaystyle{\displaylines{n}}$ بالطريقة التالية : $\displaystyle{\displaylines{a = b \pmod {n}}}$.

خاصيات الموافقة بترديد :

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

  • $\displaystyle{\displaylines{a \equiv a [n]}}$


  • $\displaystyle{\displaylines{a \equiv b [n] \iff a+c \equiv b+c[n]}}$


  • $\displaystyle{\displaylines{a \equiv b [n] \implies ac \equiv bc[n]}}$ .


  • $\displaystyle{\displaylines{\left\{\begin{matrix}a \equiv b [n] \\ c \equiv d [n]\end{matrix}\right. \implies a+c \equiv b+d[n]}}$


  • $\displaystyle{\displaylines{\left\{\begin{matrix}a \equiv b [n] \\ c \equiv d [n]\end{matrix}\right. \implies ac \equiv bd[n]}}$


  • $\displaystyle{\displaylines{\forall k \in \mathbb{N} \, : \, a \equiv b [n] \implies a^k \equiv b^k[n]}}$


القسمة الأقليدية

القسمة الأقليدية في $\displaystyle{\displaylines{\mathbb{Z}}}$ :

$\displaystyle{\displaylines{(\forall (a,b) \in \mathbb{Z} \times \mathbb{Z}^{*}) \, (\exists !(q,r) \in \mathbb{Z} \times \mathbb{N}) \, : a = bq+r}}$
بحيث : $\displaystyle{\displaylines{0 \leq r < |b|}}$

القسمة الأقليدية في $\displaystyle{\displaylines{\mathbb{N}}}$ :

$\displaystyle{\displaylines{(\forall (a,b) \in \mathbb{N} \times \mathbb{N}^{*}) \, (\exists !(q,r) \in \mathbb{N}^{2}) \, : a = bq+r}}$
بحيث : $\displaystyle{\displaylines{0 \leq r < b}}$

  • $\displaystyle{\displaylines{a}}$ : المقسوم
  • $\displaystyle{\displaylines{b}}$ : المقسوم عليه
  • $\displaystyle{\displaylines{q}}$ : الخارج
  • $\displaystyle{\displaylines{r}}$ : الباقي

للبرهان على الخاصية من هنا : القسمة الأقليدية Division Euclidienne.

في القسمة الأقليدية في $\displaystyle{\displaylines{\mathbb{N}}}$ لدينا : $\displaystyle{\displaylines{a = bq + r}}$ مع $\displaystyle{\displaylines{0 \leq r < b}}$.
وبما أن $\displaystyle{\displaylines{b \in \mathbb{N}^{*}}}$ (أي $\displaystyle{\displaylines{b \neq 0}}$) فيمكننا القسمة على $\displaystyle{\displaylines{b}}$ :

$\displaystyle{\displaylines{\frac{a}{b} = q + \frac{r}{b}}}$ مع : $\displaystyle{\displaylines{0 \leq \frac{r}{b} < 1}}$.


وبالتالي فإن :

$\displaystyle{\displaylines{\left\{ \begin{array}{cl}q & = \ \left\lfloor \dfrac{a}{b} \right\rfloor \\r & = \ a - b \left\lfloor \dfrac{a}{b} \right\rfloor\end{array} \right.}}$


مع $\displaystyle{\displaylines{x \to \left\lfloor x \right\rfloor}}$ دالة الجزء الصحيح.

مثال : أنجز القسمة الأقليدية للعدد $\displaystyle{\displaylines{171}}$ على $\displaystyle{\displaylines{79}}$ :

لدينا الخارج يساوي : $\displaystyle{\displaylines{\left\lfloor \frac{171}{79} \right\rfloor = 2}}$.

والباقي : $\displaystyle{\displaylines{171 - 2 \times 79 = 13}}$.

إذن : $\displaystyle{\displaylines{171 = 79 \times 2 + 13}}$.

القاسم المشترك الأكبر

ليكن $\displaystyle{\displaylines{a,b}}$ عددين من $\displaystyle{\displaylines{\mathbb{Z}^{*}}}$.

القاسم المشترك الأكبر للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ هو أكبر قاسم موجب للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$.

ويرمز له بــ $\displaystyle{\displaylines{a \wedge b}}$ أو $\displaystyle{\displaylines{\gcd(a,b)}}$. لدينا :

$\displaystyle{\displaylines{a \wedge b = d \iff \left\{\begin{matrix}d | a \ , \ d | b \\ d_1 | a \ , \ d_1 | b \implies d_1 | d\end{matrix}\right.}}$

كيف نحدد القاسم المشترك الأكبر لعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ ؟

هناك العديد من الطرق نذكر منها :

التفكيك لجداء عوامل أولية

تقوم هذه الطريقة على تفكيك العددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ لجداء عوامل أولية ثم استنتاج القاسم المشترك الأكبر لهذين العددين.

هذه الطريقة مشروحة في الفقرة القاسم المشترك الأكبر / المضاعف المشترك الأصغر.

خوارزمية أقليدس لتحديد القاسم المشترك الأكبر
يتم تحديد القاسم المشترك الأكبر للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ عن طريق قسمات أقليدية متتالية (Algorithme d'Euclide).
ليكن $\displaystyle{\displaylines{b}}$ لا يقسم $\displaystyle{\displaylines{a}}$ :

$\displaystyle{\displaylines{\begin{array}{rcl}a=bq_0+r_0 & & 0 \leq r_0 < b \\b=r_0q_1+r_1 & & 0 \leq r_1 < r_0 \\r_0=r_1q_2+r_2 & & 0 \leq r_2 < r_1 \\.. & & \\.. & & \\r_{n-2}=r_{n-1}q_{n}+r_{n} & & 0 \leq r_{n} < r_{n-1} \\r_{n-1}=r_{n}q_{n+1}+0 & & \end{array}}}$

القاسم المشترك الأكبر للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ هو آخر باقي غير منعدم. لدينا $\displaystyle{\displaylines{a \wedge b = r_n}}$.

للحصول على البرهان من هنا : خوارزمية أقليدس لتحديد القاسم المشترك الأكبر.

مثال : حدد $\displaystyle{\displaylines{55 \wedge 145}}$ باستخدام خوارزمية أقليدس.

$\displaystyle{\displaylines{ \begin{array}{rcl}145 & = & 55 \times 2 + 35 \\55 & = & 35 \times 1 + 20 \\35 & = & 20 \times 1 + 15\\20 & = & 15 \times 1 + 5\\15 & = & 5 \times 3 + 0\end{array}}}$

إذن لدينا : $\displaystyle{\displaylines{145 \wedge 55 = 5}}$.

خاصيات :

  • القاسم المشترك الأكبر لعددين هو عدد موجب قطعا.


  • $\displaystyle{\displaylines{a | b \iff a \wedge b = |a|}}$


  • $\displaystyle{\displaylines{(ca) \wedge (cb) = |c| (a \wedge b)}}$

أمثلة:
$\displaystyle{\displaylines{\begin{matrix}21 \wedge 14 & = & 7 \\9 \wedge 10 & = & 1 \\10 \wedge 5 & = & 5\end{matrix}}}$

المضاعف المشترك الأصغر

ليكن $\displaystyle{\displaylines{a,b}}$ عددين من $\displaystyle{\displaylines{\mathbb{Z}^{*}}}$.

المضاعف المشترك الأصغر للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ هو أصغر مضاعف موجب للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$.

ويرمز له بــ $\displaystyle{\displaylines{a \vee b}}$ أو $\displaystyle{\displaylines{\mathrm{lcm}(a,b)}}$. لدينا :

$\displaystyle{\displaylines{a \vee b = m \iff \left\{\begin{matrix}a | m \ , \ b | m \\ a | m_1 \ , \ b | m_1 \implies m | m_1\end{matrix}\right.}}$


خاصيات :

  • المضاعف المشترك الأصغر لعددين هو عدد موجب قطعا.


  • $\displaystyle{\displaylines{a | b \iff a \vee b = |b|}}$


  • $\displaystyle{\displaylines{(ca) \vee (cb) = |c| (a \vee b)}}$

أمثلة:
$\displaystyle{\displaylines{\begin{matrix}21 \vee 14 & = & 42 \\9 \vee 10 & = & 90 \\10 \vee 5 & = & 10\end{matrix}}}$

الأعداد الأولية فيما بينها

ليكن $\displaystyle{\displaylines{a,b}}$ عددين من $\displaystyle{\displaylines{\mathbb{Z}^{*}}}$.
نقول أن العددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ أوليان فيما بينهما إذا وفقط إذا كان$\displaystyle{\displaylines{a \wedge b = 1}}$.

لدينا الخاصية التالية :

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

البرهان

مبرهنة Bézout


ليكن $\displaystyle{\displaylines{a,b}}$ عددين من $\displaystyle{\displaylines{\mathbb{Z}}}$.

1) متساوية Bézout :

$\displaystyle{\displaylines{a \wedge b = d \implies \exists (u, v) \in \mathbb{Z}^{2} \, : \, d = a u + b v}}$

ملاحظات :
  • الزوج $\displaystyle{\displaylines{(u,v)}}$ ليس وحيدا.
  • عكس المبرهنة غير صحيح.

2) مبرهنة Bézout :

$\displaystyle{\displaylines{a \wedge b = 1 \iff \exists (u, v) \in \mathbb{Z}^{2} \, : \, au+bv=1}}$

للحصول على البرهان : مبرهنة Bézout.


مبرهنة Gauss

لتكن $\displaystyle{\displaylines{a,b,c}}$ أعداد من $\displaystyle{\displaylines{\mathbb{Z}^{*}}}$.
تنص مبرهنة Gauss على الآتي :
$\displaystyle{\displaylines{\left\{\begin{matrix}c | ab \\ c \wedge a = 1\end{matrix}\right. \implies c | b}}$

البرهان من هنا

الأعداد الأولية

تعريف العدد الأولي

ليكن $\displaystyle{\displaylines{n \in \mathbb{N}^{*}}}$.

نقول أن العدد $\displaystyle{\displaylines{n}}$ عدد أولي إذا وفقط إذا كان $\displaystyle{\displaylines{n}}$ يقبل قاسمين بالضبط هما $\displaystyle{\displaylines{1}}$ و $\displaystyle{\displaylines{n}}$.

نرمز لمجموعة الأعداد الأولية بالرمز $\displaystyle{\displaylines{\mathbb{P}}}$.

الأعداد الأولية الأصغر من 100 :

$\displaystyle{\displaylines{2,3,5,7,11,13,17,19,23,29,31,37,41, \\ 43,47,53,59,61,67,71,73,79,83,89,97}}$


خاصيات :

ليكن $\displaystyle{\displaylines{n \in \mathbb{N}^{*}}}$ و $\displaystyle{\displaylines{p}}$ عدد أولي.

1) لدينا $\displaystyle{\displaylines{p | n}}$ أو $\displaystyle{\displaylines{n \wedge p = 1}}$.

2) مجموعة الأعداد الأولية غير منتهية. البرهان : بين أن مجموعة الأعداد الأولية غير منتهية.

3) إذا كان $\displaystyle{\displaylines{p}}$ و $\displaystyle{\displaylines{q}}$ عددان أوليان مختلفان فإن : $\displaystyle{\displaylines{p \wedge q = 1}}$.

4) $\displaystyle{\displaylines{\left\{\begin{matrix}p \in \mathbb{P} \\ p | ab\end{matrix}\right. \implies p|a \; \text{ou} \; p|b}}$

تتمتع الأعداد الأولية بالكثير من الخصائص التي تميزها عن باقي الأعداد. لهذا فهي موضوعة في اهتمامات الباحثين الرياضين لحل ألغازها ومحاولة فهم سلوكها وتوزيعها.

لإثبات أولية عدد $\displaystyle{\displaylines{n}}$ هناك العديد من الطريق مثل غربال إيراتوستين, أو طريقة الجذر مربع.

لدينا الخاصية التالية : $\displaystyle{\displaylines{n}}$ غير أولي $\displaystyle{\displaylines{\iff}}$ يوجد $\displaystyle{\displaylines{a}}$ عدد صحيح طبيعي يقسم $\displaystyle{\displaylines{n}}$ بحيث $\displaystyle{\displaylines{ 1 < a \leq \sqrt{n}}}$.

للحصول على البرهان : طريقة عملية لمعرفة أولية عدد.

وبالتالي لاختبار أولية عدد $\displaystyle{\displaylines{n}}$ يكفي قسمته على الأعداد الأولية الأصغر من $\displaystyle{\displaylines{\sqrt{n}}}$.

مبرهنة Wilson

ليكن $\displaystyle{\displaylines{p \in \mathbb{N}}}$ تنص مبرهنة Wilson على الآتي :


$\displaystyle{\displaylines{p}}$ أولي $\displaystyle{\displaylines{ (p-1)!+1 \equiv 0[p] \iff}}$


للحصول على البرهان : مبرهنة Wilson.

لاحظ أن هذه العلاقة تصلح فقط للجانب النظري في الرياضيات. لأننا إذا أردنا مثلا البرهان على أن $\displaystyle{\displaylines{17}}$ عدد أولي بمبرهنة Wilson لدينا :

$\displaystyle{\displaylines{(17-1)! + 1 = 20922789888001}}$ وعلينا اختبار قابلية القسمة لهذا العدد على $\displaystyle{\displaylines{17}}$ !!

مبرهنة Fermat الصغرى

تنص مبرهنة Fermat الصغرى على الآتي :

$\displaystyle{\displaylines{p \in \mathbb{P} \implies (\forall a \in \mathbb{Z}) \quad a^p \equiv a [p]}}$

وإذا كان $\displaystyle{\displaylines{p \wedge a = 1}}$ لدينا :

$\displaystyle{\displaylines{a^{p-1} \equiv 1 [p]}}$


للحصول على البرهان : مبرهنة فيرما الصغرى.

لاحظ أن عكس مبرهنة Fermat الصغرى غير صحيح. مثال : $\displaystyle{\displaylines{7^{25} \equiv 7 [25]}}$ لكن $\displaystyle{\displaylines{25}}$ ليس أولي.

المبرهنة الأساسية للحسابيات

تنص المبرهنة الأساسية للحسابيات على أن كل عدد صحيح نسبي غير منعدم $\displaystyle{\displaylines{n}}$ يمكن كتابته بكيفية وحيدة على شكل جداء عوامل أولية.

لدينا : $\displaystyle{\displaylines{n = \epsilon p_{1}^{\alpha_1} p_{2}^{\alpha_2}... p_{k}^{\alpha_k}}}$

بحيث $\displaystyle{\displaylines{p_1,p_2,...,p_k}}$ أعداد أولية موجبة مختلفة مثنى مثنى و $\displaystyle{\displaylines{\alpha_1,\alpha_2,...,\alpha_k}}$ أعداد صحيحة طبيعية. والعدد $\displaystyle{\displaylines{\epsilon = 1}}$ إذا كان $\displaystyle{\displaylines{n >0}}$ و $\displaystyle{\displaylines{\epsilon = -1}}$ إذا كان $\displaystyle{\displaylines{ n < 0}}$.

في كل ما سيأتي نعتبر $\displaystyle{\displaylines{\epsilon^2 = 1}}$ و $\displaystyle{\displaylines{\epsilon_1^{2} = 1}}$.

1) قواسم عدد :

ليكن $\displaystyle{\displaylines{n \in \mathbb{Z}^{*}}}$, لدينا التفكيك إلى جداء عوامل أولية للعدد : $\displaystyle{\displaylines{n = \epsilon p_{1}^{\alpha_1} p_{2}^{\alpha_2}... p_{k}^{\alpha_k}}}$.

إذا كان $\displaystyle{\displaylines{a}}$ يقسم العدد $\displaystyle{\displaylines{n}}$ فإن : $\displaystyle{\displaylines{a = \epsilon_1 p_{1}^{\beta_1} p_{2}^{\beta_2}... p_{k}^{\beta_k}}}$.

بحيث $\displaystyle{\displaylines{\forall i \in \{1,...,k\}\, 0 \leq \beta_i \leq \alpha_i}}$.

2) عدد قواسم عدد :

ليكن $\displaystyle{\displaylines{n \in \mathbb{N}^{*}}}$.

لدينا التفكيك إلى جداء عوامل أولية للعدد : $\displaystyle{\displaylines{n = p_{1}^{\alpha_1} p_{2}^{\alpha_2}... p_{k}^{\alpha_k}}}$.

إذا كان $\displaystyle{\displaylines{a}}$ عدد قواسم $\displaystyle{\displaylines{n}}$ الموجبة, لدينا : $\displaystyle{\displaylines{a = (1+\alpha_1) (1+\alpha_2) ... (1+\alpha_k)}}$.

مثال : حدد عدد قواسم العدد $\displaystyle{\displaylines{756}}$ الموجبة.

لدينا التفكيك لجداء عوامل أولية للعدد : $\displaystyle{\displaylines{756 = 2^2 3^3 7}}$.

وبالتالي عدد قواسم $\displaystyle{\displaylines{756}}$ الموجبة : $\displaystyle{\displaylines{(2+1) (1+3) (1+1) = 24}}$.

3) القاسم المشترك الأكبر / المضاعف المشترك الأصغر:

ليكن $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ عددين من $\displaystyle{\displaylines{\mathbb{Z}^{*}}}$.

التفكيك إلى جداء عوامل أولية للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ :

$\displaystyle{\displaylines{a = \epsilon p_{1}^{\alpha_1} p_{2}^{\alpha_2}... p_{k}^{\alpha_k} \quad b = \epsilon_1 p_{1}^{\beta_1} p_{2}^{\beta_2}... p_{k}^{\beta_k}}}$.

لاحظ أنه قمنا بعمل نفس الأعداد الأولية للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ إذ يكفي إذا كان مثلا $\displaystyle{\displaylines{p_i}}$ يوجد في تفكيك $\displaystyle{\displaylines{a}}$ ولا يوجد في تفكيك $\displaystyle{\displaylines{b}}$ أن نضع $\displaystyle{\displaylines{\beta_i = 0}}$ والعكس.

قمنا بتعريف القاسم المشترك الأكبر في السابق على أنه أكبر قاسم موجب للعدد $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ لدينا إذن :

$\displaystyle{\displaylines{d = a \wedge b = p_{1}^{\gamma_1} p_{2}^{\gamma_2}... p_{k}^{\gamma_k}}}$.

بحيث $\displaystyle{\displaylines{\forall i \in \{1,...,k\} \, \gamma_i = \min(\alpha_i, \beta_i)}}$.

خلاصة : القاسم المشترك الأكبر لعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ هو جداء العوامل الأولية المشتركة بين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ مرفوعة إلى أصغر أس.

قمنا بتعريف المضاعف المشترك الأصغر في السابق على أنه أصغر مضاعف موجب للعدد $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ لدينا إذن :

$\displaystyle{\displaylines{m = a \vee b = p_{1}^{\lambda_1} p_{2}^{\lambda_2}... p_{k}^{\lambda_k}}}$.

بحيث $\displaystyle{\displaylines{\forall i \in \{1,...,k\} \, \lambda_i = \max(\alpha_i, \beta_i)}}$.

خلاصة : المضاعف المشترك الأصغر لعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ هو جداء العوامل الأولية المشتركة وغير المشتركة للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ مرفوعة لأكبر أس.

ملحوظة : لاحظ أن $\displaystyle{\displaylines{\forall i \in \{1,...,k\} \quad \gamma_i + \lambda_i = \alpha_i + \beta_i}}$.

وبالتالي :
$\displaystyle{\displaylines{\begin{array}{rcl}(a \wedge b) \times (a \vee b) & = & p_1^{\gamma_1 + \lambda_1} p_2^{\gamma_2 + \lambda_2} ... p_k^{\gamma_k + \lambda_k} \\ \\& = & p_1^{\alpha_1 + \beta_1} p_2^{\alpha_2 + \beta_2} ... p_k^{\alpha_k + \beta_k} \\ \\& = & |ab|\end{array}}}$


مثال : حدد $\displaystyle{\displaylines{a \wedge b}}$ و $\displaystyle{\displaylines{a \vee b}}$ بحيث $\displaystyle{\displaylines{a = 120, \quad b=588}}$.

التفكيك لجداء عوامل أولية للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ يعطي :

$\displaystyle{\displaylines{\left\{ \begin{array}{cl}a & = \ 2^3 \times 3 \times 5 \\b & = \ 2^2 \times 3 \times 7^2\end{array} \right.}}$


أي أن :

$\displaystyle{\displaylines{\left\{ \begin{array}{cl}a & = \ 2^3 \times 3 \times 5 \times 7^0 \\b & = \ 2^2 \times 3 \times 5^0 \times 7^2\end{array} \right.}}$.


وبالتالي :

$\displaystyle{\displaylines{\left\{ \begin{array}{cl}a \wedge b & = \ 2^2 \times 3 \times 5^0 \times 7^0 = 12 \\a \vee b & = \ 2^3 \times 3 \times 5 \times 7^2 = 5880\end{array} \right.}}$

المعادلات الديفونتية الخطية

لتكن $\displaystyle{\displaylines{a,b,c}}$ أعدادا من $\displaystyle{\displaylines{\mathbb{Z}}}$.

المعادلة $\displaystyle{\displaylines{a x + by = c}}$ ذات المجهولين $\displaystyle{\displaylines{x}}$ و $\displaystyle{\displaylines{y}}$ في $\displaystyle{\displaylines{\mathbb{Z}^2}}$ تسمى المعادلة الديوفنتية الخطية والتي تنسب إلى العالم الرياضي اليوناني Diophantus.

خصائص :
  • للمعادلة $\displaystyle{\displaylines{a x + by = c}}$ حل في $\displaystyle{\displaylines{\mathbb{Z}^2}}$ $\displaystyle{\displaylines{\iff}}$ $\displaystyle{\displaylines{a \wedge b}}$ يقسم $\displaystyle{\displaylines{c}}$.


  • إذا كان الزوج $\displaystyle{\displaylines{(x_0,y_0)}}$ حلا للمعادلة $\displaystyle{\displaylines{a x + by = c}}$ فإن مجموعة حلول المعادلة $\displaystyle{\displaylines{(E)}}$ تكتب على الشكل :

    $\displaystyle{\displaylines{S = \left\{\left(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b}\right) \ \middle| \ k \in \mathbb{Z}\right\}}}$

للحصول على البرهان : المعادلات الديفونتية الخطية


لاحظ أن حل معادلة ديوفنتية راجع إلى إيجاد حل خاص $\displaystyle{\displaylines{(x_0, y_0)}}$ وهو دائما موجود بفضل متساوية Bézout. كيف نجد حلا خاصا ؟

لدينا حسب متساوية Bézout : $\displaystyle{\displaylines{d = a \wedge b \implies \exists (u, v) \in \mathbb{Z}^2 \quad au+bv = d}}$.

إذن يكفي إيجاد زوج$\displaystyle{\displaylines{(u, v)}}$ يحقق المتساوية أعلاه وحيث أن $\displaystyle{\displaylines{d}}$ يقسم $\displaystyle{\displaylines{c}}$ نقوم بالضرب في المعامل الآخر ونحصل على النتيجة.

مثال : أوجد حلا خاصا للمعادلة $\displaystyle{\displaylines{(E) \quad 56 x + 72 y = 40}}$.

هنا تكمن أهمية خوارزمية أقليدس لدينا :

$\displaystyle{\displaylines{ \begin{array}{rcl}72 & = & 56 \times 1 + {\color{DarkRed} 16} \\56 & = & 16 \times 3 + {\color{Blue} 8} \\16 & = & 8 \times 2 + 0\end{array}}}$


لدينا : $\displaystyle{\displaylines{56 \wedge 72 = 8}}$.

ولدينا $\displaystyle{\displaylines{8}}$ تقسم $\displaystyle{\displaylines{40}}$ إذن المعادلة $\displaystyle{\displaylines{(E)}}$ لديها حلول.

نضع $\displaystyle{\displaylines{a = 56, \quad b = 72}}$

$\displaystyle{\displaylines{\begin{array}{rcl}\longrightarrow {\color{DarkRed} 16} & = & b-a \\\longrightarrow {\color{Blue} 8} & = & a - {\color{DarkRed} 16}\times 3 \\ & = & a - (b-a)\times3 \\ & = & 4a-3b\end{array}}}$


وبالتالي فإن : $\displaystyle{\displaylines{56 \times 4 + 72 \times (-3)=8}}$

إذن : $\displaystyle{\displaylines{56 \times 20 + 72 \times (-15)=40}}$

هنا نكون قد وجدنا حلا خاصا للمعادلة $\displaystyle{\displaylines{(E)}}$ وهو $\displaystyle{\displaylines{(20, -15)}}$ و مجموعة الحلول بصفة عامة هي :

$\displaystyle{\displaylines{S = \{(20+9k, -15-7k) \, | \, k \in \mathbb{Z} \}}}$.

تمرين :

1) حل في $\displaystyle{\displaylines{\mathbb{Z}^2}}$ المعادلة : $\displaystyle{\displaylines{(E_1) \quad 5x+20y=7}}$.

2) حل في $\displaystyle{\displaylines{\mathbb{Z}^2}}$ المعادلة : $\displaystyle{\displaylines{(E_2) \quad 54x+21y=906}}$.

الحل

ملحوظة: ينصح بهذا الدرس لطلبة الأولى باك علوم رياضية وكذا ثانية باك علوم رياضية وأيضا الشعب العلمية الأخرى.
التعليقات :
إضافة تعليق