Can you use modular arithmetic to solve this?

[jey1234]

I came across a problem like this (not homework)
x^2+y^2-k

For example,
x^2+y^2-24 \text{ ,n=4}
x^2+y^2-45 \text{ ,n=8}

If x and y are any positive integers (not given) and k is a positive integer (given), is this expression divisible by n (a positive integer that is given). A friend told me that you could use modular arithmetic to solve this. Having never learned modular arithmetic, I don't if that is true. Is it? And if yes, can someone please point me to some online resources where I can learn it? Thanks.

 

[Robert1986]

Well, modular arithmetic is something that is really easy to mess with after you have learned it, but it is kind of strange to learn. I suggest reading the wikipedia article and then try to understand what I am about to say:

So, say you have x^2 + y^2 - k and you want to know if this is divisible by n. If you think about it, this is the same as saying that if you divide x^2 + y^2 by n and get a remainder r this is the same as the remainder that you get after dividing k by n. In this case, we say that x^2 + y^2 and k are congruent modulo n. Now, each integer n has a finite number of squares \mod n which means that we only need to check a finite number of combinations.

Example: does 4 divide x^2+y^2-24 for any x,y? Well, 24 is 0 \mod 4, and the only squares \mod 4 are 0,1 (e.g. 2^2 = 0 \mod 4 and 1^2 = 1 \mod 4.) So, the answer is yes: if x,y are either 0 \mod 4 or 2 \mod 4 then 4 divides x^2 + y^2 - 24. For example, let x = 10 (which is 2 mod 4) and let y=12 (which is 0 mod 4). Then x^2 + y^2 - 24 = 100 + 144 - 24 = 220 = 4*55.

This might not make sense, but it will after you read the wikipedia article and play aroud with it for a while.

 

[jey1234]

I followed you until ("the only squares mod 4 are 0,1"). I don't understand what you mean by that. Could you please elaborate? Thanks.

 

[haruspex]

I followed you until ("the only squares mod 4 are 0,1"). I don't understand what you mean by that. Could you please elaborate? Thanks.

Square an even number: (2n)² = 4n² = 0 mod 4.
Square an odd number: (2n+1)² = 4n²+4n+1 = 1 mod 4.

 

[Robert1986]

I followed you until ("the only squares mod 4 are 0,1"). I don't understand what you mean by that. Could you please elaborate? Thanks.

To check which numbers are squares \mod n, all you need to do is square the integers less than n and see what the squares are. With n=4 this means we only need to check 1,2,3. So 1^2 = 1 \mod 4, 2^2 = 4 = 0 \mod 4 and 3^2 = 9 = 1 \mod 4. So, the only squares \mod 4 are 0,1.

You can carry this same procedure out with any integer n.