Finding the set {$ a\ |\ \mathrm{gcd}(a, b) = 1$}

Question

I was wondering about the method to determine the set {$ a \ |\ \mathrm{gcd}(a, b) = 1$} : what is the faster way to get it ?

I was thinking about to compute it like the sieve of Eratosthenes : test if $\mathrm{gcd}(i, b) \not= 1$, in that case we will not test numbers which are a multiple of $i$ etc ...

Can I be more effective ?

Thank you for your help :)

Answer 1

Determine the positive integers $k$ less than $b$ which are relatively prime to $b$. Then the set of equivalence classes $k$ modulo $b$ describes the set of all integers relatively prime to $k$. The equivalence class $k$ modulo $b$ is $\{k + mb : m \in \mathbb{Z}\}$. This works because $k + mb$ is relatively prime to $b$ if and only if $k$ is relatively prime to $b$.

For example, we have that the set of odd integers (i.e. the set of numbers relatively prime to $2$) is described as $\{ n \in \mathbb{Z} : n \equiv 1 \mod 2 \}$.