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!

Fun with counting and modular arithmetic

  1. Jul 16, 2007 #1
    So today I was doing a problem out of my book for practice, and I came across some interesting results.

    Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4.

    a set of consecutive integers

    1 mod 4 = 1
    2 mod 4 = 2
    3 mod 4 = 3
    4 mod 4 = 0
    5 mod 4 = 1

    a set of nonconsecutive integers

    6 mod 4 = 2
    14 mod 4 = 2
    3 mod 4 = 3
    71 mod 4 = 3
    35 mod 4 = 3

    should the question be rephrased like this?
    Show that among any group of five (not necessarily consecutive) integers, there are two or more with the same remainder when divided by 4.
     
  2. jcsd
  3. Jul 17, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    "There are two" is an informal (if inexact) way of expressing "there are two or more". I.e. if there are two or more, then there ARE certainly two that are equal. Shouldn't you be solving the problem, not doing linguistic hair splitting? Or is this a linguistics class? :)
     
    Last edited: Jul 17, 2007
  4. Jul 17, 2007 #3
    This is a simple pigeonhole problem. What are the pigeons and what are the holes? I assume you are familiar with the pigeonhole theorem.

    In determining the holes, you'll want to consider the division algorithm.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Fun with counting and modular arithmetic
  1. Modular arithmetic (Replies: 2)

Loading...