Generating $\mathbb{Z}^*_n$

I'm using Mathematica to illustrate basic number theory concepts in a graduate cryptography class. To generate elements of the multiplicative group of integers modulo $n$, i.e. $\mathbb{Z}^*_n$, I can use the following code:

Z[n_] := Table[If[GCD[i, n] == 1, i, ## &[]], {i, n}];

Example:

In: Z
Out: {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}

The notation ## &[] used in defining Z[n_] will certainly raise questions for students who have no prior exposure to Mathematica. Is there a simpler way of generating elements of $\mathbb{Z}^*_n$?

PS: I can use:

Z[n_] := DeleteCases[Table[If[GCD[i, n] == 1, i], {i, n}], Null];

but that's not elegant either.

• How about a Select over a simple range? – wxffles Mar 11 '15 at 23:39
• Z[n_] := Select[CoprimeQ[#, n] &]@Range[1, n] – evanb Mar 11 '15 at 23:45
• @evanb I just posted something very similar - simultaneously with your comment... – Jens Mar 11 '15 at 23:47
• Position[MultiplicativeOrder[21, #] & /@ Range@20, _?IntegerQ, 1] – Dr. belisarius Mar 12 '15 at 0:08
• Select[Range, NumericQ@MultiplicativeOrder[21, #] &] – Dr. belisarius Mar 12 '15 at 0:13

There is a simpler function instead of GCD that allows you to skip the comparison with 1: CoprimeQ. Using it, we can do this:

Z[n_] := With[{i = Range[n]}, Pick[i, CoprimeQ[i, n]]]

Z

(* ==> {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} *)

Here I deliberately tried to avoid any cryptic symbols (although perhaps that should be par for the course in a cryptography class)...

Edit speed

Considering the comment, I looked at the timings and found that my solution is also about twice as fast as the ones posted by Mr. Wizard:

AbsoluteTiming@Do[
Select[Range[n], CoprimeQ[#, n] &],
{n, 200, 3000}]

(* ==> {3.102409, Null} *)

AbsoluteTiming@Do[
Join @@ Position[Range[n]/n, _[_, n]],
{n, 200, 3000}]

(* ==> {3.367569, Null} *)

AbsoluteTiming@Do[
With[{i = Range[n]}, Pick[i, CoprimeQ[i, n]]],
{n, 200, 3000}]

(* ==> {1.692815, Null} *)

The general rule is that you get more speed if you use the listability of built-in functions, instead of doing explicit looping (or Table, or Map operations). Listability here means that you can feed a whole List into the argument of CoprimeQ, and the looping will be done at a lower level internally.

• Thanks. This is the simplest of all the suggestions. Out of curiosity, do you know which of the suggestions is the most efficient? – M.S. Dousti Mar 12 '15 at 13:00
• Without doing any testing, the general rule is that you get more speed if you use the listability of built-in functions, instead of doing explicit looping (or Table, or Map operations). Listability here means that you can feed a whole List into the argument of CoprimeQ, and the looping will be done at a lower level internally. That's why I think my solution will also be efficient: it works with lists as a whole, never breaking it up into its elements. – Jens Mar 12 '15 at 16:02
• @Sadeq And that is exactly why I prefer Jens' solution. :-) – Mr.Wizard Mar 12 '15 at 20:43
• @Mr.Wizard: Yeah, it's very elegant in that it is both the simplest (IMHO) and the most efficient! – M.S. Dousti Mar 12 '15 at 20:55

I prefer Jens' solution but here is another simple formation:

z1[n_] := Select[Range[n], CoprimeQ[#, n] &]

And one for just for fun:

z2[n_] := Join @@ Position[Range[n]/n, _[_, n]]
• That second one blew my mind a little bit! +1. – evanb Mar 12 '15 at 17:48