ليكن $\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{\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{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{a}}$ و $\displaystyle{\displaylines{b}}$ هو آخر باقي غير منعدم. لدينا $\displaystyle{\displaylines{a \wedge b = r_n}}$.
ليكن $\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{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.}}$
البرهان
1) نفترض أن $\displaystyle{\displaylines{d = a \wedge b}}$
لدينا إذن : $\displaystyle{\displaylines{d |a}}$ و أيضا $\displaystyle{\displaylines{d | b}}$ إذن :
$\displaystyle{\displaylines{\exists (\alpha , \beta) \in \mathbb{Z^{*}}^{2} \quad a = \alpha d ; \quad b = \beta d }}$
وبالتالي $\displaystyle{\displaylines{d = a \wedge b = (\alpha d) \wedge (\beta d) = |d| (\alpha \wedge \beta)}}$.
لتكن $\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{c \wedge a = 1}}$ و $\displaystyle{\displaylines{c | ab}}$.
لدينا حسب مبرهنة Bézout : $\displaystyle{\displaylines{a \wedge c = 1 \iff (\exists(u,v) \in \mathbb{Z}^{2});au+cv = 1}}$.
نقوم بالضرب في $\displaystyle{\displaylines{b}}$ : $\displaystyle{\displaylines{bau+bcv = b \quad (\star)}}$.
لدينا أيضا $\displaystyle{\displaylines{c | ab}}$ إذن يوجد $\displaystyle{\displaylines{k}}$ من $\displaystyle{\displaylines{\mathbb{Z}}}$ بحيث : $\displaystyle{\displaylines{ab = ck}}$
نعوض في $\displaystyle{\displaylines{\star}}$ لدينا : $\displaystyle{\displaylines{cku+bcv = b}}$.
نقول أن العدد $\displaystyle{\displaylines{n}}$ عدد أولي إذا وفقط إذا كان $\displaystyle{\displaylines{n}}$ يقبل قاسمين بالضبط هما $\displaystyle{\displaylines{1}}$ و $\displaystyle{\displaylines{n}}$.
نرمز لمجموعة الأعداد الأولية بالرمز $\displaystyle{\displaylines{\mathbb{P}}}$.
3) إذا كان $\displaystyle{\displaylines{p}}$ و $\displaystyle{\displaylines{q}}$ عددان أوليان مختلفان فإن : $\displaystyle{\displaylines{p \wedge q = 1}}$.
تتمتع الأعداد الأولية بالكثير من الخصائص التي تميزها عن باقي الأعداد. لهذا فهي موضوعة في اهتمامات الباحثين الرياضين لحل ألغازها ومحاولة فهم سلوكها وتوزيعها.
لإثبات أولية عدد $\displaystyle{\displaylines{n}}$ هناك العديد من الطريق مثل غربال إيراتوستين, أو طريقة الجذر مربع.
لدينا الخاصية التالية : $\displaystyle{\displaylines{n}}$ غير أولي $\displaystyle{\displaylines{\iff}}$ يوجد $\displaystyle{\displaylines{a}}$ عدد صحيح طبيعي يقسم $\displaystyle{\displaylines{n}}$ بحيث $\displaystyle{\displaylines{ 1 < a \leq \sqrt{n}}}$.
لاحظ أن هذه العلاقة تصلح فقط للجانب النظري في الرياضيات. لأننا إذا أردنا مثلا البرهان على أن $\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}}$ لدينا :
لاحظ أن عكس مبرهنة Fermat الصغرى غير صحيح. مثال : $\displaystyle{\displaylines{7^{25} \equiv 7 [25]}}$ لكن $\displaystyle{\displaylines{25}}$ ليس أولي.
المبرهنة الأساسية للحسابيات
تنص المبرهنة الأساسية للحسابيات على أن كل عدد صحيح نسبي غير منعدم $\displaystyle{\displaylines{n}}$ يمكن كتابته بكيفية وحيدة على شكل جداء عوامل أولية.
بحيث $\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}}$.
لدينا التفكيك إلى جداء عوامل أولية للعدد : $\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{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{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)}}$ تكتب على الشكل :
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}}$.
الحل
1) لدينا $\displaystyle{\displaylines{20 \wedge 5 = 5}}$ ولدينا $\displaystyle{\displaylines{5}}$ لا تقسم $\displaystyle{\displaylines{7}}$ وبالتالي المعادلة $\displaystyle{\displaylines{(E_1)}}$ لا تقبل أي حلول.