Hint : show that the map is an injection, and hence a bijection. What is the inverse image of ?
For a prime , let be the set of all equivalence classes of the relation defined by:
Prove or disprove: is a field.
So I already showed that the set has addition and multiplication well-defined. The only thing I'm having trouble with is showing that for any there exists such that .
How would I go about showing that exactly?
For any , of course...
This is because for any two positive natural numbers and there exist integers and such that , where is the greatest common divisor of and . This fact is proved using Euclid's algorithm for finding the GCD.
Now for any , ..., so...
Well you should recall that if is a finite set, and you have a function , then the following are equivalent :
1. is an injection;
2. is a surjection;
3. is a bijection.
So certainly if is injective, then it is surjective and there exists such that .
So we show it's an injection.
Suppose . Then , so . Now recall that this means , and that since is prime we must have either or . By hypothesis, we have , therefore and hence , so is indeed an injection.
In my opinion it is much better to rely on as few theorems as you can, unless you have a very good understanding of them. A friend of mine who is a PhD student once gave me a good example, after I supplied him with a proof which he found too technical (and he was right). He said : "I'll prove to you that the cube root of 2 is irrational. By Fermat's Last Theorem, has no solution in integers."