For this note I assume that you know the basics properties of divisibility including those of the congruence relation . See for example Modular arithmetics
I will show some nice problems involving the congruence relation, most of them are very useful in problem solving, thus we can consider this problems as lemmas.
Problem 1. If then there exists an integer such that . is called the multiplicative inverse of modulo .
Solution. Consider the numbers . If for , then , since we conclude that and then . Thus the numbers are pairwise distinct modulo , since this set consists of numbers then it is a complete residue system modulo . In particular, for some we have .
Problem 2. Let be an integer:
If is prime then . [Wilson's Theorem]
If is composite and then .
Hint for the first part. If is an odd prime, prove that the set can be divided in pairs where and are inverse each other.
Problem 3. If is a prime and then .
Solution. We know that then . The number is divisible by while is not, then is divisible by .
Problem 4. If is a prime then .
Hint. Use the previous problem.
Now, you can practice with the following problems. To avoid confusion I will call these problems N1, N2, etc.
Problem N1. ¿Does there exist a positive integer for wich the set can be partitioned in two subsets and such that the product of the elements of is equal to the product of the elements of ?
Problem N2. Let be a prime. For each denote by the remainder when is divided by , thus . Calculate .
Please post your comments and solutions!