• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Modular arithmetic

  • Thread starter chwala
  • Start date

chwala

Gold Member
488
26
Problem Statement
how is -10≡2 mod 3?
Relevant Equations
modular arithmetic
ok this is a bit confusing to me, long since i did this things...-10/3=quotient -3+ remainder -1. How is the remainder 2?
 

Math_QED

Science Advisor
Homework Helper
1,050
337
By definition, this means that ##3## divides ##-10-2 = -12## which is trivially true.

What definition are you using?
 

chwala

Gold Member
488
26
By definition, this means that ##3## divides ##-10-2 = -12## which is trivially true.

What definition are you using?
i am not using any , is it that a=b mod c and a≡ b mod c imply different things? my interest is on the former. The latter i presume applies to congruence.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,081
3,278
Problem Statement: how is -10≡2 mod 3?
Relevant Equations: modular arithmetic

ok this is a bit confusing to me, long since i did this things...-10/3=quotient -3+ remainder -1. How is the remainder 2?
##-1## means the inverse of ##1##. In mod 3 arithmetic ##1 + 2 = 0##, hence ##-1 = 2##.

More simply, ##-1 \equiv 2 (mod \ 3)##
 

Orodruin

Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
15,295
5,448
Problem Statement: how is -10≡2 mod 3?
Relevant Equations: modular arithmetic

ok this is a bit confusing to me, long since i did this things...-10/3=quotient -3+ remainder -1. How is the remainder 2?
If you want to talk about remainders in connection to modular arithmetic you should define the remainder of n/m to be the smallest non-negative number k such that the quotient (n-k)/m is an integer. With this definition you have the quotient -4 and the remainder 2.

Also, as has been pointed out already, -1 = 2 mod 3 so saying -10 = -1 mod 3 is also perfectly fine, -1 and 2 are in the same equivalence class.
 

fresh_42

Mentor
Insights Author
2018 Award
10,039
6,780
Problem Statement: how is -10≡2 mod 3?
Relevant Equations: modular arithmetic

ok this is a bit confusing to me, long since i did this things...-10/3=quotient -3+ remainder -1. How is the remainder 2?
The reason is that multiples of three doesn't count anymore. The procedure is, that we impose a relation ##\sim## on the set of integers which is defined by: ##a\sim b## iff ##3## divides ##a-b## or iff ##a## and ##b## have the same sort of remainder: ##3\mathbb{Z}##, ##3\mathbb{Z}+1##, or ##3\mathbb{Z}+2##. We consider these sets as one element: ##[0]=3\mathbb{Z}##, ##[1]=3\mathbb{Z}+1##, ##[2]=3\mathbb{Z}+2##. The brackets ##[]## which indicates that entire sets are behind the numbers ##0,1,2## are usually not written, as they don't carry any additional information compared to what has already been said by using ##\operatorname{mod}## or ##\equiv##. The same is true for ##\equiv##: it is often just written as equality ##=##, an equality of sets, the so called equivalence classes with respect to ##\sim##.
 

SammyS

Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,102
881
Problem Statement: how is -10≡2 mod 3?
Relevant Equations: modular arithmetic

ok this is a bit confusing to me, long since i did this things...-10/3=quotient -3+ remainder -1. How is the remainder 2?
In addition to what has already been stated (or perhaps I missed that this, too, has already been stated):

The statmment:
## a \equiv b \mod n ##​
means that there is some integer, ##m##, such that:
## a - b = mn ## .​

Regarding your question:
## -10 \equiv 2 \mod 3 ##
because
## (-10) - (2) = (-4)( 3) ##
 
Last edited:

chwala

Gold Member
488
26
If you want to talk about remainders in connection to modular arithmetic you should define the remainder of n/m to be the smallest non-negative number k such that the quotient (n-k)/m is an integer. With this definition you have the quotient -4 and the remainder 2.

Also, as has been pointed out already, -1 = 2 mod 3 so saying -10 = -1 mod 3 is also perfectly fine, -1 and 2 are in the same equivalence class.
ok meaning that say -20/3 will be -20≡1mod 3? where quotient is -7 and k=1
-50/3 will be -50≡1 mod 3? where quotient is -17 and k=1
 
Last edited:

chwala

Gold Member
488
26
If you want to talk about remainders in connection to modular arithmetic you should define the remainder of n/m to be the smallest non-negative number k such that the quotient (n-k)/m is an integer. With this definition you have the quotient -4 and the remainder 2.

Also, as has been pointed out already, -1 = 2 mod 3 so saying -10 = -1 mod 3 is also perfectly fine, -1 and 2 are in the same equivalence class.
so you're implying that k cannot be a negative integer, rather it has to be positive?
 

chwala

Gold Member
488
26
##-1## means the inverse of ##1##. In mod 3 arithmetic ##1 + 2 = 0##, hence ##-1 = 2##.

More simply, ##-1 \equiv 2 (mod \ 3)##
i don't understand what you're saying here on inverses...this is a relative new area to me as my area of maths is applied maths...
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,081
3,278
i don't understand what you're saying here on inverses...this is a relative new area to me as my area of maths is applied maths...
Do you understand why:

##-1 \equiv 2 (mod \ 3)##?
 

Orodruin

Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
15,295
5,448
so you're implying that k cannot be a negative integer, rather it has to be positive?
No, both -10 = -1 mod 3 and -10 = 2 mod 3 are valid statements as -1 = 2 mod 3.
 

chwala

Gold Member
488
26
i figured out a way of doing this things...lets say you have a≡ k mod b then it follows that,
{a-k}/{b}= integer value...positive critism is welcome.
 

Orodruin

Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
15,295
5,448
i figured out a way of doing this things...lets say you have a≡ k mod b then it follows that,
{a-k}/{b}= integer value...positive critism is welcome.
This is just the definition of a ~ k (mod b). See, for example, post #7.
 

chwala

Gold Member
488
26

SammyS

Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,102
881
i figured out a way of doing this things...lets say you have a≡ k mod b then it follows that,
{a-k}/{b}= integer value...positive criticism is welcome.
Yes, this is correct.

In post #2, @Math_QED gives this for the specific case in which ##a=-1,\ k=2, \text{ and } b=3## .

Also, as @Orodruin mentioned, I gave a definition equivalent to yours in Post #7.

The more important issue here is that you now have a very solid way of thinking of modular equivalence (congruence), at least as it applies to integers. Congratulations on this!
 
Last edited by a moderator:
894
193
The reason why we define the remainder to positive follows from a few key ideas. Do you know what an equivalence class is? Do you know how elements of congruence mod n look like? and how many are there?

The reason that the reduced residue (the remainder) must be positive follows from the statement of the Division Theorem.
 

fresh_42

Mentor
Insights Author
2018 Award
10,039
6,780
The reason that the reduced residue (the remainder) must be positive follows from the statement of the Division Theorem.
This is wrong. The representatives (remainders) do not have to be positive. This is out of convenience and not a mathematical necessity. Thus it doesn't follow from anything. One can perfectly calculate with ##\mathbb{Z}/2\mathbb{Z} =\{\,[17],[-12]\,\}## but it makes more fun to write it as ##\{\,[0],[1]\,\}##.
 
894
193
This is wrong. The representatives (remainders) do not have to be positive. This is out of convenience and not a mathematical necessity. Thus it doesn't follow from anything. One can perfectly calculate with ##\mathbb{Z}/2\mathbb{Z} =\{\,[17],[-12]\,\}## but it makes more fun to write it as ##\{\,[0],[1]\,\}##.
true. but usually we define remainders using the statement of the Division Theorem and showing that the relation congruence modulo n on Z is an equivalence relation. Using the definition of equivalence classes....

Since the elements of Zn are equivalence classes, then it does not matter which representative we use to denote the distinct equivalence classes (this is what you are saying).

Also, it helps establish the fact that a is congruent to r modulo n, where r is the reduced reduced residue of a.


writing the remainders as positive helps us build more results of number theory in a "nice way."
 
Last edited:

fresh_42

Mentor
Insights Author
2018 Award
10,039
6,780
writing the remainders as positive helps us build more results of number theory in a "nice way."
Right. I just wanted to prevent the impression that it has to be those representatives. This contradicted the entire concept of equivalence classes. Any are as good as specific ones, just not as easy to calculate with. And if we only consider the group property and forget about the ring, then ##\mathbb{Z}_2=\{\,0,1\,\}## can even be written multiplicatively as ##\mathbb{Z}_2=\{\,-1,1\,\}##.
 

Want to reply to this thread?

"Modular arithmetic" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top