什麼叫原根？什麼樣的正整數具有原根？我來介紹一下《數學100個基本問題》中提到的這個比較有趣的概念。
假設a和m是互素的正整數，那麼對於所有a的方冪，a，a^2，a^3，…除以m後所得的餘數來說，因為餘數的可能性只有m種，因此總能找到2個不同的方冪不妨設i，j使得m整除a^i-a^j=a^i[a^(j-i)-1]。又因為a和m互素，所以m整除a^(j-i)-1。由此證明了對於任意a和m互素，就存在正整數k使得a^k≡1(mod m)。我們把這個最小的k稱作a模m的階，或者a關於m的指數。
階k應該是什麼樣子的？假設有另外一個正整數n使得a^n≡1(mod m)。我們可以令n=kq+r，其中q和r都是整數且0≤r<k，那麼有下面推導：
根據k的最小值假定，則r=0。所以k整除n，因此k是a模m的階若且唯若a^k≡1(mod m)，且對於所有a^n≡1(mod m)總有k整除n。
在我之前的關於歐拉函數的文章中有提到過關於歐拉對於費馬小定理的推廣，即當a和m為互素正整數時，總有m整除a^Φ(m)-1，其中Φ(m)為歐拉函數。有上面的推導可得，k必定整除Φ(m)，那麼有趣的問題來了，什麼時候k=Φ(m)呢？
如果a模m的階恰好等於Φ(m)，則稱a為m的一個原根。那麼什麼樣的正整數有原根，我們能否求得它的所有原根？為什麼要談論這個問題，因為對於具有原根a的正整數m而言，a的Φ(m)個方冪：a，a^2，…，a^Φ(m)除以m所得的餘數恰好是小於m且與m互素的全部正整數（因為如果餘數和m有公因子，那麼a也會有這個公因子，這與a和m互素矛盾）
並不是所有的正整數都有原根，簡單的計算可知m=8時就沒有原根。歐拉在1773年首先證明了對於所有的素數p都是有原根的。在介紹歐拉的證明前我們要先做點準備工作。首先介紹一個同餘方程解的一個性質。如果x是同餘方程f(x)≡0(mod m)的一個解，且x除以m後所得的餘數為r，即x=km+r，可得f(x)≡f(km+r)≡f(r)≡0(mod m)，即r也是同餘方程的一個解。因此我們在討論同餘方程的解的時候只討論小於m的情況。下面說一下2個重要結論。
1) 拉格朗日定理：設f(x)為n次整係數多項式，則同餘方程f(x)≡0(mod p)至多有n個解。
這是拉格朗日在1770年首先證明的。我們現在用歸納法來證明這個結論，設：
為整係數多項式，不妨設an不整除p。那麼當n=1時，一次同餘方程a1x+a0≡0(mod p)顯然只有一個解。假定該結論對於前面的n-1都成立。對於n次多項式方程f(x)≡0(mod p)無解，結論顯然成立。如果有一解r使得f(r)≡0(mod p)，那麼此時用x-r去除f(x)所得的餘式恰為f(r)，即存在g(x)滿足f(x)=(x-r)g(x)+f(r)，此時g(x)最高次項為n-1次。因此f(x)≡(x-r)g(x)(mod p)，即f(x)≡0(mod p)的全部解為r和g(x)≡0(mod p)，由於g(x)≡0(mod p)至多有n-1個解，所以f(x)≡0(mod p)至多有n個解。
2) 如果d是p-1的一個因子，則x^d≡1(mod p)恰有d個解。
由費馬小定理可知x^(p-1)≡1(mod p)恰有p-1個解1,2,3,…,p-1。而條件中d整除p-1可以得到x^d-1也整除x^(p-1)-1（因式分解），則我們可以令：
由結論1)可得，同餘方程h(x)≡0(mod p)最多有p-1-d個解，而x^(p-1)≡1(mod p)恰有p-1個解，所以x^d≡1(mod p)至少有d個解。而直接運用結論1)可得x^d≡1(mod p)至多有d個解。合併2個結論，即x^d≡1(mod p)恰有d個解。
接下來我們就來證明歐拉的這個結論。
首先考慮到1,2,3,…,p-1中的每個數模p的階都整除Φ(p)=p-1。對於p-1的每一個因子d，我們用ψ(d)表示該p-1個數中模p的階等於d的那些數的的個數。運用上面的結論2)我們可以得到：
現在比較Φ(d)和ψ(d)的大小。對於p-1的每一個因子d，如果ψ(d)=0則ψ(d)< Φ(d)。如果ψ(d)≠0，則存在一個模p的階為d的正整數，假設為a。因為階為d的數都是同餘方程x^d≡1(mod p)的解。而上面結論2)告訴我們方程恰有d個解。因為a，a^2，…，a^d模p都是1，且兩兩不同，故為上述方程全部的解，因此我們知道凡是階為d的正整數都可以寫成a的方冪。而且若a^k的階為d，則d和k互素。從而有Φ(d)個階為d的方冪即Φ(d)=ψ(d)。因此我們證明了Φ(d)≥ψ(d)。再由歐拉函數的性質，我們可以得到：
因此對於每一個d都有Φ(d)=ψ(d)。特別的Φ(p-1)=ψ(p-1)≠0，這說明存在模p的階為p-1的正整數，即p有原根。高斯在1801年證明了一個正整數有原根若且唯若它型如1,2,4,p^e,2p^e，其中p為奇素數e為正整數。
最後關於原根有個猜想在1927年由奧地利數學家阿廷提出：對於每個不等於1，p-1以及完全平方數的正整數a都存在有無窮多個素數p以a為原根。