I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're trying to store a mapping of UIDs to usernames or something like that. The naive way of doing that would be to just have an array with one entry for each possible UID so, in this case, an array of 1,000,000 strings. The advantage of that approach is that you can look up the name associated with a UID in constant time: you just write something like
username[uid] to retrieve it from the array. The problem is that in most applications, you only have maybe a few thousand users at most, so most of your array is empty and you're wasting a lot of space.
You can avoid wasting the space by, for example, storing pairs of UID and username in a linked list: now you only have one entry in the list for each user so you're much more memory-efficient. However, retrieving a username now requires a linear search through the list, as does adding a new username. Using something like a search tree would allow logarithmic look-up and insertion but that's still quite a bit slower than an array.
The point of using a hash table is that it gives you nearly constant look-up and insertion time, like an array, but it doesn't waste as much space. The idea is that, instead of storing a UID's username at
username[uid], you store it at
username[h(uid)] for some function
h which is fairly easy to compute. You choose a function with a range that is the size of the hash table you're going to use, and the point is to make this a good deal smaller than the number of possible UIDs.
However, doing this guarantees that
h will map at least two UIDs to the same slot in the hash table: this is exactly the pigeonhole principle. Unless you know in advance exaclty what data you're going to be storing, you it's impossible to guarantee that this won't happen; all you can do is try to make it unlikely and deal with the inevitable collisions when they happen.
In a comment, you ask if using a hash table with size 999,983 would work. That wouldn't be a sensible hash table, since it's almost as big as just using an array of size 1,000,000 and forgetting about hashing. In fact, it's bigger because dealing with collisions would require you to store both the UID and username for each entry in the hash table, whereas in an array, you just need to store the username.
In the question, you say
since $M$ is prime, dividing an UID with $M$ generates a unique remainder
That has nothing to do with whether or not $M$ is prime. Dividing any positive integer by any other positive integer produces a single, well-defined, unique remainder.