Mod or quotient remainder theorem (QRT)

[Instinctlol]

I have to prove this problem. For all n integers, if n mod 5 = 3, then n² 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

 

[Dick]

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.

 

[Instinctlol]

Sorry it was n² not x, I just edited it.

 

[Dick]

Sorry it was n² 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?

 

[Instinctlol]

Why woudn't it be the definition of QRT?

 

[Office_Shredder]

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

 

[Instinctlol]

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

 

[Deveno]

I have to prove this problem. For all n integers, if n mod 5 = 3, then n² 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]₅ = [3]₅,

that [n²]₅ = [n]₅[n]₅ = [3]₅[3]₅ = ?

 

[Instinctlol]

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]₅ = [3]₅,

that [n²]₅ = [n]₅[n]₅ = [3]₅[3]₅ = ?

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

 

[Dick]

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]₅ = [3]₅,

that [n²]₅ = [n]₅[n]₅ = [3]₅[3]₅ = ?

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.

 

[Deveno]

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.