My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
  • 1 Post By agentredlum
Reply
 
LinkBack Thread Tools Display Modes
January 5th, 2017, 02: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 03:09 AM.
beesee is offline  
 
January 5th, 2017, 04:09 AM   #2
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,321
Thanks: 215

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
agentredlum is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
congruent, integer, integers, modulo, precisely



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is it possible to divide Ln(2) by a fraction of two integers to get an integer? Krokodzilla Algebra 8 November 11th, 2015 12:20 PM
Present a set of integers as one integer adilturbo Algebra 24 June 27th, 2015 05:59 PM
Theorem that sum or product of integers result in an integer king.oslo Algebra 1 November 21st, 2013 09:20 AM
Find all integers which have inverses modulo 8, and... craighill5 Number Theory 3 February 21st, 2012 05:02 AM
Modulo and Integer Division Articuno Number Theory 10 June 14th, 2009 12:11 PM





Copyright © 2017 My Math Forum. All rights reserved.