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

How to get list of relative primes for a given number? Is there any direct sage function?

edit retag close merge delete

Sort by ยป oldest newest most voted

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)
more

It turns out list_of_elements_of_multiplicative_group returns Python integers on purpose, for speed.

( 2019-02-03 12:42:20 +0100 )edit

( 2019-02-05 07:00:01 +0100 )edit

This is my custom function to get list of relative primes

def getRelativePrimeList(n):
L = [];
for i in range(1,n):
if gcd(i,n)==1:
L.append(i);
return L;

more

## Stats

Seen: 3,068 times

Last updated: Feb 03 '19