Arithmetic Modulo P Why is it that arithmetic modulo p for some prime is so useful compared to composite numbers?  Is in part because for primes any number a in $a^x \mod p$ when raised to enough $x$'s will eventually generate all numbers from $0\ldots p-1$?  Is this always true?  When do we know that something will generate all numbers smaller than the value we're modding by?
 A: Mainly, it's because all the non-zero numbers modulo $p$ form a multiplicative group: you will never have $ab \equiv 0 \mod p$, unless either $a \equiv 0 \mod p$ or $b \equiv 0 \mod p$. (This is in fact the definition of a prime element in rings.) So we can even talk of the field of numbers modulo $p$.
If you take the numbers modulo a composite number $n = pq$, then you get all sort of issues like two nonzero numbers getting multiplied to be $0$ modulo $n$: for example, $12 \times 15 \equiv 0 \mod 20$.
This does not mean that we don't ever work modulo a composite number; often we need to, and do. But even then, it turns out that we can just work modulo different (powers of) primes dividing the composite number $n$, and this completely defines the structure modulo $n$: this is the Chinese remainder theorem.

To answer the other parts of your question: it is not true that for any $a \neq 0 \mod p$, the set of numbers $a^x$ leave all possible remainders modulo $p$. For example, consider $p = 7$, and $a = 2$: the powers of $2$ mod $7$ go $2, 4, 1, 2, 4, 1, \dots$, so you never get the other numbers like $3$ or $5$ in there. There will however exist some number $a$ which generates all the nonzero numbers mod $p$, this is called a primitive root mod p.
For a composite number $n$, if we pick an $a$ for which $\gcd(a, n) = d > 1$, then any power of $a$ will always be divisible by $d$, so $a^x \mod n$ will always be one of $d, 2d, \dots$. So it will not generate all the other numbers mod $n$. However, there may exist some $a$ with $\gcd(a,n) = 1$, such that the set of numbers $a^x \mod n$ will generate all the remainders that are relatively prime to $n$. Sometimes no such $a$ may exist (e.g. consider $n = 12$).
