21127 Lecture Notes - Lecture 18: Borr, Natural Number, European Route E20
16 Dec 2015
School
Department
Course
Professor
Document Summary
In recitation on thursday, you proved that a particular relation on z is an equivalence relation. For a given, xed n n, we de ne the relation by saying, for any x, y z, x y k z. nk = x y. 5 3 7 + 2 6 15 7 + 12 20 2 mod 6. The equivalence classes under the relation ( mod n) correspond to the possible remainders upon division by n. to say that n | x y means that x n have the same remainder. However, notice that this is not what the relation is de ned as! This is a separate observation that we need to prove. This amounts to showing that any integer, when divided by n, yields a unique representation as a multiple of n plus some remainder that is between 0 and n 1. Division lemma: let n n be given and xed. Let x z be arbitrary and xed.
