تعریف: اگر $n$ عددی طبیعی باشد تابع فی اویلر چنین تعریف می شود:
$$\phi(n):=\begin{cases}1 & n=1 \\|A_n| & n>1 \end{cases}$$
که در آن $A_n$ مجموعۀ اعداد طبیعی و کمتر ار $n$اند که نسبت به $n$ اولند.
قضیۀ اویلر: اگر $n$ عددی طبیعی باشد و $a$ عددی صحیح که $(a,n)=1$، آنگاه $a^{ \phi (n)} \equiv 1(modn)$.
قضیۀ فرما: اگر $p$ عددی اول و $a$ عددی صحیح آنگاه $a^p \equiv a(modp)$. واضح است که اگر $(a,p)=1$ آنگاه چون $ \phi (p)=p-1$ داریم $a^{p-1} \equiv 1(modp)$. پس قضیه فرما حالتی خاص از قضیه اویلر است.
تعریف: اگر $n$ عددی طبیعی و $a$ عددی صحیح باشد که $(a,n)=1 $ به کوچکترین عدد طبیعی مانند $d$ که $a^d \equiv 1(modn)$، مرتبۀ $a$ به پیمانه $n$ گویند و می نویسیم $Ord^a_n:=d$.
توجه: بنابه اصل خوشترتیبی و قضیۀ اویلر مرتبه همیشه وجود دارد.
تعریف: اگر $n>1$ عددی طبیعی و $a$ عددی صحیح باشد که $(a,n)=1 $ و $Ord^a_n= \phi (n)$ آنگاه $a$ را ریشهای اولیه به پیمانه $n$ مینامیم.
مثلن $3$ ریشهای اولیه به پیمانه $7$ است.
تعریف: فرض کنید $n$ عددی طبیعی و $A$ مجموعهای از اعداد صحیح باشد. در این صورت $A$ را یک دستگاه کامل (مخفف) ماندهها به پیمانه $n$ گویند در صورتیکه هر عدد صحیح (که نسبت به $n$ اول است) دقیقن با یکی از اعضای $A$ به پیمانه $n$ همنهشت باشد.
با کوششی نه چندان کم می توان نشان داد که $a$ ریشهای اولیه به پیمانه $n$ است اگر و تنها اگر
{$a,a^2,...,a^{ \phi (n)}$}
یک دستگاه مخفف ماندهها به پیمانه $n$ باشد.
قضیه: اگر $a>1$ عددی طبیعی باشد آنگاه:
$$ \forall n \in N:n| \phi (a^n-1)$$
سؤال: آیا در هر پیمانهای ریشههای اولیه وجود دارند؟
جواب به این سؤال در واقع کوشش و نبوغ چندین ریاضیدان بزرگ است که:
قضیه: فقط این اعداد ریشۀ اولیه دارند: $2$، $4$، $p^k$ و $2p^k$ که در آن $p$ عددی اول و فرد و $k$ عددی طبیعی است.
اثبات این قضیه و دیگر گزارههای مربوط به ریشه در اغلب کتابهای مقدماتی نظریه اعداد پیدا میشود.
مرجع: کتاب "نظریۀ اعداد" تألیف " مریم میرزاخانی ریاضیدان فقید و رؤیا بهشتیزاده"
یاد ریاضیدان بزرگ اقلیدس، اویلر، فرما، مریم میرزاخانی و... گرامی و زنده باد.
$\Box$
