*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.

## No comments:

## Post a Comment