Number System Part IV: Remainder
Remainders
There are a plethora of remainder related questions you can expect in your exam. So it is a mandatory requirement to create a clear awareness of remainders before going to attend the exam.
Based on above illustration, any number 'N' can be expressed as N=dq+r.
Properties of remainders
When the dividend is less than divisor, then the remainder is the dividend itself. Eg: when 5 divided by 7, the remainder is 5 itself, and then the quotient of this division is 0.
Remainders are consistent under basic mathematical operations such as addition, subtraction, multiplication and powers.
Addition:When N1 and N2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r1 and r2, then the remainder when N1+N2 divided by d is r1+r2.
Eg. Rem[11/9]=2 and Rem[14/9]=5
∴Rem[(11+14)/9]=2+5=7
Subtraction:When N1 and N2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r1 and r2, then the remainder when N1−N2 divided by d is r1−r2.
Eg. Rem[19/10]=9 and Rem[15/10]=5
∴Rem[(19−15)/10]=9−5=4
Multiplication:When N1 and N2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r1 and r2, then the remainder when N1×N2 divided by d is r1×r2.
Eg. Rem[14/10]=4 and Rem[12/10]=2
∴Rem[(14×12)/10]=4×2=8
Powers or exponents:When a dividend 'N' divided by divisor 'd', leaves a remainder 'r', then Nn leaves a remainder rn when it is divided by d.
Eg. Rem[10/8]=2
∴Rem[10^2/8]=2^2=4
Concept of Negative remainders: As per Eucledian Lemma any number 'N' can be expressed in the following way; N=dq+r
In a similar arrangement, 7 can be expresses as; 7=3×2+1, where 3 is the divisor, 2 is the quotient and 1 is the remainder.
7 can be expressed in the following way too; 7=3×3−2, where 3 is the same divisor which we considered above, 3 is the new quotient and '-2' is the remainder as per the change in the quotient. Therefore the remainders 1 and -2 are representing the same division. Hence -2 is the corresponding negative remainder of the original remainder 1, when the divisor is 3.
Negative remainder=original remainder−divisor
Therefore original remainder=divisor+negative remainder
There are a plethora of remainder related questions you can expect in your exam. So it is a mandatory requirement to create a clear awareness of remainders before going to attend the exam.
Based on above illustration, any number 'N' can be expressed as N=dq+r.
Properties of remainders
When the dividend is less than divisor, then the remainder is the dividend itself. Eg: when 5 divided by 7, the remainder is 5 itself, and then the quotient of this division is 0.
Remainders are consistent under basic mathematical operations such as addition, subtraction, multiplication and powers.
Addition:When N1 and N2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r1 and r2, then the remainder when N1+N2 divided by d is r1+r2.
Eg. Rem[11/9]=2 and Rem[14/9]=5
∴Rem[(11+14)/9]=2+5=7
Subtraction:When N1 and N2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r1 and r2, then the remainder when N1−N2 divided by d is r1−r2.
Eg. Rem[19/10]=9 and Rem[15/10]=5
∴Rem[(19−15)/10]=9−5=4
Multiplication:When N1 and N2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r1 and r2, then the remainder when N1×N2 divided by d is r1×r2.
Eg. Rem[14/10]=4 and Rem[12/10]=2
∴Rem[(14×12)/10]=4×2=8
Powers or exponents:When a dividend 'N' divided by divisor 'd', leaves a remainder 'r', then Nn leaves a remainder rn when it is divided by d.
Eg. Rem[10/8]=2
∴Rem[10^2/8]=2^2=4
Concept of Negative remainders: As per Eucledian Lemma any number 'N' can be expressed in the following way; N=dq+r
In a similar arrangement, 7 can be expresses as; 7=3×2+1, where 3 is the divisor, 2 is the quotient and 1 is the remainder.
7 can be expressed in the following way too; 7=3×3−2, where 3 is the same divisor which we considered above, 3 is the new quotient and '-2' is the remainder as per the change in the quotient. Therefore the remainders 1 and -2 are representing the same division. Hence -2 is the corresponding negative remainder of the original remainder 1, when the divisor is 3.
Negative remainder=original remainder−divisor
Therefore original remainder=divisor+negative remainder
Let's
look at one more example to understand concept of negative remainders.
Rem[18/8]=2 and Rem[5/8]=5
∴Rem[(18−5)/8]=2−5=−3
Hence the original remainder=divisor+negative remainder
=8+(−3)=5
ie; Rem[(18−5)/8]=Rem[13/8]=5
Pattern of remainders:
Pattern of remainders is one of the most aesthetical and very important features of remainders. Let us consider the following pattern of remainders;
Rem[3^1/5]=3
Rem[3^2/5]=3×3→4
Rem[3^3/5]=4×3→2
Rem[3^4/5]=2×3→1
Rem[3^5/5]=1×3→3 and so on...
The above pattern of remainders will repeat cyclically after the occurrence of 1 and the pattern of remainders is 3,4,2,1, 3,4,2,1... In the given example, there are 4 distinct remainders. If the exponent of 3 is any multiple of 4, then the remainder should be 1; Ie. if the exponent is in the form 4k+1→remainder is 3
4k+2→remainder is 4
4k+3→remainder is 2
4k+0→remainder is 1, Where k is any whole number, k = 0, 1, 2, 3...
Find the remainder when 3^1729 divided by 5
As per the above explanation, there are 4 distinct remainders and those are occurring in the order 3, 4, 2, 1. 1729=4k+1 (when 1729 divided by 4, it leaves the remainder 1). If the exponent is in the form 4k+1, then the remainder is 3.
Find the remainder when 13^271 divided by 7
First of all develop the cyclic pattern of possible remainders.
Rem[(13^1)/7]=6
Rem[(13^2)/7]=6×6→1
Rem[(13^3)/7]=1×6→6
Rem[(13^4)/7]=6×6→1
Now we got a pattern of remainders in the cyclic order 6,1,6,1...
Note: In the pattern of remainders if in any step the remainder occurs as 1, then the pattern will start from there. Hence the operation of finding remainders can stop at that point.
In the above pattern, there are two distinct remainder, ie. when the exponent is odd, remainder is 6 and when the exponent is even, then the remainder is 1. ∴Rem[(13^271)/7]=6, because 271 is an odd exponent.
Fermat's little theorem
Let N and p are two relatively prime numbers and p itself is a prime, then N^p−1/p leaves a remainder of 1.
Eg. Rem[100^36/37]=1
Find the remainder when 100^41 divided by 41
As per Fermat's theorem, (N^p−1)/p leaves a remainder of 1, where N and p are two relatively prime numbers and p itself is a prime. In the given question, the divisor 41 is a prime number and 100 and 41 are relatively prime.∴Rem[(100^40)/41]=1.
So, Rem[(100^41)/41]=Rem[(100^40×100)/41]=Rem[100/41]=18
Wilson's theorem
For all prime p, [(p−1)!+1] is always divisible by p.
OR
When (p−1)! Is divided by p, the remainder is (p−1).
Let's look at an example to understand Wilson's theorem.
Find the remainder when 6! Divided by 7.
As per Wilson's theorem; 7 is a prime →Rem[(7−1)!/7]=7−1=6
Remainder theorem and its numerical application
If p(x) is a polynomial in x, then p(a) is the remainder when p(x) divided by (x−a).
Understanding the numerical application of this theorem will help you to solve some complicated type of remainder related questions. Let's take a look at few examples to understand remainder theorem better.
Find the remainder when 2^402 divided by 7.
Consider 2^402 as a polynomial in 2. Also, 7 can be expressed in terms of 2 as: 7=2^3−1, which can be considered as a polynomial on 2^3
∴Rem[(2^402)/7]=Rem[((2^3)^134)/(23−1)]=1^134=1
Find the remainder when 16^133 divided by 17.
17=16+1→ it is in the form of x+1, where x=16
16^133 is in the form of x^133, where x=16
`"Rem"[16^133/(16 + 1)] = (-1)^133 = -1
Here the remainde is negative, so original remainder (positive) is 17 - 1 = 16
Find the remainder when 27^101 divided by 82.
82=(3^4)+1
27^101=(3^3)^101=(3^4)^75⋅(3^3)=(34)^75⋅(27)
Rem[(27^101)/82]=Rem[(3^4)^75⋅(27)/(3^4)+1)]=(−1)^75⋅(27)=−27
Here we got negative remainder as -27, so actual remainder is 82 - 27 = 55
Rem[18/8]=2 and Rem[5/8]=5
∴Rem[(18−5)/8]=2−5=−3
Hence the original remainder=divisor+negative remainder
=8+(−3)=5
ie; Rem[(18−5)/8]=Rem[13/8]=5
Pattern of remainders:
Pattern of remainders is one of the most aesthetical and very important features of remainders. Let us consider the following pattern of remainders;
Rem[3^1/5]=3
Rem[3^2/5]=3×3→4
Rem[3^3/5]=4×3→2
Rem[3^4/5]=2×3→1
Rem[3^5/5]=1×3→3 and so on...
The above pattern of remainders will repeat cyclically after the occurrence of 1 and the pattern of remainders is 3,4,2,1, 3,4,2,1... In the given example, there are 4 distinct remainders. If the exponent of 3 is any multiple of 4, then the remainder should be 1; Ie. if the exponent is in the form 4k+1→remainder is 3
4k+2→remainder is 4
4k+3→remainder is 2
4k+0→remainder is 1, Where k is any whole number, k = 0, 1, 2, 3...
Find the remainder when 3^1729 divided by 5
As per the above explanation, there are 4 distinct remainders and those are occurring in the order 3, 4, 2, 1. 1729=4k+1 (when 1729 divided by 4, it leaves the remainder 1). If the exponent is in the form 4k+1, then the remainder is 3.
Find the remainder when 13^271 divided by 7
First of all develop the cyclic pattern of possible remainders.
Rem[(13^1)/7]=6
Rem[(13^2)/7]=6×6→1
Rem[(13^3)/7]=1×6→6
Rem[(13^4)/7]=6×6→1
Now we got a pattern of remainders in the cyclic order 6,1,6,1...
Note: In the pattern of remainders if in any step the remainder occurs as 1, then the pattern will start from there. Hence the operation of finding remainders can stop at that point.
In the above pattern, there are two distinct remainder, ie. when the exponent is odd, remainder is 6 and when the exponent is even, then the remainder is 1. ∴Rem[(13^271)/7]=6, because 271 is an odd exponent.
Fermat's little theorem
Let N and p are two relatively prime numbers and p itself is a prime, then N^p−1/p leaves a remainder of 1.
Eg. Rem[100^36/37]=1
Find the remainder when 100^41 divided by 41
As per Fermat's theorem, (N^p−1)/p leaves a remainder of 1, where N and p are two relatively prime numbers and p itself is a prime. In the given question, the divisor 41 is a prime number and 100 and 41 are relatively prime.∴Rem[(100^40)/41]=1.
So, Rem[(100^41)/41]=Rem[(100^40×100)/41]=Rem[100/41]=18
Wilson's theorem
For all prime p, [(p−1)!+1] is always divisible by p.
OR
When (p−1)! Is divided by p, the remainder is (p−1).
Let's look at an example to understand Wilson's theorem.
Find the remainder when 6! Divided by 7.
As per Wilson's theorem; 7 is a prime →Rem[(7−1)!/7]=7−1=6
Remainder theorem and its numerical application
If p(x) is a polynomial in x, then p(a) is the remainder when p(x) divided by (x−a).
Understanding the numerical application of this theorem will help you to solve some complicated type of remainder related questions. Let's take a look at few examples to understand remainder theorem better.
Find the remainder when 2^402 divided by 7.
Consider 2^402 as a polynomial in 2. Also, 7 can be expressed in terms of 2 as: 7=2^3−1, which can be considered as a polynomial on 2^3
∴Rem[(2^402)/7]=Rem[((2^3)^134)/(23−1)]=1^134=1
Find the remainder when 16^133 divided by 17.
17=16+1→ it is in the form of x+1, where x=16
16^133 is in the form of x^133, where x=16
`"Rem"[16^133/(16 + 1)] = (-1)^133 = -1
Here the remainde is negative, so original remainder (positive) is 17 - 1 = 16
Find the remainder when 27^101 divided by 82.
82=(3^4)+1
27^101=(3^3)^101=(3^4)^75⋅(3^3)=(34)^75⋅(27)
Rem[(27^101)/82]=Rem[(3^4)^75⋅(27)/(3^4)+1)]=(−1)^75⋅(27)=−27
Here we got negative remainder as -27, so actual remainder is 82 - 27 = 55
Comments
Post a Comment