مبرهنة فيرما الصغرى

سنثبت النظرية باستخدام الاستقراء الرياضي لكل الأعداد الصحيحة الموجبة a ≥ 0. خطوة الأساس هي حينما 0 ^p ≡ 0 (mod p) صحيحة لأنها صحيحة للأعداد الصحيحة. ثم نثبتها لـa = k ومنها ننطلق لـa = k+1. ولهذه الخطوة سنحتاج إلى الاستدلال:

لأي عدد أولي p فإن

${\displaystyle (x+y)^{p}\equiv x^{p}+y^{p}{\pmod {p}}.\,}$

لبرهنة الاستدلال سنحتاج إلى تقديم نظرية ذات الحدين والتي تنص على أنه لأي عدد صحيح n

${\displaystyle (x+y)^{n}=\sum _{i=0}^{n}{n \choose i}x^{n-i}y^{i},}$

حيث المعاملات معاملات ذات الحدين
${\displaystyle {n \choose i}={\frac {n!}{i!(n-i)!}},}$

والتي يمكن كتابتها بصيغة المضروب

${\displaystyle {n \choose i}={\frac {n!}{i!(n-i)!}},}$

و حيث أن جميع المعاملات أعداد صحيحة وحين 0 < p > i فإنه لايوجد قاسم لـp في المقام، وبالتالي فإن المعامل يحتوي على قاسم p في البسط وبالتالي

${\displaystyle {p \choose i}\equiv 0{\pmod {p}},\qquad 0<i<p.}$
وهذا يقصي جميع الحدود ماعدا الحدين الأول والأخير .

لنفرض أن (k^p ≡ k (mod p و لننظر لـk+1)^p) من الاستدلال لدينا

${\displaystyle (k+1)^{p}\equiv k^{p}+1^{p}{\pmod {p}}.\,}$

وباستخدام نظرية الاستقراء لدينا (k^p ≡ k (mod p; وببساطة 1^p = 1

وبالتالي نحصل على ${\displaystyle (k+1)^{p}\equiv k+1{\pmod {p}}\,}$

وهو مانريد إثباته a = k+1. ∎

إذا كان p' عددا أوليا وكان m وn عددين صحيحين طبيعيين حيث m يوافق n بترديد p-1, فإن لكل عدد صحيح ؟ لدينا: a^m ≡ aⁿ (بترديد p). (≡ يوافق بترديد)