Why does GPS depend on relativity?

The effect of gravitational time dilation can even be measured if you go from the surface of the earth to an orbit around the earth. Therefore, as GPS satellites measure the time it's messages take to reach you and come back, it is important to account for the real time that the signal takes to reach the target.

You can find out about this in great detail in the excellent summary over here: What the Global Positioning System Tells Us about Relativity?

In a nutshell:

1. General Relativity predicts that clocks go slower in a higher gravitational field. That is the clock aboard the GPS satellites "clicks" faster than the clock down on Earth.
2. Also, Special Relativity predicts that a moving clock is slower than the stationary one. So this effect will slow the clock compared to the one down on Earth.

As you see, in this case the two effects are acting in opposite direction but their magnitude is not equal, thus don't cancel each other out.

Now, you find out your position by comparing the time signal from a number of satellites. They are at different distance from you and it then takes different time for the signal to reach you. Thus the signal of "Satellite A says right now it is 22:31:12" will be different from what you'll hear Satellite B at the same moment). From the time difference of the signal and knowing the satellites positions (your GPS knows that) you can triangulate your position on the ground.

If one does not compensate for the different clock speeds, the distance measurement would be wrong and the position estimation could be hundreds or thousands of meters or more off, making the GPS system essentially useless.

There's the article from Ohio State University http://www.astronomy.ohio-state.edu/~pogge/Ast162/Unit5/gps.html which explains quite well why the clocks on a GPS satellite are faster by about 38 microseconds every day. The article then claims that not compensation for these 38 microseconds per day would cause a GPS to be off by about 11 km per day, plainly unusable, and claims that this (the fact that we need to compensate for the 38 microseconds to get GPS working) is proof for General Relativity.

The problem is that while the clocks are indeed off by 38 microseconds per day and General Relativity is all fine, we wouldn't actually have to compensate for it. The GPS in your car or your phone doesn't have an atomic clock. It doesn't have any clock precise enough to help with GPS. It doesn't measure how long the signal took to get from satellite A to GPS. It measures the difference between the signal from satellite A and the signal from satellite B (and two more satellites). This works if the clocks are fast: As long as they are all fast by the exact same amounts, we still get the right results.

That is, almost. Satellites don't stand still. So if we rely on a clock that is 38 microseconds fast per day, we do the calculations based on the position of a satellite that is off by 38 microseconds per day. So the error is not (speed of light times 38 microseconds times days), it is (speed of satellite times 38 microseconds times day). This is about 15 cm per day. Well, satellite positions get corrected once a week. I hope nobody thinks we could predict the position of a satellite for long time without any error.

Back to the original assumption, that without compensation the error would be 11km per day: The satellite clocks are multiplied by a factor just shy of 1 so that they go at the correct speed. But that wouldn't work. The effect that produces 38 microseconds per day isn't constant. When the satellite flies over an ocean, gravity is lower. The satellite speed changes all the time because the satellite doesn't fly on a perfect circle around a perfectly round earth made of perfectly homogenous material. If GR created an error of 11km per day uncompensated, then it is quite unconceivable that a simple multiplication of the clock speed would be good enough to reduce this to make GPS usable.

I don't think that GPS "depends on relativity" in the sense that a technological civilization that never discovered special/general relativity would be unable to make a working GPS system. You can always compare the clock in a satellite to clocks on the ground and adjust the rate until they don't drift out of sync, whether or not you understand why they were drifting out of sync. In fact, they do synchronize them empirically, not by blindly trusting a theoretical calculation.

Asking what would happen if the clocks drifted by 38 μs/day (for any reason) is a strange counterfactual because it suggests that no one is maintaining the system, in which case it would presumably quickly succumb to various other problems of non-relativistic origin. If someone is keeping some parts of the system in sync, you'd probably have to specify which parts. For example if the satellites accurately know their positions with respect to an inertial frame moving with the center of the earth, but the orientation of the earth is calculated from the time of day, then you'd have an accumulating position error of 38 μs worth of earth rotation, or a couple of centimeters at the equator, per day. But if the satellites accurately know their position with respect to a corotating reference frame, then the error would be much smaller.