Kongruencia, primitív gyök?

Ezt az alábbi tétellel lehet megcsinálni:

Tétel: Az m, egynél nagyobb modulusra nézve akkor és csak akkor létezik primitív gyök, ha m páratlan prímhatvány, vagy egy páratlan prímhatvány duplája, vagy 2, vagy 4.

Forrás (2. oldalon):

[link]

Két kétjegyű prím szorzata nem lehet ilyen alakú, ezért a válasz: nem.

Közben beugrott egy másik megoldás.

Ha p és q kétjegyű, különböző prímek, akkor nyilván páratlanok. Tegyük fel indirekt, hogy létezik primitív gyök modulo pq. Legyen ez a g.

Ha g primitív gyök, akkor g-nek az alábbi hatványai páronként különböző maradékot adnak pq-val osztva (felhasználva, hogy fí(pq)=(p-1)(q-1)):

g^1, g^2, ..., g^((p-1)(q-1))

Azt állítjuk, hogy g^(0,5*(p-1)(q-1))=1 (mod pq).

Ugyanis ekkor g^(0,5*(p-1)) egész szám, hiszen p páratlan, és ennek a (q-1)-edik hatványa a kis-Fermat-tétel miatt 1 maradékot ad q-val osztva.

Hasonlóan kijön, hogy g^(0,5*(p-1)(q-1))=1 (mod p).

Az előző kettőből következik, hogy g^(0,5*(p-1)(q-1))=1 (mod pq).

Viszont ekkor g^(0,5*(p-1)(q-1))=g^((p-1)(q-1))=1 (mod pq), ami ellentmond az indirekt feltevésnek .