Alkion kertaluku (modulaariaritmetiikka)

Alkion kertaluku modulaariaritmetiikassa tarkoittaa pienintä positiivista eksponenttia, jolla potenssiinkorotuksen jakojäännökseksi tulee ykkönen tietyllä positiivisella kokonaisluvulla jaettaessa.

Olkoot $n$ ja $a$ kokonaislukuja, $n>1$ ja ${\mbox{gcd}}(a,n)=1$.

Eulerin lauseen mukaan $a^{\varphi (n)}\equiv 1$ $({\mbox{mod }}n)$. On siis olemassa sellaisia positiivisia kokonaislukuja $k$, että $a^{k}\equiv 1$ $({\mbox{mod }}n)$. Pienintä tällaista kokonaislukua $k$ sanotaan alkion $a$ kertaluvuksi modulo $n$ ja merkitään ${\mbox{ord}}_{n}(a)$.

Alkion kertaluku on aina Eulerin funktion tekijä ts. ${\mbox{ord}}_{n}(a)|\varphi (n)$. Kertaluku voidaan siis laskea, jos luvun $\varphi (n)$ tekijöihinjako tunnetaan.