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.
Do seperate strings (e.g.
1\n3\n) count as valid output? – devRicher – 2016-12-27T00:37:47.547@devRicher that works, sure. – Rɪᴋᴇʀ – 2016-12-27T00:53:00.093
The intuition about there being an infinite number of numbers above n that are coprime to n feels correct to me. There are infinitely many primes, and a prime would be coprime with every number below it. Therefore, every prime greater than n (of which there are infinitely many) are also part of the coprime list. – Brian J – 2016-12-27T20:28:46.977
@BrianJ Not just that. If c and n are coprimes, c + kn and n are also coprimes, for all integers k. – Dennis – 2016-12-28T02:12:51.947
1
Fun fact: these are called totatives.
– Wojowu – 2016-12-29T15:20:01.877