# Mod or quotient remainder theorem (QRT)

• Instinctlol
In summary, the conversation centered around proving a problem involving integers and the use of the definitions of MOD and QRT. The correct approach was discussed, with one person using
Instinctlol
I have to prove this problem. For all n integers, if n mod 5 = 3, then n2 mod 5 = 4

Proof: Let n be an integer such that n mod 5 = 3.
n = 5k+3 for some integer k by definition of MOD or QRT?

Which one would be correct? Am I using the definition of MOD or QRT? I'm thinking its QRT because its in the form of QRT but it could be mod since we know that 3 is the remainder by the definition of MOD. Not sure which one is correct

Last edited:
Well, n mod 5=3 then n=5k+3 by the definition of mod. I'm not sure where you are going from there though.

Sorry it was n2 not x, I just edited it.

Instinctlol said:
Sorry it was n2 not x, I just edited it.

That makes more sense. But n mod 5=3 then n=5k+3 is just the definition of mod, right?

Why woudn't it be the definition of QRT?

This is kind of semantics. The QRT is what makes mod well-defined - if there were multiple remainders possible, then saying n=3 mod 5 doesn't make sense, because 2 might also be a remainder. Mod is (usually) defined as the remainder you get from the QRT - so n=3 mod 5 means that n=5k+3 by definition of mod, which only makes sense because of the QRT

Office_Shredder said:
so n=3 mod 5 means that n=5k+3 by definition of mod, which only makes sense because of the QRT

You mean n mod 5 = 3?

I am only asking because my teacher is very strict about this stuff, he requires us to state all definitions used. But I think saying the definition of MOD would make more sense because QRT is kinda implied in def of MOD

Instinctlol said:
I have to prove this problem. For all n integers, if n mod 5 = 3, then n2 mod 5 = 4

Proof: Let n be an integer such that n mod 5 = 3.
n = 5k+3 for some integer k by definition of MOD or QRT?

Which one would be correct? Am I using the definition of MOD or QRT? I'm thinking its QRT because its in the form of QRT but it could be mod since we know that 3 is the remainder by the definition of MOD. Not sure which one is correct

i think this isn't even the right approach (you could get there from here, but it's the long way around).

suppose we write [a]k, for the equivalence class (or residue class, i.e., the remainder upon division by k) of the integer a.

then once can DEFINE: ([a]k)(k) = [ab]k.

in particular, this means if: [n]5 = [3]5,

that [n2]5 = [n]5[n]5 = [3]5[3]5 = ?

Deveno said:
i think this isn't even the right approach (you could get there from here, but it's the long way around).

suppose we write [a]k, for the equivalence class (or residue class, i.e., the remainder upon division by k) of the integer a.

then once can DEFINE: ([a]k)(k) = [ab]k.

in particular, this means if: [n]5 = [3]5,

that [n2]5 = [n]5[n]5 = [3]5[3]5 = ?

My approach is correct, since I got the correct answer. I'm not quite sure what you are doing with the subscripts

Deveno said:
i think this isn't even the right approach (you could get there from here, but it's the long way around).

suppose we write [a]k, for the equivalence class (or residue class, i.e., the remainder upon division by k) of the integer a.

then once can DEFINE: ([a]k)(k) = [ab]k.

in particular, this means if: [n]5 = [3]5,

that [n2]5 = [n]5[n]5 = [3]5[3]5 = ?

Ack. I think everyone here knows what the correct answer is. There is some quibble about how to justify it, by the QRT or the definition of MOD. I'm having a hard time caring which.

Instinctlol said:
My approach is correct, since I got the correct answer. I'm not quite sure what you are doing with the subscripts

my guess is, you are learning some number theory.

my second guess is, you are more comfortable with writing:

a = b + kn than:

a = b (mod n).

what i am "doing with the subscripts" is this:

[a]n = b, where a = b + kn, and 0 ≤ b < n.

the reason for the brackets is that [a]n = [a+n]n, that is: a = a+n (mod n), but surely a and a+n aren't the same integer.

often, working with the integers mod n, the brackets are omitted (as being "understood we are working mod n").

here's the thing:

if a = b (mod n) and c = d (mod n), then (a+c) = (b+d) (mod n), and ab = cd (mod n).

well there are only n "remainder classes" mod n. this reduces the (possibly infinite) number of cases about integers, to just n cases. one can consider "numbers of the form":

0 + kn
1 + kn
2 + kn
...
(n-1) + km

but the arithmetic involved "carrying the terms involving n" is much more tedious to work with, and they don't affect the answer we're looking for. in other words, modular arithmetic is invoked to make things EASIER.

you seem to be of the view, that as long as you get the correct answer correctly, that you're good. that is only half true. homework questions are not "real problems", they are usually "invented" by a professor or text author as "practice" to test your understanding of the ideas involved. later, you will use the ideas involved in situations where the "answer" may not be known. in such a situation, "checking to see if your answer is right" is useless, the only guide you have is your confidence in your methods.

i sense a certain reluctance in you to embrace modular arithmetic. my suspicion is, this will not be a fruitful stategy for you in the long run, and may cause difficulties for you later on.

******

as others have remarked in this thread, the definition of "MOD" and the "QRT" are mirrors of each other:

a = b + kn if and only if a = b (mod n).

if i (personally) am working thorugh an equation involving "divisibility by n":

[a] = is much more straight-forward that a = b + kn, since i really don't care about which integer k is.

## 1. What is the Mod or Quotient Remainder Theorem (QRT)?

The Mod or Quotient Remainder Theorem, also known as the Division Algorithm, is a mathematical theorem that states that when dividing a number by another number, the remainder will always be less than the divisor and greater than or equal to 0.

## 2. How is the Mod or QRT used in mathematics?

The Mod or QRT is used in a variety of mathematical applications, including solving equations, finding the greatest common divisor of two numbers, and determining whether a number is prime or composite.

## 3. Can you provide an example of how to use the Mod or QRT?

Sure, let's say we want to divide 15 by 4. Using the Mod or QRT, we can write this as 15 = 4 x 3 + 3. This means that the quotient is 3 and the remainder is 3. In other words, 15 divided by 4 is 3 with a remainder of 3.

## 4. What is the relationship between the Mod or QRT and the Euclidean Algorithm?

The Mod or QRT is closely related to the Euclidean Algorithm, which is a method for finding the greatest common divisor of two numbers. The Mod or QRT is used to simplify the process of finding the greatest common divisor, making it more efficient.

## 5. Are there any limitations or restrictions to using the Mod or QRT?

Yes, the Mod or QRT can only be used for positive integers. It also cannot be used to divide by 0, as division by 0 is undefined. Additionally, it only applies to division of integers, not other types of numbers such as fractions or decimals.

Replies
2
Views
1K
Replies
4
Views
1K
Replies
1
Views
1K
Replies
6
Views
2K
Replies
11
Views
1K
Replies
16
Views
2K
Replies
11
Views
1K
Replies
3
Views
3K
Replies
4
Views
1K
Replies
12
Views
3K