Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can you use modular arithmetic to solve this?

  1. Nov 3, 2012 #1
    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.
  2. jcsd
  3. Nov 3, 2012 #2
    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.
  4. Nov 6, 2012 #3
    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.
  5. Nov 7, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Square an even number: (2n)2 = 4n2 = 0 mod 4.
    Square an odd number: (2n+1)2 = 4n2+4n+1 = 1 mod 4.
  6. Nov 7, 2012 #5
    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].
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook