Main content
Computer science
Course: Computer science > Unit 2
Lesson 5: Modular arithmetic- What is modular arithmetic?
- Modulo operator
- Modulo Challenge
- Congruence modulo
- Congruence relation
- Equivalence relations
- The quotient remainder theorem
- Modular addition and subtraction
- Modular addition
- Modulo Challenge (Addition and Subtraction)
- Modular multiplication
- Modular multiplication
- Modular exponentiation
- Fast modular exponentiation
- Fast Modular Exponentiation
- Modular inverses
- The Euclidean Algorithm
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
The quotient remainder theorem
The quotient remainder theorem
When we want to prove some properties about modular arithmetic we often make use of the quotient remainder theorem.
It is a simple idea that comes directly from long division.
It is a simple idea that comes directly from long division.
The quotient remainder theorem says:
Given any integer A, and a positive integer B, there exist unique integers Q and R such that
Given any integer A, and a positive integer B, there exist unique integers Q and R such that
A= B * Q + R where 0 ≤ R < B
We can see that this comes directly from long division. When we divide A by B in long division, Q is the quotient and R is the remainder.
If we can write a number in this form then A mod B = R
If we can write a number in this form then A mod B = R
Examples
A = 7, B = 2
7 = 2 * 3 + 1
7 mod 2 = 1
7 mod 2 = 1
A = 8, B = 4
8 = 4 * 2 + 0
8 mod 4 = 0
8 mod 4 = 0
A = 13, B = 5
13 = 5 * 2 + 3
13 mod 5 = 3
13 mod 5 = 3
A = -16, B = 26
-16 = 26 * -1 + 10
-16 mod 26 = 10
-16 mod 26 = 10
Want to join the conversation?
Have you proven the Quotient Remainder Theorem previously?(30 votes)
Here's the proof.
Proof of the Quotient Remainder Theorem
We want to prove:
Given any integer A, and a positive integer B, there exist unique integers Q and R such that: A= B * Q + R where 0 ≤ R < B
We have to prove two things:
Given any integer A and positive integer B:
1) Q and R exist
2) Q and R are unique
Proof that Q and R exist
(One approach is to use the Well Ordering Principle of Integers, but I will use an approach that is arguably simpler)
Suppose we have an integer A and a positive integer B.
Given any real number A and any positive real number B if I divide A by B, I will have an integer part (before the decimal),w, and a fractional part,f, after the decimal.
If A is >= 0 then w and f are non-negative:
A/B = w + f where 0 ≤ f < 1
A = B * w + B * f
w is an integer (it is the whole part) we can simply label it as Q, i.e. Q = w
by multiplying 0 ≤ f < 1 by B we find that
B * 0 ≤ B * f < B * 1
0 ≤ B * f < B
we can simply label the term B * f as R i.e. R= B * f
We have shown that 0 ≤ R < B
To show that R is an integer we can say that:
A = B * w + B * f
A = B * Q + R (using our new labels)
we can rearrange this to:
R = A - B * Q
but A, B, Q are integers and the result of any integer minus the product of integers is still an integer (this a property of integers)
so R must be an integer
so we have shown that given any integer A >= 0 and any positive integer B, there exist integers Q and R such that: A= B * Q + R where 0 ≤ R < B
if A is negative then
A/B = w + f where -1 < f ≤ 0
A = B * w + B * f
if f = 0 then label w as Q and B * f as R
A = B * Q + R
since B * f = R = 0 we can say that R satisfies 0 ≤ R < B
and that R is an integer
if -1 < f < 0
A = B * w + B * f
A = B * ( w - 1) + B * (f + 1)
label w-1 as Q, which is an integer
add 1 to -1 < f < 0
0 < f + 1 < 1
multiply by B
0 < B * ( f + 1 ) < B
we can simply label the term B * (f + 1) as R
We have shown that 0 < R < B which satisfies 0 ≤ R < B
To show that R is an integer, in this case, we can say that:
A = B * ( w - 1) + B * (f + 1)
A = B * Q + R (using our new labels)
we can rearrange this to:
R = A - B * Q
but A, B, Q are integers and the result of any integer minus the product of integers is still an integer (this a property of integers)
so R must be an integer
so we have shown that given any integer A < 0 and any positive integer B, there exist integers Q and R such that: A= B * Q + R where 0 ≤ R < B
so we have shown that given any integer A and any positive integer B, there exist integers Q and R such that: A= B * Q + R where 0 ≤ R < B
Proof that Q and R are unique
Suppose we have an integer A and a positive integer B.
We have shown before that Q and R exist above.
So we can find at least one pair of integers, Q1 and R1, that satisfy
A= B * Q1 + R1 where 0 ≤ R1 < B
And we can find at least one pair of integers, Q2 and R2, that satisfy
A= B * Q2 + R2 where 0 ≤ R2 < B
For labeling purposes, R2 is >= than R1 (if not we could just switch the integer pairs around).
We will show that Q1 must equal Q2 and R1 must equal R2 i.e. Q and R are unique
We can set the equations equal to each other
B * Q1 + R1 = B * Q2 + R2
B * (Q1 - Q2) = (R2 - R1)
(Q1 - Q2) = (R2 - R1)/ B
since R2 >= R1 we know that R2 - R1 is >= 0
since R2 <B and R1 >= 0 we know that R2-R1 < B
So we can say that 0 ≤ R2 - R1 < B
divide by B
0 ≤ (R2 - R1)/B < 1
but from above we showed that
(Q1 - Q2) = (R2 - R1)/ B
and Q1 - Q2 must be an integer since an integer minus an integer is an integer
so (R2 - R1)/B must be an integer but its value is >= 0 and < 1.
The only integer in that range is 0.
So (R2- R1)/B= 0 ,thus R2-R1 =0 ,thus R2 = R1
also
Q1-Q2 = 0 thus Q1 = Q2
Thus we have shown that Q1 must equal Q2 and R1 must equal R2 i.e. Q and R are unique
Hope this makes sense(128 votes)
Is this the same as Euclid's Division Lemma?(7 votes)
if n is divided by 3 remainder is 2,if n is divided by 5 remainder is 1,what is the least value of n?(2 votes)- We have
n mod 3 = 2
n mod 5 = 1
3 and 5 are coprime so we can use the Chinese Remainder Theorem
By the Chinese Remainder Theorem:
Given
n mod x = a
n mod y = b
where x and y are coprime, we have:
n = (y * (y^-1 mod x) * a + x * (x^-1 mod y) * b ) mod (x * y)
n = (5 * (5^-1 mod 3) * 2 + 3 * (3^-1 mod 5) * 1 ) mod (3 * 5)
n = 5 * 2 * 2 + 3 * 2 * 1 mod 15
n = 26 mod 15
n = 11(3 votes)
- show that one and only one out of n,n+2 or n+4 is divisible by 3(2 votes)
- Taking divisibility of numbers by 3, numbers can be expressed in 3 forms: 3q,3q+1,3q+2
(where q is the quotient obtained on dividing by 3 and 1,2 are the remainders)
Let us take Case1: n=3q
n+2 will be3q+2 and n+4=3q+4
Hence only n is divisible by3
Case2: n=3q+1
n+2=(3q+1)+2=3q+3=3(q+1)
n+4=(3q+1)+4=3q+5
Hence n+2 is divisible by 3
Similarly we can apply n=3q+2 to get n+4 divisible by 3(3 votes)
- if -16 mod 26 = 10, then how is the quotient -1?(2 votes)
- If you multiply the integer quotient by the divisor and then add the remainder (mod), you get the original number.
-16 (original number) divided by 26 (divisor) gets a quotient of -1 with a remainder of 10. The inverse is -1 (quotient) * 26 (divisor) + 10 (remainder) = -26+10= -16 (original number)(3 votes)
- I have the following question please , How can I calculate -24 mod 23 ? if i apply the theorem of the reminder then R= -1 but the theorem reads that R >= 0
Also what about if we have 0.25 mod 23 how can you solve it? in other words can we find the mod for not integer numbers . Thanks for any help(2 votes)- We want to write:
A = B * Q + R where 0 <= R < B
Doing long division the correct way (remembering that R >= 0):
-24/23 = -2 R 22
From this, we can see that:
-24 = 23 * -2 + 22
Thus -24 mod 23 = 22
We can still recover from doing long division the incorrect way (forgetting that R >= 0):
-24/23 = -1 R -1 (oops!)
This shows us that:
-24 = 23 * -1 + -1
We can add 23 to the second term and subtract it from the first term on the right hand side (since 23 - 23 is 0)
-24 = (23 * -1 - 23) + (-1 + 23)
-24 = 23 * -2 + 22
Now it's in the form we want.
Thus -24 mod 23 = 22
With regards to 0.25 mod 23:
- modular arithmetic is not applicable to non-integer numbers
In case you were wondering, the modulus must be >0 as well ( So 5 mod -23 doesn't make sense either)
Hope this makes sense(1 vote)
- Why doesn't the Euclid division algorithm work for numbers "n" where n={x:x is a set containing all negative integers} ?(2 votes)
What does it mean if Q and R are unique? That Q and R are different, or that for every pair of integers (A, B), there exists only one pair (Q,R)? I don't see how either of those are true.(1 vote)- It means that for a given pair (A,B) there exists only one pair (Q,R).
e.g.
17/3= 5 R 2
in this case (A,B)=(17,3) and (Q,R)=(5,2)
If (Q,R) was not unique then there would be some other answer to 17/3. There is not.
In reality, there is exactly one answer, for A/B.
A proof of this is posted in the comments section.(3 votes)
- if n is divided by 4 the reminder is 3 then 2n divide by 4 the reminder is(2 votes)
- n=4c+3 (c is a constant)
2n=8c+6
2n=4(2c+1)+2
2n=4d+2 (d is another constant)
remainder=2(1 vote)
- I'm so confused... I don't understand any of this. :( What does mod mean?(1 vote)
modulo (or mod) is the modulus operation very similar to how divide is the division operation. When you divide, you're finding the quotient. When you mod, you're finding the remainder.
Think of the fraction7/3, or seven divided by three. It's the same as2 + 1/3, or two and a third.
***Now, where did the two come from?***
It's because you divided 7 (your dividend) by 3 (your divisor) that you end up with 2 (your quotient).
***Now, where did the third come from?***
It's because you modded your 7 (your dividend) by 3 (your divisor), that you end up with 1 (your remainder).
So 7 divided by 3 is 2, or7/3=2(strict integer division), while 7 mod 3 is one, or7 mod 3=1
I hope this helps!(2 votes)
