How to get list of relative primes for a given number?

savecancel

There are indeed more direct ways to list integers coprime to a given integer in Sage.

One way is to build the ring of integers modulo m, then list the multiplicative group of that ring.

sage: m = 8
sage: Zmod(m).list_of_elements_of_multiplicative_group()
[1, 3, 5, 7]

Note that this returns a list of Python integers:

sage: type(Zmod(m).list_of_elements_of_multiplicative_group()[0])
<class 'int'>

To get Sage integers one would need

sage: m = 8
sage: [ZZ(k) for k in Zmod(m).list_of_elements_of_multiplicative_group()]
[1, 3, 5, 7]

Check:

sage: [ZZ(k) for k in Zmod(m).list_of_elements_of_multiplicative_group()][0].parent()
Integer Ring

Another way is to use the method coprime integers, which expects another argument to say how far you want to list integers that are coprime to m. To get them up to m - 1:

sage: m = 8
sage: m.coprime_integers(m)

To get them further:

sage: m.coprime_integers(29)  # list up to 29 (excluded)
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]

These are returned as Sage integers:

sage: m.coprime_integers(m)[0].parent()
Integer Ring

This suggests two improvements in Sage (I'll check if tickets exist, and open them if not):

• make list_of_elements_of_multiplicative_group return Sage integers
• set a default argument value in the coprime_integers method of integers so that m.coprime_integers() is equivalent to m.coprime_integers(m)