Calculate all cyclic subgroups of a group under multiplication of modulo n (group theory) The task was to calculate all cyclic subgroups of a group \$ \textbf{Z} / n \textbf{Z} \$ under multiplication of modulo \$ \text{n} \$ and returning them as a list of lists. The first level has all subgroups and the secend level holds the elements of these groups.

The programm first calculates the numbers \$ \text{g} \$ that are coprimes of \$ \text{n} \$. Each element of a cyclic subgroup can than be obtained by calculating the powers of \$ \text{g} \$.

A explanation of what cyclic groups are can be found on wikipedia: Group (mathematics). 

# coding=utf-8

"""Basic usage:
$ python subgroups.py 1
[[1]]
$ python subgroups.py 7
[[1], [1, 2, 4], [1, 2, 3, 4, 5, 6], [1, 6]]
"""

import argparse
from fractions import gcd


def main():
    """Prints out the results of `calculate_subgroups()`
    """

    parser = argparse.ArgumentParser()
    parser.add_argument('modulus', type=int)
    args = parser.parse_args()

    if args.modulus &gt; 0:
        print(calculate_subgroups(args.modulus))
    else:
        print("Please enter an integer &gt; 0.")


def calculate_subgroups(modulus):
    """For a group of integers modulo n, n is called the `modulus`. With the
    modulus of a cyclic group, calculate all subgroups of Z/nZ.
    See Wikipedia for reference:
    http://en.wikipedia.org/wiki/Group_(mathematics)#Modular_arithmetic

    Basic usage:
    &gt;&gt;&gt; calculate_subgroups(1)
    [[1]]
    &gt;&gt;&gt; calculate_subgroups(4)
    [[1], [1, 3]]
    &gt;&gt;&gt; calculate_subgroups(7)
    [[1], [1, 2, 4], [1, 2, 3, 4, 5, 6], [1, 6]]
    &gt;&gt;&gt; calculate_subgroups(9)
    [[1], [1, 2, 4, 5, 7, 8], [1, 4, 7], [1, 8]]
    &gt;&gt;&gt; calculate_subgroups(18)
    [[1], [1, 5, 7, 11, 13, 17], [1, 7, 13], [1, 17]]
    """

    # All cyclic groups have the trivial subgroup [1]
    subgroups = [[1]]
    coprimes = get_coprimes(modulus)

    for i in range(1, len(coprimes)):
        # Subgroups of cyclic groups always contain 1
        potential_subgroup = [1]

        exponent = 1
        coprime_potency = pow(coprimes[i], exponent, modulus)
        while coprime_potency != 1:
            potential_subgroup.extend([coprime_potency])
            exponent += 1
            coprime_potency = pow(coprimes[i], exponent, modulus)

        potential_subgroup = sorted(potential_subgroup)

        if potential_subgroup not in sorted(subgroups):
            subgroups.append(potential_subgroup)

    return subgroups


def get_coprimes(number):
    """Returns the coprimes of a number as a list.
    Basic usage
    &gt;&gt;&gt; get_coprimes(7)
    [1, 2, 3, 4, 5, 6]
    &gt;&gt;&gt; get_coprimes(10)
    [1, 3, 7, 9]
    """

    coprimes = []

    for i in range(1, number + 1):
        if gcd(number, i) == 1:
            coprimes.extend([i])

    return coprimes


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()
Two things to consider:


pow is an overkill. To calculate the subgroup, I'd continuously multiply a power by the generator:

subgroup = [1]
power = generator
while power != 1:
    subgroup.append(power)
    power = (generator * power) % modulus


BTW, now you don't have to special case a trivial subgroup.
I would also strike out calculated powers from the list of candidate generators (that is, coprimes). This way you'd avoid recalculating the same subgroup over and over again.