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