Alkion kertaluku (modulaariaritmetiikka)

Malline:LähteetönAlkion 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 $\text{gcd}(a,n)=1$.

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

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