Daily 13: Some Modular Mathematics

This daily assignment will serve as a reference to my weekly 7 assignment. The problem is essentially this:

For some integer q,n, if q = n^2 (mod 5) then either q = 0 (mod 5), q = 1 (mod 5), or 
q = 4 (mod 5).

Proof: Let q and n be some integers and assume q = n^2 (mod 5). To prove the statement above, we will use cases. Since n is an integer, we know that either n = 0 (mod 5), n = 1 (mod 5), n = 2 (mod 5), n = 3 (mod 5), or n = 4 (mod 5). Out of all these cases, we will show that the only possibilities are that q = 0 (mod 5), or q = 1 (mod 5), or q = 4 (mod 5).

Case 1: n = 0 (mod 5). This means n^2 = 0^2 (mod 5) = 0 (mod 5); I used the well known theorem: if
a = b (mod n) then a^2 = b^2 (mod n), it's a strait forward proof. Since n^2 = 0 (mod 5), there exists an integer a such that n^2 = 0 + 5a = 5a. Also, since q = n^2 (mod 5), there exists an integer b such that
q = n^2 + 5b and plugging in n^2 = 5a we get q = 5a + 5b = 5(a+b) which means q = 0 (mod 5).

Case 2: n = 1 (mod 5). This means n^2 = 1^2 (mod 5) = 1 (mod 5). Since n^2 = 1 (mod 5), there exists an integer a such that n^2 = 1 + 5a. Also, since q = n^2 (mod 5), there exists an integer b such that
q = n^2 + 5b and plugging in n^2 = 1 + 5a we get q = 1 + 5a + 5b = 1 + 5(a+b) which means
q = 1 (mod 5).

Case 3: n = 2 (mod 5). This means n^2 = 2^2 (mod 5) = 4 (mod 5). Since n^2 = 4 (mod 5), there exists an integer a such that n^2 = 4 + 5a. Also, since q = n^2 (mod 5), there exists an integer b such that
q = n^2 + 5b and plugging in n^2 = 4 + 5a we get q = 4 + 5a + 5b = 4 + 5(a+b) which means
q = 4 (mod 5).

Case 4: n = 3 (mod 5). This means n^2 = 3^2 (mod 5) = 9 (mod 5) = 4 (mod 5). Then this case follows exactly like case 3, so we can conclude q = 4 (mod 5).

Case 5: n = 4 (mod 5). This means n^2 = 4^2 (mod 5) = 16 (mod 5) = 1 (mod 5). Then this case follows exactly like case 2, so we can conclude q = 1 (mod 5).

Therefore, considering all the cases, we can see that the only possibilities are either q = 0 (mod 5), q = 1 (mod 5), or q = 4 (mod 5). So the theorem has been proved.

Note: in the context of the weekly 7 assignment, q is prime. This means q cannot be congruent to 0 (mod 5) because then q would be a multiple of 5, which can't happen.