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?
add a comment
2 Answers
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_groupreturn Sage integers - set a default argument value in the
coprime_integersmethod of integers so thatm.coprime_integers()is equivalent tom.coprime_integers(m)
Comments
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;
Your Answer
Stats
Asked: 2019-02-02 15:25:02 +0200
Seen: 3,289 times
Last updated: Feb 03 '19
