ფერმას მცირე თეორემა

ფერმას მცირე თეორემა არის რიცხვთა თეორიის ერთ-ერთი მარტივი თეორემა, რომლის მიხედვითაც ნებისმიერი მარტივი რიცხვისთვის $p$ და მისი თანამარტივი (ანუ ამ შემთხვევაში — არა ჯერადი) რიცხვისთვის $a$ სრულდება შემდეგი იგივეობა:

$a^{p-1}\equiv 1{\pmod {p}}$

${\pmod {p}}$ აღნიშნავს იგივეობის შესრულებას $p$ -ს მოდულით. (ანუ იგივეობის ორივე ნაწილი ერთმანეთის ტოლი არ არის. მხოლოდ მათი $p$-ზე გაყოფის ნაშთებია ტოლი). მოდულის გარეშე თეორემა შეგვიძლია შემდეგნაირად ჩამოვაყალიბოთ:

გამოსახულება $a^{p-1}-1$ იყოფა რიცხვ $p$-ზე ნებისმიერი $p$ და $a$-სთვის.

ფერმას დიდი თეორემისგან განსხვავებით ფერმას ეს თეორემა საკმაოდ მარტივი დასამტკიცებელია და როგორც წესი მათემატიკის უმაღლესი განათლების პროგრამის პირველივე კურსში შედის ხოლმე.

დამტკიცება

ფერმას მცირე თეორემის დამტკიცების უამრავი მეთოდი არსებობს. ერთ-ერთი ყველაზე ლამაზი დამტკიცება სხვადასხვა ფრად შეღებილი მძივების გადათვლით ხდება. ამ დამტკიცებისთვის არითმეტიკის გარდა თითქმის არაფრის ცოდნა არ არის საჭირო.

თუ განვიხილავთ ყველა შესაძლო $p$ რგოლიან ჯაჭვს (წრფივი), რომელიც შედგენილია $a$ სხვადასხვა ფერის ბურთულისგან (შესაძლოა ყველა ფერი არ გამოვიყენოთ ან რამდენიც გვინდა იმდენი ფერი გამოვიყენოთ $a$-დან) ასეთი ჯაჭვების რაოდენობა $a^{p}$ იქნება. გამოვრიცხოთ ჯაჭვები, რომლებიც მთლიანად ერთი ფერის რგოლებით არიან დამზადებული და დაგვრჩება $a^{p}-a$ ცალი ჯაჭვი.

ახლა განვიხილოთ იგივე რაოდენობის ფერებისგან შემდგარი მძივები (ანუ უკვე შეკრული ჯაჭვები). აქაც გამოვრიცხოთ ერთ ფერიანი მძივები. დავუშვათ გვაქვს $n$ ცალი ასეთი მძივი. თითოეული მძივი, რადგან მისი სიგრძე $p$-ს ტოლია, შეგვიძლის $p$ სხვადასხვა ადგილას გავჭრათ და ჯაჭვი მივიღოთ. თუ შევამოწვებთ ადვილი დასანახია, რომ ასეთნაირად მიღებული ყველა ჯაჭვი სხვადასხვა იქნება (რადგან ერთ-ფერიანი ჯაჭვები გამოვრიცხეთ და $a$ და $p$ თანამარტივებია). შესაბამისად სულ გვექნება:

$n\cdot p$ ცალი სხვადასხვა ჯაჭვი. ასევე ადვილი მისახვედრია, რომ ასეთი ხერხით ყველა არაერთფარი ჯაჭვის მიღებაა შესაძლებელი (თითოეული ჯაჭვი ხომ შეგვიძლია შევკრათ და მძივი მივიღოთ, შესაბამისად ამ მძივის გაჭრით იგივე ადგილას იმავე ჯაჭვს მივიღებთ). ჯაჭვების რაოდენობა კი, როგორც გვახსოვს $a^{p}-a$ -ს ტოლი იყო.

შესაბამისად გვაქვს:

$a^{p}-a=n\cdot p$

$a\cdot (a^{p-1}-1)\equiv 0{\pmod {p}}$

და რადგან $a$ $p$-ს თანამარტივია, ამიტომ შეგვიძლია $a$ გამოვრიცხოთ ამ იგივეობიდან.

ანუ:

$(a^{p-1}-1)\equiv 0{\pmod {p}}$

ეს იგივეა რისი დამტკიცებაც გვინდოდა. ანუ დამტკიცება დამთავებულია.

უფრო სტანდარტული დამტკიცება, რომელიც უფრო მეტად რიცხვთა თეორიას ემყარება და არა მძივების დატრიალების შედეგად მიღებული ჯაჭვების შედარებას, ქვემოთ არის მოცემული.

განვიხილოთ შემდეგი რიცხვთა მიმდევრობა

$a^{0}(=1),a,a^{2},a^{3},a^{4}\ldots$

უფრო სწორად დავაკვირდეთ ამ მიმდევრობის წევრების $p$-ზე გაყოფის ნაშთებს.

$b_{0}=a^{0}{\bmod {p}}(=1),\quad b_{1}=a^{1}{\bmod {p}},\quad b_{2}=a^{2}{\bmod {p}}\ldots$

თითოეულ წევრს ამ მიმდევრობიდან 0-დან $p$-მდე რაღაც მნიშვნელობა აქვს. ეს მნიშვნელობა 0 ვერ იქნება, იმიტომ რომ $a$ და $p$ თანამარტივი რიცხვებია და შესაბამისად $a$-ს ხარისხი $p$-ს ჯერადს ვერ მოგვცემს. ხოლო $p$-ზე ნაკლები იმიტომ უნდა იყოს თითოეული წევრი, რომ ჩვენ უბრალოდ $p$-ზე გაყოფის ნაშთებს განვიხილავთ. შესაბამისად ამ მიმდევრობის პირველ $p$ წევრს ($b_{0}$-დან $b_{p-1}$-ს ჩათვლით) მხოლოდ $p-1$ შესაძლო მნიშვნელობის მიღება შეუძლია და ამიტომ ერთი მნიშვნელობა მაინც აუცილებლად ორჯერ მაინც უნდა გამეორდეს.

განვიხილოთ ყველაზე მცირე ინდექსის მქონე $b_{j}$ რომლის მნიშვნელობაც ერთ-ერთი წინა $b_{i}$-ს მნიშვნელობას ემთხვევა (როგორც ავღნიშნეთ ასეთი დამთხვევა აუცილებლად უნდა მოხდეს)

$(b_{j}=b_{i})\Rightarrow (a^{j}\equiv a^{i}{\pmod {p}})$

სადაც $0\leq i<j\leq p-1$

შესაბამისად გვაქვს რომ:

$(a^{j}-a^{i}\equiv 0{\pmod {p}})\Rightarrow ((a^{j-i}-1)a^{i}\equiv 0{\pmod {p}})\Rightarrow (a^{j-i}-1)a^{i}=p\cdot k)$

რადგან $a$ $p$-ს თანამარტივია, $a^{i}$-ც $p$-ს თანამარტივი იქნება და შესაბამისაც $a^{j-1}-1$ უნდა იყოს $p$-ს ჯერადი. ეს გვაძლევს რომ:

$(a^{j-1}-1\equiv 0{\pmod {p}})\Rightarrow (a^{j-i}\equiv 1{\pmod {p}})\Rightarrow b_{j-i}=1=b_{0}$

რადგან $0<j-i\leq j$ ამიტომ $b_{j-i}$ უნდა იყოს სწორედ ის უმცირესი გამეორებული $b_{j}$. ანუ $i=0$ და $b_{j}=b_{0}$ არის პირველი მნიშვნელობის გამეორება ამ მიმდევრობაში.

ახლა დავაკვირდეთ რომ $b_{j}$ წევრის შემდეგ მთელი მიმდევრობა თავიდან მეორდება, რადგან:

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

შესაბამისად, $b_{j}$ მიმდევრობას მხოლოდ $j$ ცალი განსხვავებული წევრი გააჩნია $1$-დან $p-1$ -მდე სიმრავლეში.

განვიხილოთ $1$-დან $p-1$-მდე რიცხვთა სიმრავლის სხვა წევრები. (თუ ასეთები არ არსებობს, მაშინ $j=p-1$ და შესაბამისად თეორემა დამტკიცებულია) ეს წევრები შეგვიძლია ჯგუფებად დავყოთ შემდეგნაირად:

თუ რაიმე ნატურალური რიცხვი $i$-სთვის $xa^{i}\equiv y{\pmod {p}}$ მაშინ $x$ და $y$ ერთ ჯგუფში ჩავსვათ, თუ არა - მაშინ სხვადასხვაში. შეგვიძლია შევამოწმოთ, ასეთნაირად განმარტებული ერთ ჯგუფში მოთავსების პრინციპი ექვივალენტობის მიმართებას წარმოადგენს და შესაბამისად ასეთ ჯგუფებად დაყოფა შესაძლებელია. თითოეული ჯგუფის ზომა იმხელა იქნება, რამდენი განსხვავებული $a^{i}$ც არსებობს, ანუ $j$. ასევე შეგვიძლია შევამოწმოთ რომ ეს ჯგუფები ერთმანეთს არ გადაფარავს.

შედეგად მივიღეთ რომ $p-1$ ელემენტიანი ჯგუფი იყოფა $j$ ზომის ქვეგჯუფებად. შესაბამისად $p-1$ $j$-ს ჯერადია. ანუ $p-1=k\cdot j$

მაგრამ:

$1=a^{0}\equiv a^{j}\equiv a^{2j}\equiv \cdots \equiv a^{k\cdot j}=a^{p-1}{\pmod {p}}$

რისი დამტკიცებაც გვინდოდა

განზოგადებები

ფერმას თეორემას რამდენიმე განზოგადება აქვს. პირველი მათგან გვეუბნება რა ხდება იმ შემთხვევაში თუ მარტივი რიცხვის მაგივრად მარტივი რიცხვის ხარისხს განვიხილავთ. ასეთ შემთხვევაში, თუ $a$ $p$-ს თანამარტივია და $p^{n}$ კი - $p$ მარტივი რიცხვის რაიმე ხარისხია გვაქვს შემდეგი იგივეობა:

$a^{p^{n-1}(p-1)}\equiv 1{\pmod {p^{n}}}$

ზოგადად ნებისმიერი რიცხვი $n$-სთვის, თუ განვმარტეთ ე.წ. ეილერის მაჩვენებელი $\Phi (n)$ რომელიც უდრის $1$-დან $n$-მდე $n$-ის თანამარტივ რიცხვთა რაოდენობას. მაშინ ნებისმიერი $n$-ის თანამარტივი რიცხვი $a$-სთვის სრულდება ფერმას თეორემის შემდეგი განზოგადებული სახე, რომელსაც ეილერის თეორემა ეწოდება:

$a^{\Phi (n)}\equiv 1{\pmod {n}}$