In de eindige verzameling \(Z_n = \{0,1,2,...,n-1\}\) kan je getallen optellen en vermenigvuldigen modulo \(n\).

Bijvoorbeeld in \(Z_{10}\): \(6 + 6 = 12 = 2\) en \(6 \times 6 = 36 = 6\).

Voor de vermenigvuldiging wordt \(0\) uitgesloten uit de eindige verzameling. De eindige verzameling \(Z_n^0 = \{1,2,...,n-1\}\) bevat dus \(n-1\) getallen. In die verzameling kan je ook machten berekenen. Omdat \(Z_n^0\) maar \(n-1\) verschillende getallen bevat zijn er maximaal \(n-1\) verschillende machten mogelijk.

Reken na:

• alle machten van \(2\) in \(Z_{10}^0\) zijn: \(2, 4, 8, 6\).

• alle machten van \(2\) in \(Z_5^0\) zijn: \(2, 4, 3, 1\), de volledige eindige verzameling \(Z_5^0\)

Een cyclische groep ¹ is een groep die kan beschreven worden door alle machten van één element \(g\). De verzameling \(Z_n^0 = \{g, g^2, g^3,...,g^{n-1}\}\) of anders geformuleerd: de \(n-1\) getallen \(g, g^2, g^3,...,g^{n-1}\) zijn allemaal verschillend in \(Z_n^0\). Het element \(g\) wordt een generator voor \(Z_n^0\) genoemd.

Opgave

Schrijf een logische functie is_generator(g, n) die nagaat of de eerste parameter g een generator is voor \(Z_{n}^0\).

Tips

• Indien \(g^k = 1\) voor een \(k\) uit het interval \([1 , n-2]\) dan is \(g^{k+1} = g\) en komt het getal \(g\) twee keer voor. Dus is \(g\) geen generator.
• Indien \(g^k\)≠\(1\) voor alle \(k\) uit het interval \([1 , n-2]\), dan moet je ook nog controleren of \(g^{n-1} = 1\) om aan te tonen dat \(g\) een generator is.
• Gebruik enkel eenvoudige bewerkingen (+/-, *, %). Dit wordt apart gecontroleerd in Dodona

Voorbeelden

>>> is_generator(2, 5)
True
>>> is_generator(2, 10)
False