[Question]
  [
Given a number `n >= 2`, output all the positive integers less than `n` where `gcd(n, k) == 1` (with `k` being any one of the output numbers).  Numbers of this sort are **coprime** to each other.
Example: `10` gives the output `[1, 3, 7, 9]` (in any form you like, as long as the numbers are unambiguously separated and in some sort of list). The list cannot have duplicate entries and doesn't have to be sorted.
More test cases:
```
2 -> [1]
3 -> [1, 2]
6 -> [1, 5]
10 -> [1, 3, 7, 9]
20 -> [1, 3, 7, 9, 11, 13, 17, 19]
25 -> [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24]
30 -> [1, 7, 11, 13, 17, 19, 23, 29]
```
We are also not counting numbers above `n` that are coprime to `n`, solely because I'm fairly certain there's infinite solutions.
Also note: Numbers that are coprime to each other are also said to be relatively prime or mutually prime to each other.
  
[Answer]
# [Python 2](https://docs.python.org/2/), ~~61~~ 47 bytes
```
lambda n:[k/n for k in range(n*n)if k/n*k%n==1]
```
[Try it online!](https://tio.run/nexus/python2#FYpLCoAgAAXXdYq3CTSEftQi8CTVwihDrFdI97dczGZmLDTmeJpr3Qw4Tr4i7B3g4YhgeOyCJaWz@EvpC2rdLDEdTEer0CkMCk2t0Cb639Rjnj3B8RVWUMr4AQ "Python 2 – TIO Nexus")
### Background
Consider the [ring](https://en.wikipedia.org/wiki/Ring_(mathematics)) \$(Z\_n, +\_n, \cdot\_n)\$. While this ring is usually defined using residue classes modulo \$n\$, it can also be thought of as the set \$Z\_n = \{0, \dots, n - 1\}\$, where the addition and multiplication operators are defined by \$a +\_n b = (a + b)\:\%\: n\$ and \$a \cdot\_n b = a \cdot b\:\%\: n\$, where \$+,\:\cdot\text{, and } \%\$ denote the usual addition, multiplication, and modulo operators over the integers.
Two elements \$a\$ and \$b\$ of \$Z\_n\$ are called mutual [multiplicative inverses modulo \$n\$](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) if \$a \cdot\_n b = 1\:\%\:n\$. Note that \$1\:\%\:n = 1\$ whenever \$n > 1\$.
Fix \$n > 1\$ and let \$a\$ be a coprime of \$n\$ in \$Z\_n\$. If \$a \cdot\_n x = a \cdot\_n y\$ for two elements \$x\$ and \$y\$ of \$Z\_n\$, we have that \$a \cdot x\:\%\:n = a \cdot y\:\%\:n\$. This implies that \$a \cdot (x - y)\:\%\:n = a \cdot x\:\%\:n - a \cdot y\:\%\:n = 0\$, and we follow that \$n \mid a \cdot (x - y)\$, i.e., \$n\$ divides \$a \cdot (x - y)\$ evenly. Since \$n\$ shares no prime divisors with \$a\$, this means that \$n \mid x - y\$. Finally, because \$-n < x - y < n\$, we conclude that \$x = y\$. This shows that the products \$a \cdot\_n 0, \dots, a \cdot\_n (n - 1)\$ are all different elements of \$Z\_n\$. Since \$Z\_n\$ has exactly \$n\$ elements, one (and exactly one) of those products must be equal to \$1\$, i.e., there is a *unique* \$b\$ in \$Z\_n\$ such that \$a \cdot\_n b = 1\$.
Conversely, fix \$n > 1\$ and let \$a\$ be an element of \$Z\_n\$ that is *not* coprime to \$n\$. In this case, there is a prime \$p\$ such that \$p \mid a\$ and \$p \mid n\$. If \$a\$ admitted a multiplicative inverse modulo \$n\$ (let's call it \$b\$), we'd have that \$a \cdot\_n b = 1\$, meaning that \$a \cdot b\:\%\:n = 1\$ and, therefore, \$(a \cdot b - 1)\:\%\:n = a \cdot b\:\%\:n - 1 = 0\$, so \$n \mid a \cdot b - 1\$. Since \$p \mid a\$, we follow that \$p \mid a \cdot b\$. On the other hand, since \$p \mid n\$, we also follow that \$p \mid a \cdot b - 1\$. This way, \$p \mid (a \cdot b) - (a \cdot b - 1) = 1\$, which contradicts the assumption that \$p\$ is a prime number.
This proves that the following statements are equivalent when \$n > 1\$.
* \$a\$ and \$n\$ are coprime.
* \$a\$ admits a multiplicative inverse modulo \$n\$.
* \$a\$ admits a *unique* multiplicative inverse modulo \$n\$.
### How it works
For each pair of integers \$a\$ and \$b\$ in \$Z\_n\$, the integer \$k := a \cdot n + b\$ is unique; in fact, \$a\$ and \$b\$ are quotient and remainder of \$k\$ divided by \$n\$, i.e., given \$k\$, we can recover \$a = k/n\$ and \$b = k\:\%\: n\$, where \$/\$ denotes *integer* division. Finally, since \$a ≤ n - 1\$ and \$b ≤ n - 1\$, \$k\$ is an element of \$Z\_{n^2}\$; in fact, \$k ≤ (n - 1) \cdot n + (n - 1) = n^2 - 1\$.
As noted above, if \$a\$ and \$n\$ are coprime, there will be a unique \$b\$ such that \$a \cdot b\:\%\:n = 1\$, i.e., there will be a unique \$k\$ such that \$k / n = a\$ and \$k / n \cdot k\:\%\:n = (k / n) \cdot (k\:\%\:n)\:\%\:n = 1\$, so the generated list will contain \$a\$ exactly once.
Conversely, if \$a\$ and \$n\$ are *not* coprime, the condition \$k / n \cdot k\:\%\:n = 1\$ will be false for all values of \$k\$ such that \$a = k / n\$, so the generated list will *not* contain \$a\$.
This proves that the list the *lambda* returns will contain all of \$n\$'s coprimes in \$Z\_n\$ exactly once.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 4 bytes
```
gRỊT
```
[Try it online!](https://tio.run/nexus/jelly#@58e9HB3V8j/w@2Pmta4//9vqKNgpKNgrKNgpqNgaADkgLApUMQAAA "Jelly – TIO Nexus")
### How it works
```
gRỊT  Main link. Argument: n
 R    Range; yield [1, ..., n].
g     Compute the GCD of n and each k in [1, ..., n].
  Ị   Insignificant; return 1 for GCDs less or equal to 1.
   T  Truth; yield the indices of all truthy elements.
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 3 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
gÐṂ
```
[Try it online!](https://tio.run/##y0rNyan8/z/98ISHO5v@H25/1LTG/f//aCMdBWMdBTMdBUMDHQUjEDYFihjEAgA "Jelly – Try It Online")
# How does this work?
```
gÐṂ  - (Monadic) Full program.
g    - Greatest common divisor.
 ÐṂ  - Keep the elements with minimum link value (i.e. those with GCD == 1)
       Note that this automatically creates the range [1, input] (inclusive).
```
## Proof of validity
Since we want to extract the coprimes only, the minimum value of the Greatest-Common-Divisors list *has* to be **1** for the `ÐṂ` trick to work. Let's prove that (in two different methods):
1. The implicitly generated range, \$[1, \text{input}]\$ contains \$1\$ and \$\gcd(1, x) = 1\:\:\forall\:\:x \in \mathbb{Z}^{\*}\$. The greatest common divisor is always a strictly positive integer, hence \$1\$ is guaranteed to occur and will always be the minimum value.
2. Two consecutive positive integers are always coprime. Consider \$x, y \in \mathbb{Z}^{\*}\$, with \$y = x + 1\$. Then we take another positive integer \$k\$ such that \$k \mid x\$ and \$k \mid y\$.
This implies that \$k \mid (y - x)\$, so \$k \mid (x + 1 - x)\$, thus \$k \mid 1\$. The only positive integer to divide \$1\$ is \$1\$ itself, so it is guaranteed to appear in the list and will always be the minimum value.
[Answer]
## Mathematica, 25 bytes
```
Range@#~GCD~#~Position~1&
```
Slightly weird output format, where each result is wrapped in a separate list, e.g. `{{1}, {3}, {7}, {9}}`. If that's not okay, I've got two solutions at 30 bytes:
```
Select[Range[x=#],#~GCD~x<2&]&
#&@@@Range@#~GCD~#~Position~1&
```
Mathematica actually has `CoprimeQ` but that's way too long.
[Answer]
# [2sable](https://github.com/Adriandmen/2sable), 4 bytes
Code:
```
ƒN¿–
```
Explanation:
```
ƒ       # For N in the range [0, input]..
 N¿     #   Compute the GCD of N and the input
   –    #   If 1, print N with a newline
```
Uses the **CP-1252** encoding. [Try it online!](https://tio.run/nexus/2sable#@39skt@h/Y8aJv//b2wAAA "2sable – TIO Nexus")
[Answer]
# Python, ~~93~~ ~~82~~ 74 bytes
```
f=lambda a,b:f(b,a%b)if b else a<2
lambda c:[i for i in range(c)if f(i,c)]
```
`f` recursively checks for coprimes, and the second lambda generates them. Outputs a list.
[Answer]
# [Actually](https://github.com/Mego/Seriously), 8 bytes
```
;╗R`╜┤`░
```
[Try it online!](https://tio.run/nexus/actually#ARUA6v//O@KVl1Jg4pWc4pSkYOKWkf//MTA "Actually – TIO Nexus")
Explanation:
```
;╗R`╜┤`░
  R`  `░  elements of range(1, n+1) where
;╗  ╜     n and the element
     ┤    are coprime
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 7 bytes
```
:GZd1=f
```
[Try it online!](https://tio.run/nexus/matl#@2/lHpViaJv2/7@RAQA "MATL – TIO Nexus")
[Answer]
# MATLAB/Octave, 22 bytes
```
@(n)find(gcd(1:n,n)<2)
```
[Try it online!](https://tio.run/nexus/octave#@@@gkaeZlpmXopGenKJhaJWnk6dpY6T5PzGvWMPIQPM/AA "Octave – TIO Nexus")
[Answer]
# JavaScript (ES6), ~~64~~ 61 bytes
*Saved 3 bytes thanks to @user81655*
```
n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
```
### Test snippet
```
f=n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
for(var i = 2; i < 50; i++) console.log(i + ":", `[${ f(i) }]`);
```
[Answer]
## [Jellyfish](https://github.com/iatorm/jellyfish), ~~19~~ 18 bytes
```
p
[#
`B
&~xr1
NnEi
```
This works by computing the prime factorization of every number in the range and checking whether it intersects that of the input (Jellyfish doesn't have a gcd builtin yet).
For golfing reasons, the output is in descending order.
[Try it online!](https://tio.run/nexus/jellyfish#@1/AFa3MleDEpVZXUWTI5Zfnmvn/v5EBAA "Jellyfish – TIO Nexus")
## Explanation
First off, `i` is evaluated input; for input `10`, the value of the `i`-cell is `10`.
```
r1
i
```
Here `r` (range) is applied to the input and 1.
Because the input is greater than 1, the range is in descending order; for input `10`, this gives `[9 8 7 6 5 4 3 2 1]`.
```
[#
`B
&~x
Nn
```
This part is one big function, which is evaluated on `i` and the above range.
```
~x
n
```
Intersection (`n`) of prime factors (`x`).
```
&~x
Nn
```
Is it empty? (`N`)
```
`
&~x
Nn
```
Thread to level 0, testing for each element of the range.
```
[#
`B
&~x
Nn
```
Filter (`#`) the range with respect to this list of booleans.
The function produced by `[` wants to use the argument to `#` as its own argument, so we put a `B` to block `#` from getting any arguments.
Otherwise, the value of the `~`-cell would be used as the argument of the big function.
Finally, `p` prints the result.
[Answer]
# Stacked, noncompeting, ~~24~~ 21 bytes
Saved 3 bytes, inspired by [Borsunho's ruby](https://codegolf.stackexchange.com/a/104675/31957). (`1 eq` to `2<`)
```
{!n:>1+:n gcd 2<keep}
```
[Try it here!](https://conorobrien-foxx.github.io/stacked/stacked.html)
This is an n-lambda that takes a single argument and yields the array.
```
{!n:>1+:n gcd 2<keep}
{!                  }  n-lambda
  n                    push n
   :>                  range [0, n)
     1+                range [1, n]
       :               duplicate
        n gcd          element-wise gcd with n
              2<       element-wise equality with 1
                       this yields the range [1, n] and a boolean mask of coprime numbers
                keep   then, we simply apply the mask to the range and keep coprimes.
```
[Answer]
## [CJam](https://sourceforge.net/p/cjam), 14 bytes
```
{:X{Xmff%:*},}
```
[Try it online!](https://tio.run/nexus/cjam#izZSMFYwUTBVMFMwNFAwAiJTBWOD2P/VVhHVEblpaapWWrU6tf9VrQr@AwA "CJam – TIO Nexus")
### Explanation
We don't need to check all possible divisors of `a` and `b` to test whether they're coprime. It's sufficient to look at whether any of the prime factors of `b` divides `a`.
```
:X     e# Store the input in X.
{      e# Filter the list [0 1 ... X-1] by the results of this block...
  Xmf  e#   Get the prime factors of X.
  f%   e#   Take the current value modulo each of those prime factors.
  :*   e#   Multiply the results. Iff any of them divide the current
       e#   value, there's a 0 in the list, and the result of the product
       e#   is also 0, dropping the value from the resulting list.
},
```
[Answer]
# Mathematica, 26 bytes
```
Pick[r=Range@#,r~GCD~#,1]&
```
[Answer]
# [Perl 6](http://perl6.org), 20 bytes
```
{grep 2>* gcd$_,^$_}
```
[Answer]
# [Julia 0.5](http://julialang.org/), 23 bytes
```
!n=1÷gcd.(1:n,n)|>find
```
[Try it online!](https://tio.run/nexus/julia5#@6@YZ2t4eHt6coqehqFVnk6eZo1dWmZeyv@0/CKFPIXMPAUNIx0FYx0FMx0FQwMdBSMQNgWKGGhycToUFGXmlaRpKKkapSjo2imoFsfkKeko5OkoKOZpcqUCTQEA "Julia 0.5 – TIO Nexus")
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), ~~16~~ 13 bytes
```
>.$p'(e:A*?),
```
This is a function that takes *N* as input, and [generates](https://codegolf.meta.stackexchange.com/a/10753/62131) all integers less than and coprime to it.
[Try it online!](https://tio.run/nexus/brachylog#@29VbaenUqCukWrlqGWvqVObVv7/v7EBAA "Brachylog – TIO Nexus") As is often the case in Brachylog, this has had extra code added to make the function into a full program; Brachylog's interpreter, if given a function rather than a full program, will run it but not print the output, which means you can't really observe its workings.
Explanation:
A Brachylog program is a chain of constraints; typically, the LHS of one constraint is the RHS of the next.
```
>.$p'(e:A*?),
>              The input is greater than
 .             the output, whose
  $p           prime factorisation does
    '(     )   not obey the following constraint:
      e        it has an element which
       :A*     can be multiplied by something to
          ?    produce the input.
            ,  (This comma turns off an unwanted implicit constraint.)
```
Golfed down three characters by realising there's no reason to check to see if the common factor (which is already known to be a prime factor of the output) is a *prime* factor of the input. We already know it's prime, so we can just check if it's a factor. I'm pleasantly surprised here that `:A*?` doesn't send the interpreter into an infinite loop *and* doesn't allow a non-integer value for *A*, but as the interpreter does what I want, I'll take it.
[Answer]
# Dyalog APL, 10 [bytes](http://meta.codegolf.stackexchange.com/questions/9428/when-can-apl-characters-be-counted-as-1-byte-each/9429#9429).
```
0~⍨⍳×1=⊢∨⍳
```
Explanation (input `n`):
```
0~⍨⍳×1=⊢∨⍳
         ⍳ - 1 ... n (Thus, ⎕IO is 1)
       ⊢∨  - Each GCD'd by n
     1=    - Test equality with 1 on each element
   ⍳×      - multiplied by its index
0~⍨        - without 0.
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt/) `-f`, ~~9~~ ~~8~~ ~~5~~ 2 bytes
```
jN
```
[Try it](https://ethproductions.github.io/japt/?v=1.4.6&code=ak4=&input=ODgKLWY=)
* 2 bytes saved thanks to [ETH](https://codegolf.stackexchange.com/users/42545/ethproductions) pointing out a brainfart, which led to another byte saved.
[Answer]
# Mathematica, 33 bytes
```
xSelect[Range@x,x~CoprimeQ~#&]
```
Contains U+F4A1
[Answer]
# Haskell, 27 bytes
```
f n=[k|k<-[1..n],gcd n k<2]
```
[Try it online!](https://tio.run/nexus/haskell#@5@mkGcbnV2TbaMbbainlxerk56copCnkG1jFPs/NzEzT8FWoaC0JLikyCdPpTgjv1xFIU3ByOA/AA "Haskell – TIO Nexus")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 3 bytes
```
Lʒ¿
```
[Try it online!](https://tio.run/##MzBNTDJM/f/f59SkQ/v//zc2AAA "05AB1E – Try It Online")
Has new features.
[Answer]
# [memes](https://github.com/ineternet/memes), 11 bytes
Uses UTF-8 encoding.
```
d`}}]i=1?ip
```
Explanation:
```
d     Set program to not output result
`}    Loop next input-times
}]i   GCD of input and loop index
=1?   Is it equal to 1? If yes,
ip    Print out loop index
```
`}` accesses the next input item, but last input is looped through when given, so inputting `6` will result as `6 6 6 6 6 ...` in STDIN, making it possible for reading two outputs from one.
[Answer]
# Ruby, ~~36~~34
```
->n{n.times{|i|p i if i.gcd(n)<2}}
```
Admittedly, this isn`t a very *inspired* answer.
2 bytes saved thanks to Conor O'Brien.
[Answer]
# [Python 3](https://docs.python.org/3/), 60 bytes
Imports gcd instead of writing a new lambda for it. Golfing suggestions welcome. [Try it online!](https://tio.run/nexus/python3#@5@ZW5BfVKKQm1iSwVVhm5OYm5SSqJBsFZ2pkJZfpJCpkJmnUJSYl56qkayZmQZWppeenKKRrJOpaWMUy1VQlJlXolGhYWigqfn/PwA "Python 3 – TIO Nexus")
```
import math
lambda c:[i for i in range(c)if math.gcd(c,i)<2]
```
[Answer]
# Julia, 30 bytes
```
n->filter(x->(gcd(n,x)<2),1:n)
```
Anonymous function. `filter` removes elements from a list that aren't truthy according to a function.
In this case, the function is `x->(gcd(n,x)<2)` (true if the gcd of the input and the list element is less than 2). The list is the range `1:n`.
[Answer]
# [PARI/GP](http://pari.math.u-bordeaux.fr/), 27 bytes
```
n->[k|k<-[1..n],gcd(k,n)<2]
```
This uses the set-notation introduced in version 2.6.0 (2013). In earlier versions, four more bytes were needed:
```
n->select(k->gcd(k,n)<2,[1..n])
```
would be needed.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 4 bytes
```
GN¿–
```
[Try it online!](https://tio.run/##MzBNTDJM/f/f3e/Q/kcNk///NzYAAA "05AB1E – Try It Online")
How it works
```
     # implicit input
G    # for N in range(1..input)
 N   # push N
  ¿  # gcd(input, N)
   – # if 1, print N
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 54 bytes
```
k;f(n){for(k=0;++k/n<n;k/n*k%n-1||printf("%u ",k/n));}
```
This is a port of [my Python answer](https://codegolf.stackexchange.com/a/104681/12012).
[Try it online!](https://tio.run/##PU3RCsIwDHxuvyIMBu3a4TbRB@O@RH2QQWWUxTK2p63fXlNQH5LL3SW5oX4NQ0oenSK9ufesfN@gMf5AV0LulS@pbvc9zCMtThXlCoVlXWuMiSWYniMpLTcpMltuD@hhg87C0cLZQttY6HKdWGFsIKKUgpNA5YMq8P6CjAjBGC0FfxL/tG69cB67Gll26jv8/DsVmUcZ0wc "C (gcc) – Try It Online")
[Answer]
# [Whispers v2](https://github.com/cairdcoinheringaahing/Whispers), 65 bytes
```
> Input
> 1
>> (1]
>> L⊓1
>> L=2
>> Select∘ 4 5 3
>> Output 6
```
[Try it online!](https://tio.run/##K8/ILC5ILSo2@v/fTsEzr6C0hMtOwZDLzk5BwzAWRPk86poM5vvYGoGo4NSc1OSSRx0zFEwUTBWMQUL@pSVAfQpm//8bGwAA "Whispers v2 – Try It Online")
Uses the [recently implemented](https://github.com/cairdcoinheringaahing/Whispers/commit/36e87fb697076db347602b521b30b054471a9991) `Select∘` command.
## How it works
The entire program is built from lines **4**, **5** and **6**
```
>> L⊓1
>> L=2
>> Select∘ 4 5 3
```
This is the first use of any of the three `Select` statements, this time using the `Select∘` statement. All forms of the `Select` statements take **n** line references as arguments. The last number references the array to select from (let's say \$A\$), and the others reference the functions to iterate over that array (i.e the array of functions, \$B\$). However, they differ as follows:
* `Select∧` - Only select elements which are truthy under all functions in \$B\$:
$$R := [x \in A \: | \: f(x) \top, \forall f \in B]$$
* `Select∨` - Only select elements which are truthy under any function in \$B\$
$$R := [x \in A \: | \: f(x) \top, \exists f \in B]$$
* `Select∘` - Only select elements which, when all functions in \$B\$ are [composed](https://en.wikipedia.org/wiki/Function_composition) together, are truthy under this new function:
$$\text{Let }B := [f(x), g(x), h(x)]$$
$$R := [x \in A \: | \: h(g(f(x))) \: \top]$$
In this program, we can define \$A := [1, 2, ..., \alpha-1, \alpha]\$, where \$\alpha\$ is the input. We then define line **4** (`>> L⊓1`) as \$f(x) = \gcd(x, \alpha)\$ and line **5** (`>> L=2`) as \$g(x) := (x = 1)\$. Finally, we can define \$B = [f(x), g(x)]\$. This sets us up for the select statement as shown above.
When we encounter the `Select∘` statement, we take \$R\$ (the final array) as defined by the third relationship above. To make things slightly easer, we'll define 
\begin{align}
h(x) & := g(f(x)) \\
 & := gcd(x, \alpha) = 1
\end{align}
\$R\$ is then equal to the array where \$\forall x \in R\$, \$h(x) \: \top\$. Finally, on the last line, we output \$R\$.
### Shorter version, 56 bytes
```
> Input
> 1
>> (1]
>> L⟂1
>> Select∘ 4 3
>> Output 5
```
[Try it online!](https://tio.run/##K8/ILC5ILSo2@v/fTsEzr6C0hMtOwZDLzk5BwzAWRPk8mt8E5gen5qQmlzzqmKFgomAMEvAvLQEqVzD9/9/YAAA "Whispers v2 – Try It Online")
This is much less interesting as it uses the [co-prime builtin](https://github.com/cairdcoinheringaahing/Whispers/blob/master/whispers.py#L507). In this case, any of the three select statements can be used.
]