ფერმას მცირე თეორემა: განსხვავება გადახედვებს შორის
[შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
ახალი გვერდი: ფერმას მცირე თეორემა არის რიცხვთა თეორიის ე... |
No edit summary |
||
ხაზი 21:
<math>b_0 = a^0 \bmod p (=1), \quad b_1 = a^1 \bmod p, \quad b_2 = a^2 \bmod p\ldots </math>
თითოეულ წევრს ამ მიმდევრობიდან 0-დან <math>p</math>-მდე რაღაც მნიშვნელობა აქვს. ეს მნიშვნელობა 0 ვერ იქნება, იმიტომ რომ <math>a</math> და <math>p</math> თანამარტივი რიცხვებია და შესაბამისად <math>a</math>-ს ხარისხი <math>p</math>-ს ჯერადს ვერ მოგვცემს. ხოლო <math>p</math>-ზე ნაკლები იმიტომ უნდა იყოს თითოეული წევრი, რომ ჩვენ უბრალოდ <math>p</math>-ზე გაყოფის ნაშთებს განვიხილავთ. შესაბამისად ამ მიმდევრობის პირველ <math>p</math> წევრს (<math>b_0</math>-დან <math>
განვიხილოთ ყველაზე მცირე ინდექსის მქონე <math>b_j</math> რომლის მნიშვნელობაც ერთ-ერთი წინა <math>b_i</math>-ს მნიშვნელობას ემთხვევა (როგორც ავღნიშნეთ ასეთი დამთხვევა აუცილებლად უნდა მოხდეს)
<math>(b_j = b_i) \Rightarrow (a^j \equiv a^i \pmod p)</math>
სადაც <math>0 \le i < j \le p - 1</math>
ხაზი 37:
<math>(a^{j-1} - 1 \equiv 0 \pmod p) \Rightarrow (a^{j-i} \equiv 1 \pmod p) \Rightarrow b_{j-i} = 1 = b_0 </math>
რადგან <math>0 < j - i \le j</math> ამიტომ <big><math>b_{j-i}</math></big> უნდა იყოს სწორედ ის უმცირესი გამეორებული <big><math>b_j</math></big>. ანუ <big><math>i = 0</math></big> და <big><math>b_j = b_0</math></big> არის პირველი მნიშვნელობის გამეორება ამ მიმდევრობაში.
ახლა დავაკვირდეთ <big><math>b_j</math></big> წევრის შემდეგ მთელი მიმდევრობა თავიდან მეორდება, რადგან:
<big><math>a^{j+l} \bmod p = a^j \cdot a^l \bmod p = (a^j \bmod p ) \cdot (a^l \bmod p ) \bmod p = b_j \cdot b_l \bmod p = 1 \cdot b_l \bmod p= b_l </math></big>
|