1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmetic

  1. May 12, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove that it is impossible to find an integer n, such that

    n^2 = 2 mod(4) or n^2 = 3 mod(4)

    Hence or otherwise, prove that there do not exist integers m and n such that

    3m^2 - 1 = n^2

    2. Relevant equations



    3. The attempt at a solution

    Since n must be congruent to each of 0,1,2,3, n^2 must be congruent to 0,1,4,9 but what do I do next to prove this?
     
  2. jcsd
  3. May 12, 2012 #2
    Well, if (for example) [itex]n^2 \equiv 9\pmod 4[/itex], and you know that [itex]9 \equiv 1\pmod 4[/itex],then you can tell that [itex]n^2 \equiv ??\pmod 4[/itex]
     
  4. May 12, 2012 #3

    I like Serena

    User Avatar
    Homework Helper

    Welcome to PF, mike! :smile:

    Can you simplify 0,1,4,9 mod 4?
    Is any of those congruent to 2 or to 3?
     
  5. May 12, 2012 #4
    Sorry, still confused :(
     
  6. May 12, 2012 #5

    I like Serena

    User Avatar
    Homework Helper

    As you say, n^2 must be congruent to one of 0,1,4,9.

    Writing something "mod 4", means you are only interested in the remainder after division by 4.
    What is the remainder if you divide for instance 9 by 4?
     
  7. May 12, 2012 #6
    So: 9 = 1 mod(4), since 9-1 = 8/4=2
     
  8. May 12, 2012 #7

    I like Serena

    User Avatar
    Homework Helper

    Yep.
    So what are the remainders of 0,1,4,9?
     
  9. May 12, 2012 #8
    0= mod(4)
    1= mod(4)
    4= 0 mod(4)
    9= 1 mod(4)
     
  10. May 12, 2012 #9

    I like Serena

    User Avatar
    Homework Helper

    If you divide 1 by 4, it cannot be divided and the remainder is just 1.
    The same for zero.

    So your remainders for n^2 are 0,1,0,1.
    Is any of those congruent to 2 or to 3?
     
  11. May 12, 2012 #10
    No, because 0/4 or 1/4 is not 2 or 3? & hence it's impossible to find an integer to satisfy it?
     
  12. May 12, 2012 #11

    I like Serena

    User Avatar
    Homework Helper

  13. May 12, 2012 #12
    Thanks :)

    For part b) Since n^2 is congruent to 0 or 1 mod(4), after re-arranging we see that
    3m^2 = n^1+1, so then n^2 + 1 is congruent to 1 or 2 mod(4). What should be done about the 3m^2?
     
  14. May 12, 2012 #13

    I like Serena

    User Avatar
    Homework Helper

    What are the possible remainders of m^2?
     
  15. May 12, 2012 #14
    Is it 0,1,4,9 but then times by 3 so 0,3,12,27? Or is that completely wrong..
     
  16. May 12, 2012 #15

    I like Serena

    User Avatar
    Homework Helper

    Oh that is correct.
    But didn't we conclude that 0,1,4,9 were congruent to 0,1,0,1?

    Multiply that with 3!
     
  17. May 12, 2012 #16
    Oh! So the remainders of 3m^2 are 0,3,0,3. So 3m^2 is congruent to 0 or 3 mod(4), but how we combine both of expressions?
     
    Last edited: May 12, 2012
  18. May 12, 2012 #17

    I like Serena

    User Avatar
    Homework Helper

    Well, you already had:
    Perhaps compare it to that?
     
  19. May 13, 2012 #18
    How do I compare it to that?
    Can I say since 3m^2=n^2+1, then 3m^2 is congruent to 0,1,2,3 mod(4)?...
     
  20. May 13, 2012 #19

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If we had 3m2=n2+1, then we know that 3m2=n2+1 (mod 4). What are the possible values of the left hand side? What are the possible values of the right hand side? (these were calculated earlier in the thread) Is it possible for the left hand and right hand side to be equal?
     
  21. May 13, 2012 #20
    Do you mean 0,3,0,3 and 0,1,0,1?
     
    Last edited: May 13, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular Arithmetic
  1. Modular arithmetic (Replies: 2)

  2. Modular arithmetic (Replies: 3)

  3. Modular arithmetic (Replies: 3)

  4. Modular arithmetic (Replies: 6)

  5. Modular arithmetic (Replies: 3)

Loading...