section_heading: Teoremi vezani uz primitivne korijene
paragraph_text: Dokaz. Ako <math>d \vert k</math>, recimo <math>k = d \cdot l</math>, onda je <math>a^k \equiv {(a^d)}^l \equiv 1 \pmod n </math>. Podijelimo sada <math>k</math> sa <math>d</math>, pa dobivamo <math>k = q \cdot d + r</math>, gdje je <math>0 \leq r < d.</math> Sada je <math> 1 \equiv a^k \equiv a^{qd+r} \equiv {(a^d)}^q \cdot a^r \equiv a^r \pmod n </math> pa zbog minimalnosti od <math>d</math> slijedi da je <math>r = 0</math>, tj. <math>d \vert k</math>.