ところで、ニコニコ動画で関連する解説動画シリーズ見つけたの。そこで素数を法とする原始根の存在が証明されてたの。
www.nicovideo.jp/watch/sm24708354
www.nicovideo.jp/watch/sm24802965
群とかの専門用語は使ってないから、中高生でも理解できるはずなのかしら？
でもアタシには結構ワケわからなかったからw、自分なりにまとめてみたわ。

以下、正の整数nに対して、D(n) でnの約数の集合を表すことにするわね。

補題　任意の正の整数nについて、n = ∑_{d ∈ D(n)}φ(d) が成り立つ。
証明
各 d ∈ D(n) に対して C(d) = { x ∈ {1, …, n} | gcd(x, n) = n/d } とおくと、{ C(d) | d ∈ D(n) } は {1, …, n} の分割を与えるから
n = |{1, …, n}| = ∑_{d ∈ D(n)} |C(d)|
となるわ。
C(d) の各要素を n/d で割って得られる集合 { x/(n/d) | x ∈ C(d) } を考えると、これはちょうどd以下でdと互いに素な正の整数の集合になるから、このことから |C(d)| = φ(d) がわかるわ。QED.

以下、X(d)で (Z/pZ)^× の要素の中で位数が d のものの集合を表すことにするわね。
ラグランジュの定理から、d が p−1 の約数の場合だけ考慮すればいいの。

定理　pを素数、dを p−1 の約数とすると、 |X(d)| = φ(d) となる。（したがってpの原始根が φ(p−1) 個存在する。 ）
証明
X(d) ≠ ∅ 、つまりある a ∈ X(d) が存在するとするわ。
1 ≤ k ≤ d のどのkについても、(a^k)^d = 1 なのは明らかね。（aの位数はdだから、1 ≤ i < j ≤ d なら a^i ≠ a^j ね。）
ものぐささんが解説してくれたように x^d = 1 の解は高々d個だから、このことから
X(d) ⊆ { x ∈ (Z/pZ)^× | x^d = 1 } = { a, a^2, …, a^d }
がわかるわ。
a^k の位数を r とすると r = lcm(k, d)/k = d/gcd(k, d) だから、r = d となるのはちょうど gcd(k, d) = 1 の時ね。
だから |X(d)| は、d以下でdと互いに素であるようなkの個数、つまりφ(d) になるの。
ここまでをまとめると、各 d ∈ D(p−1) について、X(d) = ∅ か |X(d)| = φ(d) ってことよ。
さて、{ X(d) | d ∈ D(p−1) } は (Z/pZ)^× の分割を与えるから、
p−1 = |(Z/pZ)^×| = ∑_{d ∈ D(p−1)} |X(d)|
となるけど、|X(d)| は 0 か φ(d) だから、補題と比べると、各 d ∈ D(p−1) について |X(d)| = φ(d) が成り立つことがわかるの。QED.