My Math Forum Each integer is congruent modulo n to precisely one of the integers 0,1,...,n-1.

 Number Theory Number Theory Math Forum

January 5th, 2017, 03:58 AM   #1
Senior Member

Joined: Jan 2013
From: Italy

Posts: 153
Thanks: 7

Each integer is congruent modulo n to precisely one of the integers 0,1,...,n-1.

Hi,

I have the following exercise:

Choose n = 5, then $\displaystyle [3] \oplus [4] = [3+4] = [7] = [2]$
END.

I don't understand what is the passage that makes $[7] = [2]$
Why the set that contains the numbers that have remainders equal to 7 when divided by 5, is the same (contains the same elements), of the set that contains the numbers that have remainders equal to 2 when divided by 5?

Let's see what we have:

for hypotesis we have $\displaystyle [3] \oplus [4]$, i.e.:
[3] is the set of the elements that have the same remainder equal to 3 when divided by 5;
[4] is the set of the elements that have the same remainder equal to 4 when divided by 5;

if we consider $a \in [3], b \in [4]$

$a \equiv 3 \mbox{ (mod 5) } \\ b \equiv 4 \mbox{ (mod 5) }$

Considering this theorem:
Quote:
 Suppose $a \equiv c \mbox{ (mod m) }$ and $b \equiv d \mbox{ (mod m) }$ then (i) $a+b \equiv c+d \mbox{ (mod m)};$ (ii) $a \cdot b \equiv c \cdot d \mbox{ (mod m)};$
we have that:

$a+b \equiv 3+4 \mbox{ (mod 5)} \\ a+b \equiv 7 \mbox{ (mod 5)} \\ 5 | a+b-7 \\ a+b-7 = 5q \\ a+b = 5q+7$

but, considering the division algorithm, the remainder must be within this interval: $0 \le r < m$, but $7 > m$
in what way can I "transform" it to obtain "congruent to 2"?

I have read in another book this phrase:
Quote:
 Any integer $a$ is congruent modulo $m$ to a unique integer in the set $\left \{0,...,m-1 \right \}$ The uniqueness comes from the fact that $m$ cannot divide the difference of two such integers.
I think that it is related to this example, but, I don't understand its meaning.

Can you help me please? Thanks!

Last edited by beesee; January 5th, 2017 at 04:09 AM.

 January 5th, 2017, 05:09 AM #2 Math Team     Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,263 Thanks: 198 Here ... $a + b = 5q + 7$ All you have to do is recognise that $7 = 5 + 2$ $a + b = 5q + 5 + 2$ $a + b = (5q + 5) + 2$ $a + b = 5(q +1) + 2$ $a + b = 5Q + 2$ $5q$ represents multiples of $5$ , so does $5Q$. As far as multiples of $5$ are concerned , $5$ is absorbed from $7$ leaving $2$ Also , If you expand this notation $[7]$ congruent to modulus $5$ you get $[7]$ = { $... -18 , -13 , -8 , -3 , 2 , 7 , 12 , 17 ...$ } All these numbers are in the same equivalence class , they all have remaider $2$ when divided by $5$ It is customary to pick the smallest positive integer within the equivalence class to represent the whole equivalence class , in this case $2$ That is why $[7] = [2]$ Thanks from beesee

 Tags congruent, integer, integers, modulo, precisely

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Krokodzilla Algebra 8 November 11th, 2015 01:20 PM adilturbo Algebra 24 June 27th, 2015 05:59 PM king.oslo Algebra 1 November 21st, 2013 10:20 AM craighill5 Number Theory 3 February 21st, 2012 06:02 AM Articuno Number Theory 10 June 14th, 2009 12:11 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top