As you suggest, one reason why robjohn's answer got more upvotes than yours may be that he has a lot more rep, and is a familiar face to many people on math.SE. Both of these facts may cause some voters to trust his answers more, without necessarily taking the time to check them in detail, than they would trust a similar answer from an unfamiliar low-rep user.
Another reason why his answer got more upvotes than yours is that, at least to my eye, it's a lot better typeset and more readable. I can look at his answer, understand the form of the argument he's making, and verify that all the steps are correct in just a few seconds. It's nothing but one simple (and nicely laid out) chain of basic algebraic manipulations and modular equivalences, leading from the given expression to zero (modulo 19).
Your answer, meanwhile, is a dense and compact block of inline math, with two separate chains of equivalences. I've been looking at it for over a minute now, while writing this answer, and (if it weren't for the fact that a lot of other math.SE users have surely vetted it a lot more thoroughly by now) I still wouldn't be able to tell for sure whether it's correct or not. In your second chain of equivalences, especially, each step involves a bunch of non-trivial algebraic manipulation that really would benefit from being written out. Correct or not, posted early or not, I can easily see how many readers may have taken a look at your answer, seen a terse answer with a bunch of messy formulas that they can't immediately parse, and decided to ignore it since there are other, more readable and interesting answers too.
Finally, as others have noted, most readers will tend to sort answers by score, and pay most attention to the top-scored answers. Some readers may also interpret a high answer score as an indication of community trust (just as people interpret rep the same way), and thus be more inclined to upvote already high-scoring answers. For better or worse, these effects tend to create a positive feedback loop that amplifies scoring differences: the more votes an answer already has, the more votes it's likely to get.
In particular, as quid noted in the comments above, in this particular case robjohn's answer may have acquired some extra upvotes from readers who didn't like the (IMO excessively long-winded) accepted answer, and therefore chose to upvote the "leading competitor" instead. Not all of these readers necessarily took the extra time to also go over all the other answers to see if they'd deserve upvotes too — they just saw an answer they liked sorted underneath an answer they didn't like so much, and decided to upvote it.
I suspect the combination of all these effects is what led to robjohn's answer acquiring so many more upvotes than yours: the few initial voters saw a clear and well-written answer by a familiar and trusted user, and decided to upvote it, while ignoring the terse and kind of hard-to-read competing answer from a low-rep user they didn't recognize. And once robjohn's answer got enough upvotes to raise it up above yours in the default sorting order, the "snowball effect" also started working for him.
Of course, by now, the "meta effect" has also caused a lot more people to take a closer look at your answer and upvote it, since it is, after all, a correct answer to the question. Thus, your answer is now at score 16 (+13 from before you posted this meta question), while robjohn's is only at 28 (+1 from before). The other (also, presumably, equally correct) lower-voted answers still languish at 2 to 3 votes, though — because, honestly, even though all of them are valid and correct, they still don't add much to the other, more popular answers.