Hey, I am having a difficult time trying to prove a few statements relating to Euler's Theorem.
1. Prove for any n: If are in , then is also in , using a contrapositive argument.
2. Prove: Every has an inverse modulo n in , by considering the linear congruence
3. Prove: For every the function defined by is a permutation.
I really don't know what to do for these.
Any help would be greatly appreciated.
Thanks
i believe is the set of all positive integers (including 1) relatively prime to n.
For the first one:
given that so there exist integers such that . similarly there exist integers such that . Multiplying the two equations we have:
.
The second part follows again from the fact that if then there exist integers such that . Note that . hence is the you want.
for the third one you need to show that is bijective. can you do it?
Sorry Tonio,
Thanks abhishekkgp, I fully understand the first one now. Is that all the working for the second one? I think I understand it.
I can see that for the third one, that it is surjective and because the set is finite it is therefore bijective, but I don't get how to work it out properly.
Any help here?
Thanks so much for your help.