Coprimes up to N

Python 2, 61 47 bytes

lambda n:[k/n for k in range(n*n)if k/n*k%n==1]

Try it online!

Background

Consider the ring \$(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\$ 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.

Jelly, 4 bytes

gRỊT

Try it online!

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.

Jelly, 3 bytes

gÐṂ

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.