Can you use modular arithmetic to solve this?

jey1234

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

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

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

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

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

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

Robert1986

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

You can carry this same procedure out with any integer [itex]n[/itex].