I don't agree with you that traditional math is extremely effective in predicting the physical world. It is in fact very bad at predicting anything that isn't an extremely isolated situation. It's -theoretically- very good at predicting the physical world, but by the same token, you can -theoretically- use fourier transforms of aperiodic waves instead of trigonometric functions.
And mathematical systems exist without -any- concept of quantity. Set theory and category theory, for example, both exist without an internal representation of quantity.
To say, based on that we've had success with our particular brand of mathematics, that we should expect similar mathematical systems in use by aliens - why, this is to ignore entirely the implications of the UTM Theorem. There are an infinite number of analogous mathematical systems with analogous predictive powers.
Eliezer's post How To Convince Me That 2 + 2 = 3 has an interesting consideration - if putting two sheep in a field, and putting two more sheep in a field, resulted in three sheep being in the field, would arithmetic hold that two plus two equals three?
I want to introduce another question. What exactly are you counting?
Imagine one sheep in one field, and another sheep in another. Now put them together. Do you now have two sheep?
"Of course!"
Ah, but is that -all- you have?
"What?"
Two sheep are more than twice as complex as a single sheep. It takes more than twice as many bits to describe two sheep than it takes to describe a single sheep, because, in addition to those two sheep, you now also have to describe their relationship to one another.
Or, to phrase it slightly differently, does 1+1=2?
Well, the answer is, it depends on what you're counting.
If you're counting the number of discrete sheep, 1+1=2. However, why is the number of discrete sheep meaningful?
If you're a hunter counting, not herded sheep, but prey - two sheep is, roughly, twice as much meat as one sheep. 1+1=2. If you're a herder, however, two sheep could be a lot more valuable than one - two sheep can turn into three sheep, if one is female and one is male. The value of two sheep can be more than twice the value of a single sheep. And if you're a hypercomputer running Solomonoff Induction to try to describe sheep positional vectors, two sheep will have a different complexity than twice the complexity of a single sheep.
Which is not to say that one plus one does not equal two. It is, however, to say that one plus one may not be meaningful as a concept outside a very limited domain.
Would an alien intelligence have arrived at arithmetic? Depends on what it counts. Is arithmetic correct?
Well, does a set of two sheep contain only two sheep, or does it also contain their interactions? Depends on your problem domain; 1+1 might just equal 2+i.