Iwas reading about group theory recently, for basic cryptography, and wanted a function for computing the set , i.e. the set of integers with greatest common divisor (gcd) with equal to , formally .

And I wanted to do it “quickly”, in a math engine, so what better place than on Wolfram’s Development Platform!

It’s not rocket science how to compute the set, but I thought this’d serve as a nice reference, with examples, to basic operations in the Wolfram Language on the Wolfram Cloud.

I needed to be able to check the gcd between numbers, this is built in as `GCD`

, example

1 2 |
in: GCD[4,6]; out: 2 |

Checking from `1..n-1`

is tedious however, where `Do`

comes in handy. `Do[ expr, { var, limit } ]`

, loops `var`

from 1 to `limit`

(inclusive), example

1 2 |
In: Do[GCD[n,6], {n,6}]; Out: // nothing's output as Do just performs the calculation. |

Time for `Print[expr]`

! Example

1 2 3 4 5 6 7 |
In: Do[Print[GCD[n,6]], {n,6}]; Out: 1 2 3 2 1 6 |

But this is badly formatted, and also it includes the check of `gcd(6,6)`

, and it has a hardcoded variable. First, into a function, example

1 2 3 |
In: f[x_] := 42 + x; f[2]; Out: 44 |

Calculates the answer to life, the universe and everything, plus `x`

, i.e. `2`

. Our function looks like, (variable factored out, removed gcd(n,n) check with g-1)

1 2 3 4 5 6 7 8 |
In: CalcSet[g_]:= Do[Print[GCD[n,g]], {n,g-1}]; CalcSet[6]; Out: 1 2 3 2 1 6 |

Still badly formatted, and actually it doesn’t output the set, just a list of tests where it prints the restult of `GCD`

; enter `If`

. `If[ expr, t, f]`

, where `t`

is evaluated if `expr`

is true, and `f`

is an optional expression, evaluated if `expr`

evaluates to false. (If no `f`

is provided, and the `If`

is used in something bigger, say a list, it’ll return `null`

). Start small:

1 2 3 4 5 6 7 |
In: If[ 1==1, Print["true"], Print["false"]]; (* prints "true" *) If[ 1==2, Print["true"], Print["false"]]; (* prints "false" *) If[ 1==2, Print["true"]];(* does nothing *) If[ 1==1, Print["true"]]; (* prints "true" *) Out: "true" "false" "true" |

Redefine function with the `If`

-condition

1 2 3 4 |
In: CalcSet[g_]:= Do[If[GCD[n,g] == 1, Print[n]], {n,g}]; CalcSet[6]; Out: 1 5 |

I love it, I can compute the set! Still it isn’t very nicely formatted; I want it in a list. So I need a list, and the `AppendTo`

function,

1 2 3 4 |
In: l = {1, 2}; AppendTo[l, 3]; Print[l]; out: {1, 2, 3} |

Putting it all together in a `()`

-clause, extracting the `Print`

I get the final code:

1 2 3 4 5 6 7 8 9 10 11 |
In: GenSet[g_]:= ( l={}; Do[If[GCD[n,g] == 1, AppendTo[l,n]], {n,g-1}]; Return[l]; ); Print[GenSet[6]]; Out: {1, 5} Print[GenSet[5]]; Out: {1, 2, 3, 4} Print[GenSet[10]]; Out: {1, 3. 7, 9} |

This could probably be optimized further by adding `1`

to the initial set, and skip the first check, like below (`Do`

with a `{ var, start, end }`

-constraint),

1 2 3 4 5 6 7 |
In: GenSetOptimized[g_]:= ( l={1}; Do[If[GCD[n,g] == 1, AppendTo[l,n]], {n,2,g-1}]; Return[l]; ); Print[GenSetOptimized[6]]; Out: {1, 5} |

But it’s not a race!!.. I wonder if this can be done with a map somehow, in a sane way. In my head it doesn’t seem faster(, or less involved!)

Also, I totally know that I’m cheating by not calculating `gcd(n,n)`

, but I made the clever observation that it’ll never be `1`

unless `n`

is `1`

(I’ll leave it up to the reader to prove this.) The function doesn’t work for generating either; suppose we’ll have to wonder for eternity what the result of this is.

Edit: lol wait, it actually does work in the optimized version, since it adds `1`

to the set initially and just skips the `Do`

-loop. I totally knew this; which is why I made the optimized version, I promise.