اختبار لوكاس-ليهمر لأولية عدد ما

هذا المقال يتعلق باختبار لوكاس-ليهمر الذي ينطبق على أعداد ميرسين فقط. من أجل اختبار لوكاس-ليهمر الذي ينطبق على عدد طبيعي ما أيا كان، المرجو النظر إلى اختبار لوكاس لأولية عدد ما. من أجل اختبار لوكاس-ليهمر-غيزل، المرجو النظر إلى اختبار لوكاس-ليهمر-غيزل.

في الرياضيات، اختبار لوكاس ليهمر هو اختبار أولية أعداد ميرسين.[1] اخترع هذا الاختبار من طرف إدوارد لوكاس عام 1856، فطوره لوكاس نفسه عام 1878، كما طوره أيضا ديريك هنري ليهمر في ثلاثينات القرن العشرين.

أمثلة

عدد ميرسن M₃ = 2³−1 = 7 أولي. اختبار لوكاس-ليهمر يتحقق من ذلك كما يلي. بدايةً، تُعطى القيمة 4 للمتغير s. وبعد ذلك تُغير قيمته. 3−2 = 1 مرةً:

s ← ((4 × 4) − 2) mod 7 = 0.

بما أن القيمة النهائية ل s هي الصفر، فإن الاستنتاج هو أن M₃ أولي.

من ناحية أخرى، M₁₁ = 2047 = 23 × 89 عدد غير أولي. مجددا، تُعطى القيمة أربعة ل s. ولكن قيمته تُبدل 11−2 = 9 مرةً :

s ← ((4 × 4) − 2) mod 2047 = 14
s ← ((14 × 14) − 2) mod 2047 = 194
s ← ((194 × 194) − 2) mod 2047 = 788
s ← ((788 × 788) − 2) mod 2047 = 701
s ← ((701 × 701) − 2) mod 2047 = 119
s ← ((119 × 119) − 2) mod 2047 = 1877
s ← ((1877 × 1877) − 2) mod 2047 = 240
s ← ((240 × 240) − 2) mod 2047 = 282
s ← ((282 × 282) − 2) mod 2047 = 1736

بما أن القيمة النهائية ل s لا تساوي الصفر، الاستنتاج هو M₁₁ = 2047 عدد ليس بأولي. رغم أن M₁₁ = 2047 لا يملك معاملات بديهية، اختبار لوكاس-ليهمر لا يعطي أي إشارة إلى قيمة هذه العوامل.

البرهان على الصحة

برهان الصحة المقدم هنا أبسط من البرهان الأصلي الذي جاء به ليهمر. تذكر التعريف

s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}

الهدف هو البرهان على أن M_p أولي إذا وفقط إذا توفر $s_{p-2}\equiv 0{\pmod {M_{p}}}.$

المتتالية ${\langle }s_{i}{\rangle }$ معرفة بعلاقة استدعاء ذاتي يمكن تعريفها بتعبير منغلق الشكل. ليكن $\omega =2+{\sqrt {3}}$ و ${\bar {\omega }}=2-{\sqrt {3}}$ . يأتي من ذلك باستعمال البرهان بالترجح ما يلي: أن $s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}$ لجميع قيم i:

s_{0}=\omega ^{2^{0}}+{\bar {\omega }}^{2^{0}}=\left(2+{\sqrt {3}}\right)+\left(2-{\sqrt {3}}\right)=4

و

{\begin{aligned}s_{n}&=s_{n-1}^{2}-2\\&=\left(\omega ^{2^{n-1}}+{\bar {\omega }}^{2^{n-1}}\right)^{2}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}+2(\omega {\bar {\omega }})^{2^{n-1}}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}.\end{aligned}}

المرحلة الأخيرة تستعمل $\omega {\bar {\omega }}=\left(2+{\sqrt {3}}\right)\left(2-{\sqrt {3}}\right)=1.$ هذه الصيغة المغلقة مستعملة في كل من البرهان على كونه كافيا وفي البرهان على كونه ضروريا.

كونه كافيا

الهدف هو البرهان على أن $s_{p-2}\equiv 0{\pmod {M_{p}}}$ تؤدي إلى $M_{p}$ أوليا. What follows is a straightforward proof exploiting elementary نظرية الزمر given by J. W. Bruce[2] as related by Jason Wojciechowski.[3]

افترض أن $s_{p-2}\equiv 0{\pmod {M_{p}}}.$ إذن،

\omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}

for some integer k, إذن،

\omega ^{2^{p-2}}=kM_{p}-{\bar {\omega }}^{2^{p-2}}.

Multiplying by $\omega ^{2^{p-2}}$ يعطي :

\left(\omega ^{2^{p-2}}\right)^{2}=kM_{p}\omega ^{2^{p-2}}-(\omega {\bar {\omega }})^{2^{p-2}}.

إذن،

\omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad (1)

For a contradiction, suppose M_p is composite, and let q be the smallest prime factor of M_p. Mersenne numbers are odd, إذن، q > 2. Informally,[note 1] let $\mathbb {Z} _{q}$ be the integers modulo q, and let $X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.$ Multiplication in $X$ is defined as

\left(a+{\sqrt {3}}b\right)\left(c+{\sqrt {3}}d\right)=[(ac+3bd)\,{\bmod {\,}}q]+{\sqrt {3}}[(ad+bc)\,{\bmod {\,}}q].

Clearly, this multiplication is closed, i.e. the product of numbers from X is itself in X. The size of X is denoted by $|X|.$

Since q > 2, it follows that $\omega$ and ${\bar {\omega }}$ are in X.[note 2] The subset of elements in X with inverses forms a group, which is denoted by X* and has size $|X^{*}|.$ One element in X that does not have an inverse is 0, إذن، $|X^{*}|\leq |X|-1=q^{2}-1.$

Now $M_{p}\equiv 0{\pmod {q}}$ and $\omega \in X$ , إذن،

kM_{p}\omega ^{2^{p-2}}=0

in X. إذن، by equation (1),

\omega ^{2^{p-1}}=-1

in X, and squaring both sides gives

\omega ^{2^{p}}=1.

إذن، $\omega$ lies in X* and has inverse $\omega ^{2^{p}-1}.$ Furthermore, the رتبة of $\omega$ divides $2^{p}.$ However $\omega ^{2^{p-1}}\neq 1$ , إذن، الرتبة لا تقسم $2^{p-1}.$ إذن، the order is exactly $2^{p}.$

رتبة عنصر في زمرة تساوي على الأكثر عدد عانصر تلك الزمرة. إذن،

2^{p}\leq |X^{*}|\leq q^{2}-1<q^{2}.

ولكن q هو أصغر عامل أولي من بين الأعداد الأولية اللائي يشكلن تفكيك $M_{p}$ إلى جداء عوامل أولية. إذن،

q^{2}\leq M_{p}=2^{p}-1.

هذا يؤدي إلى التناقض $2^{p}<2^{p}-1$ . إذن, $M_{p}$ أولي.

تطبيقات

يستعمل اختبار لوكاس-ليهمر لأولية عدد ما البحث الكبير عن أعداد ميرسين الأولية في الإنترنت.

انظر أيضا

البحث الكبير عن أعداد ميرسين الأولية في الإنترنت.

مراجع

"معلومات عن اختبار لوكاس-ليهمر لأولية عدد ما على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 16 يوليو 2019. الوسيط |CitationClass= تم تجاهله (مساعدة)
Bruce, J. W. (1993). "A Really Trivial Proof of the Lucas–Lehmer Test". The American Mathematical Monthly. 100 (4): 370–371. doi:10.2307/2324959. الوسيط |CitationClass= تم تجاهله (مساعدة)
Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.

وصلات خارجية

بوابة رياضيات
بوابة نظرية الأعداد

Formally, let $\mathbb {Z} _{q}=\mathbb {Z} /q\mathbb {Z}$ and $X=\mathbb {Z} _{q}[T]/\langle T^{2}-3\rangle$ .
Formally, $\omega +\langle T^{2}-3\rangle$ and ${\bar {\omega }}+\langle T^{2}-3\rangle$ are in X. By abuse of language $\omega$ and ${\bar {\omega }}$ are identified with their images in X under the natural ring homomorphism from $\mathbb {Z} [{\sqrt {3}}]$ to X which sends ${\sqrt {3}}$ to T.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] "معلومات عن اختبار لوكاس-ليهمر لأولية عدد ما على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 16 يوليو 2019. الوسيط |CitationClass= تم تجاهله (مساعدة)

[2] Bruce, J. W. (1993). "A Really Trivial Proof of the Lucas–Lehmer Test". The American Mathematical Monthly. 100 (4): 370–371. doi:10.2307/2324959. الوسيط |CitationClass= تم تجاهله (مساعدة)

[3] Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.

[4] Formally, let $\mathbb {Z} _{q}=\mathbb {Z} /q\mathbb {Z}$ and $X=\mathbb {Z} _{q}[T]/\langle T^{2}-3\rangle$ .

[5] Formally, $\omega +\langle T^{2}-3\rangle$ and ${\bar {\omega }}+\langle T^{2}-3\rangle$ are in X. By abuse of language $\omega$ and ${\bar {\omega }}$ are identified with their images in X under the natural ring homomorphism from $\mathbb {Z} [{\sqrt {3}}]$ to X which sends ${\sqrt {3}}$ to T.