Ask Your Question

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

asked 2019-02-02 15:25:02 +0100

Senthil gravatar image

updated 2019-02-02 15:40:16 +0100

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

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2019-02-03 11:18:40 +0100

slelievre gravatar image

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]


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)
edit flag offensive delete link more


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

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

Thanks for the awesome answer!!!

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

answered 2019-02-02 17:55:36 +0100

Senthil gravatar image

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:
    return L;
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-02-02 15:25:02 +0100

Seen: 3,068 times

Last updated: Feb 03 '19