Orden

Dette innlegget har allerede blitt vist 2684 ganger!

Definisjon: n er et naturlig tall, a er et heltall relativt primisk til n. Det minste naturlige tallet k slik at ak ≡ 1 (mod n) kalles ordenen til a modulo n.

Eks: 2 har orden 10 modulo 11 fordi 10 er det minste tallet 2 kan opphøyes i for å være kongruent med 1 modulo 11.
3 har orden 5 modulo 11 fordi 5 er det minste tallet 3 kan opphøyes i for å være kongruent med 1 modulo 11.

Teorem: a har orden k modulo n. Da har vi følgende:

  1. For alle naturlige tall h: ah ≡ 1 (mod n) hvis og bare hvis k h.
  2. k  φ(n)

Teorem: a har orden k modulo n. For alle naturlige tall i og j er ai ≡ aj (mod n) hvis i ≡ j (mod k)

Korollar: a har orden k modulo n. Da er a1, a2, …, ak forskjellige modulo n

Teorem: a har orden k modulo n, h er et naturlig tall. da har ah orden k/gcd(h,k) modulo n.

Korollar: a har orden k modulo n, h er et naturlig tall. da har ah også orden k modulo n hvis og bare hvis h og k er relativt primiske.