primitive røtter

Dette innlegget har allerede blitt vist 2464 ganger!

Definisjon: n er et naturlig tall. Da er a en primitiv rot av n hvis a har orden φ(n) modulo n.

Teorem: n er et naturlig tall. a1, a2, …, aφ(n) er relativt pimiske til n og ikke større enn n. hvis a er en primitiv rot av n er tallene a1, a2, …, aφ(n) kongruente med tallene a1, a2, … aφ(n)

Korollar: n er et naturlig tall. Hvis n har en primitiv rot, så finnes det φ(φ(n)) modulo n forskjellige primitive røtter av n.

Teorem: (Langranges) p er et primtall. La f(x) = anxn + an-1xn-1 + … + a1x+ aet polynom av grad n der alle koeffisientene ai er heltall og an ikke er kongruent med 0 modulo p. Da har kongruenslikningen f(x) ≡ 0 (mod p) maksimalt n forskjellige løsninger modulo p.

 

Lemma: p er et primtall, og d er en positiv divisor av (p-1). Dersom et tall har orden d modulo p finnes det φ(d) forskjellige slike tall modulo p.

Teorem: p er et primtall, for alle positive divisorer d av (p-1) finnes det φ(d) forskjellige tall (modulo p) som har orden d modulo p.

Teorem: et primtall p har nøyaktig φ(p-1) forskjellige primitive røtter (modulo p).