Hacker News new | past | comments | ask | show | jobs | submit login

You're right that there's only so many possible nonzero remainders mod 3, and you can check for yourself that if you multiply any of them together, you end up with another non-multiple of 3.

The same is true for 5: it takes a little more time to check, since there are a few more possible remainders mod 5, but it happens to be true, and so you can indeed verify, that when you multiply non-multiples of 5 together, the result is also a non-multiple of 5.

And you can go ahead and check by brute force that this is true of 7, and 11, and 13 as well. Mod any of those, when you multiply nonzero values, you get a nonzero result. Any modulus this happens to be true of, you can sit down and verify that it's true of, by just checking all the finitely many cases.

But knowing it's true of the first few primes doesn't guarantee the same fact will be true of every other prime you check.

How do we know that this is in fact the case for every prime?

It's not true of every number, after all: 4 isn't divisible by 10, and 5 isn't divisible by 10, and yet 4 * 5 is divisible by 10. 10 doesn't have the property that it only divides a product if it divides one of the factors.

So why do primes have this property? Obviously, if 0 < A, B < p, you can't get A * B = p right on the dot (by the relevant definition of "prime"), but why can't it be the case that A * B = some multiple of p?

This is a non-obvious fact. This is where the Euclidean algorithm reasoning invoked above comes in. It doesn't just follow immediately.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact