اثبات رو از کتاب نظریه اعداد خانم ها رویا بهشتی زواره و مریم میرزاخانی ذکر می کنم.
فرض کنیم $p$ عددی اول و فرد باشد و
$$ \varphi (p)=q_1^{\alpha_1}q_2^{\alpha_2} \cdots q_k^{\alpha_k}$$
تجزیه $\varphi(p)$ به اعداد اول باشد. به ازای هر $1\leq i\leq k$ عددی صحیح مانند $g_i$ وجود دارد که مرتبه آن به پیمانه $p$ برابر با $q_i^{\alpha_i}$. بنا بر قضیه لاگرانژ به ازای هر $1\leq i\leq k$، معادله همنهشتی
$$ x^{\frac{p-1}{q_i}} \equiv^p 1 $$
حداکثر $\frac{p-1}{q_i}$ ریشه دارد و چون $\frac{p-1}{q_i}<p-1$، عددی صحیح مانند $x_0$ وجود دارد که
$$ x_0^{\frac{p-1}{q_i}} \equiv^p 1 $$
فرض کنید $g_i=x_0^{\frac{p-1}{q_i^{\alpha_i}}} $، $1\leq i\leq k$. ادعا می کنیم که به ازای هر $1\leq i\leq k$، مرتبه $g_i$ به پیمانه $p$ برابر با $q_i^{\alpha_i}$ است. می توان نوشت
$$g_i^{q_i^{\alpha_i}}=\bigg(x_0^{\frac{p-1}{q_i^{\alpha_i}}} \bigg)^{q_i^{\alpha_i}}=x_0^{p-1} \equiv ^p 1$$
بنابراین مرتبه $g_i$ به پیمانه $p$ مقسوم علیه ای از $ q_i^{\alpha_i} $ است ($1\leq i\leq k$). فرض کنید مرتبه $g_i$ به پیمانه $p$ برابر با $ q_i^{\beta_i} $ باشد
$\beta_i\leq \alpha_i$($1\leq i\leq k$).
اگر $\beta_i<\alpha_i$، چون
$$g_i^{q_i^{\beta_i}} \equiv ^p 1$$
پس
$$\bigg(x_0^{\frac{p-1}{q_i^{\alpha_i}}} \bigg)^{q_i^{\beta_i}}=x_0^{{\frac{p-1}{q_i^{\alpha_i-\beta_i}}}} \equiv ^p 1$$
از طرف دیگر $\alpha_i-\beta_i-1\geq 0$ و در نتیجه
$$\bigg(x_0^{{\frac{p-1}{q_i^{\alpha_i-\beta_i}}}}\bigg)^{q_i^{\alpha_i-\beta_i-1}} \equiv ^p 1$$
بنابراین
$$ x_0^{\frac{p-1}{q_i}} \equiv^p 1 $$
که با نحوه انتخاب $x_0$ تناقض دارد. بنابراین $\alpha_i=\beta_i$($1\leq i\leq k$).
یعنی مرتبه $g_i$ به پیمانه $p$ برابر با $q_i^{\alpha_i}$ است. فرض کنید
$$g=g_1g_2\cdots g_k$$
چون مرتبه $g_i$ به پیمانه $p$ برابر با $q_i^{\alpha_i}$ است ($1\leq i\leq k$) و
$$(q_i,q_j)=1, i \neq j$$
پس بنابر نتیجه ای ساده درباره مرتبه، مرتبه ی $g$ به پیمانه $p$ برابر است با $q_1^{\alpha_1}q_2^{\alpha_2} \cdots q_k^{\alpha_k}$ و یا $\varphi(p)$ است. بنابراین $g$ ریشه ای اولیه به پیمانه $p$ است.
تذکر: به نظر میرسه که بخش هایی از اثبات درست نیست و یا ایراد داره. اگه باقی دوستان هم با من هم نظر هستن که اثبات ایراد داره ذکر کنن تا اثبات رو اصلاح کنیم.
