How can I list all numbers relatively prime to X? (but less than X) Given a number X how can I find all (or most) numbers that are relatively prime to and less than X?
Ideally I'd like this function to tell me the largest relative primes first.
 A: Dirichlet came up with a (non-trivial) proof that every arithmetic progression $ax+b$ for GCD$(a,b)=1$ contains an infinite number of primes.
This means that there is no largest number $k$ such that GCD$(k,X)=1$.  Instead, we usually consider all the positive numbers relatively prime to $X$ which are less than $X$.  The count of such numbers is given by Euler's totient function.
Assuming that you wish to find such numbers $k\lt X$, note that the largest of these is always $k=X-1$ and do a GCD test on each successively smaller number.
There aren't very many short-cuts to this process, however, it is possible to reduce the number space you are considering by going through the primes in succession and finding those which divide $X$ (i.e., factoring $X$ in the process) and then automatically discarding such numbers from your GCD test.  In fact, once you have determined any particular GCD$(k,X)\gt 1$, you can use that factor to eliminate all numbers $k$ which have it.
Note that GCD$(k,X)=$GCD$(X-k,X)$ so that you need only consider the first (or last) half of the number space in order to capture all the numbers relatively prime to $X$.  Note further that all factors $d$ of $X$ which are useful in determining relative primality are $d\le \sqrt X$.
A: *

*Start with the ordered set $(1,2,3,\ldots, X-1)$

*Ignore $1$ and leave it in the set: $1$ and $X-1$ are co-prime to $X$.

*Take the next element $n$ remaining in the set (initially $2$).  If $n^2 \gt X$ then move to step 5; otherwise if $n$ divides $X$ then remove $n$ and all multiples of $n$ and $\frac{X}{n}$ and all multiples of $\frac{X}{n}$ from the set; if $n$ has not already been removed and  $n$ does not divide $X$ then that tells you that $n$ and $X-n$ are coprime to $X$.  

*Repeat step 3.

*The remaining ordered set is your solution.
You might be able to speed this sieve up slightly by restricting checking the division to prime numbers, but the time saved could be less than the time taken to program it.   
A: If the number (as you mention in a comment) is about $2^{1024},$ then the task is hopeless. At least 8.4% of the numbers below $X$ are coprime to it (for $X$ of this size), so there are well over $10^{300}$ numbers coprime to and smaller than $X$.
If every atom in the universe was a 1 THz computer that had been operating since the beginning of the universe, you'd only have time to find the first $10^{109}$ numbers. You would be further from your goal than a single electron would be from the universe.
