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?
How to get list of relative primes for a given number? Is there any direct sage function?
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):
list_of_elements_of_multiplicative_group
return Sage integerscoprime_integers
method of integers
so that m.coprime_integers()
is equivalent to m.coprime_integers(m)
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;
Please start posting anonymously - your entry will be published after you log in or create a new account.
Asked: 2019-02-02 15:25:02 +0100
Seen: 3,738 times
Last updated: Feb 03 '19