Discrete Math question Let a Element Z and k Element N Prove

Discrete Math question

Let a Element Z and k Element N. Prove that one of the numbers a, a + 1, ..., a + (k - 1) is divisible by k. Let n Element Z and m Element 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 Element 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 none of them is divisible by k

Now let us ahve k-1 boxes, ith box corresponding to number with residue i modulo k

So, none of them correspond to: 0 mod k ie numbers divisible by k

Now we can put these given numbers into these boxes but we have k numbers and k-1 boxes so at least one box with have two numbers

ie for some m,n , m not equal to n

a+m=a+n

m-n=0 mod k

But, 1<=m,n<=k-1

So, m-n =0 mod k is not possible

So we have a contradiction

Hence, one of the numbers is divisible by k

b)

(4k)^2=16k^2=0 mod 4

(4k+1)^2=16k^2+8k+1=1 mod 4

(4k+2)^2=4(2k+1)^2=0 mod 4

(4k+3)^2=16k^2+24k+9=1 mod 4

So ,0 and 1 aer the only least residues of k^2 modulo 4 for any integer k

c)

Now let us first look at least residues of squares modulo 3

(3k)^2=0 mod 3

(3k+1)^2=9k^2+6k+1=1 mod 3

(3k-1)^2=9k^1-6k+1=1 mod 3

Hence, 0 and 1 are the only least residues mod 3

So, x^2+y^2 modulo 3 can take values, 0 ,1 and 2

So, n=3=x^2+y^2 mod 3 is not possible

HEnce proved