Results 1 to 3 of 3

Math Help - Making sense of a proof that every integer is congruent modulo n to some element of S

  1. #1
    Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    157
    Thanks
    5

    Making sense of a proof that every integer is congruent modulo n to some element of S

    I'm trying to make sense, well better sense, of a proof of the following that my instructor gave me, while I work out my own proof of the same if then statement.

    The problem is;

    Let k \in \mathbb{Z} and n \in \mathbb{N}. Consider the set S=\{k, k+1,...,k+n-1\}

    Prove that every integer is congruent modulo n to some element of S.

    The given proof is;

    He introduces the definition of cardinality for a set and notes that the cardinality of S equals the cardinality of \mathbb{Z}_n

    (1) Let m\in\mathbb{Z}

    (2) Solve m\equiv(k+j)\pmod n

    (3) Show that (k+i)\equiv(k+j){\pmod n} \longleftrightarrow (i=j)

    (4) (k+i)-(k+j)=i-j

    (5) n|(i-j) and n|(j-i)

    So the set S is equivalent to the set H=\{0,1,2,...,n-1\} We have a Theorem that states, every integer is congruent modulo n to an element of H.

    end proof.

    So the part about the cardinality of S and H makes perfect sense. Since all S is is H with a k added to every element.

    From 2 to 3 looks good to me. He just set m=k+i

    Proving the bi-conditional in 3 is giving me a problem.
    (i=j) \rightarrow (k+i)\equiv(k+j){\pmod n} Is trivial.

    The other direction is giving me some trouble.
    (k+i)\equiv(k+j){\pmod n} \rightarrow (i=j)

    Assume (k+i)\equiv(k+j){\pmod n}

    \frac{(k+i)-(k+j)}{n}=q

    i-j=qn and j-i=(-q)n

    I don't get how this shows that i and j are equal. Does it show that they are they additive inverses of each other?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,482
    Thanks
    960

    Re: Making sense of a proof that every integer is congruent modulo n to some element

    did he state that $i,j \in \mathbb{Z}_n$ ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    157
    Thanks
    5

    Re: Making sense of a proof that every integer is congruent modulo n to some element

    Quote Originally Posted by romsek View Post
    did he state that $i,j \in \mathbb{Z}_n$ ?
    If he did one of us didn't write it down in my notes. If it makes the proof work though I would totally take it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Making sense of it all
    Posted in the Algebra Forum
    Replies: 3
    Last Post: August 18th 2013, 11:16 PM
  2. [SOLVED] congruent modulo n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 8th 2009, 10:53 AM
  3. Geo HW not AT ALL making sense
    Posted in the Geometry Forum
    Replies: 7
    Last Post: December 7th 2008, 07:18 PM
  4. Not making sense...probability
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: October 13th 2008, 04:54 PM
  5. [SOLVED] Congruent Modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 27th 2006, 06:25 PM

Search Tags


/mathhelpforum @mathhelpforum