Let a epsilon Z and k epsilon N Prove that one of the number

Let a epsilon Z and k epsilon N. Prove that one of the numbers a, a + 1, ..., a + (k - 1) is divisible by k. Let n epsilon Z and m epsilon N. The least residue of n modulo m is the unique integer among 0, 1, ..., m - 1 to which n is congruent modulo m. For k epsilon Z. which numbers can be the least residue of k^2 modulo 4? Prove that no integer which is congruent to 3 modulo 4 can be written as a sum of two squares. That is, if n = 3 (mod 4), then there are no integers x and y such that n = x^2 + y^2.)

Solution

a)

Assume not true.

SO we have k numbers and none of them is 0 mod k

But there are only k-1 residues mod k (from 1,....,k-1} and we have k numbers

So two of them must have the same residue mod k (By Pigeonhole Principle)

So, a+r=a+s mod k, 0<=r,s<=k-1 , r and s not equal

So,r-s=0 mod k

Without loss of generality we can assume ,r>s

But, 0<r-s<k-1

So,r-s=0 mod k is not possible

So a contradiction

Hence, one of these numbers is divisible by k

b)

There are four least residues mod 4: 0,1,2,3

Squaring these gives

0^2=0 mod 4

1^2=1 mod 4

2^2=0 mod 4

3^2=1 mod 4

So,0 and 1 can be least residues of k^2 modulo 4

c)

As we saw in part b), x^2 and y^2 can be 0 or 1 mod 4

So ,x^2+y^2 can be 0 , 1 or 2 mod 4

ie x^2+y^2=3 mod 4 is not possible