Results 1 to 3 of 3

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

  1. #1
    Senior Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    269
    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 $\displaystyle k \in \mathbb{Z}$ and $\displaystyle n \in \mathbb{N}$. Consider the set $\displaystyle 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 $\displaystyle S$ equals the cardinality of $\displaystyle \mathbb{Z}_n$

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

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

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

    (4) $\displaystyle (k+i)-(k+j)=i-j$

    (5) $\displaystyle n|(i-j)$ and $\displaystyle n|(j-i)$

    So the set S is equivalent to the set $\displaystyle 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 $\displaystyle m=k+i$

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

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

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

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

    $\displaystyle i-j=qn$ and $\displaystyle 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
    6,142
    Thanks
    2610

    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
    Senior Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    269
    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: Aug 18th 2013, 11:16 PM
  2. [SOLVED] congruent modulo n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 8th 2009, 10:53 AM
  3. Geo HW not AT ALL making sense
    Posted in the Geometry Forum
    Replies: 7
    Last Post: Dec 7th 2008, 07:18 PM
  4. Not making sense...probability
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: Oct 13th 2008, 04:54 PM
  5. [SOLVED] Congruent Modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 27th 2006, 06:25 PM

Search Tags


/mathhelpforum @mathhelpforum