Remainder Theorem: Definition, Examples & More: Everyone loves to find a shortcut whether it involves driving directions or some other type of long task. Discovering a quicker and more efficient way to arrive at the same endpoint makes you feel good since you’ve most likely saved time, effort, and/or money. Math is filled with these types of shortcuts and one of the more useful ones is the remainder theorem.
The Chinese remainder theorem is a theorem that gives a unique solution to simultaneous linear congruences with coprime moduli. In its basic form, the Chinese remainder theorem will determine a number p that, when divided by some given divisors, leaves given remainders.
Remainder Theorem/Polynomial Remainder Theorem
The remainder theorem states that when a polynomial, f(x), is divided by a linear polynomial, (x -a) the remainder of that division will be equivalent to f(a). In other words, if you want to evaluate the function f(x) for a given number, a, you can divide that function by x – a and your remainder will be equal to f(a).
basic remainderIt should be noted that the remainder theorem only works when a function is divided by a linear polynomial, which is of the form x + number or x – number. How does the remainder theorem save you time? Let’s find out.
Remainder Theorem Function
The remainder theorem is especially useful when it is paired with the synthetic division. If you remember, a synthetic division is an alternate method to quickly and easily divide polynomials instead of using long division. Also, remember that in synthetic division, the number in the bottom row in the last column on the right is the remainder. Thus, rather than plugging a value in and using an order of operations, you can use synthetic division as a way to evaluate a polynomial for a given value.
Additionally, synthetic division and the remainder theorem can be used to determine if a value is a zero of a function. Hopefully, you remember that a zero of a function, by definition, is any point c, where f(c) = 0. Therefore, if you find a remainder of zero after performing synthetic division, the number listed out front, referred to as a in the definition above, evaluates to zero, or f(a) = 0.
Note, that you can use long division instead of synthetic division, but it’s almost always faster and easier to use synthetic division.
How to Use the Theorem
Let’s take the function f(x) = x^4 + 3x^3 – 6x^2 – 6x + 8. Suppose you were told to evaluate it for x = 3. You could spend the time to plug in a 3 for every x (all four of them) listed above. Then you could perform the order of operations (PEMDAS anyone?) to evaluate all five terms. Finally, you would combine all the like terms to get the final answer for f(3).
But it’s so much quicker and easier to use the remainder theorem. Simply set up synthetic division where you will divide x^4 + 3x^3 – 6x^2 – 6x + 8 by x – 3, and you’ll have you answer in no time. Remember, that you will divide by x – 3 (not x + 3) because a = 3 in this example and the remainder theorem is based on dividing by x – a (not x + a). You should get 98 as the remainder, which means that f(3) = 98. The work is shown below.
After you perform the synthetic division, you should notice several things.Now, let’s evaluate the same function for x = -4. You can use the same process of dividing x^4 + 3x^3 – 6x^2 – 6x + 8 by x + 4. Note, that in this example, since a = -4, x – a will be x – (-4), or x + 4.
Chinese Remainder Theorem
In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime. The earliest known statement of the theorem is by the Chinese mathematician Sunzi in Sunzi Suanjing in the 3rd century AD.
The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers. The Chinese remainder theorem (expressed in terms of congruences) is true over every principal ideal domain. It has been generalized to any commutative ring, with a formulation involving ideals.
Let n1, …, nk be integers greater than 1, which are often called moduli or divisors. Let us denote by N the product of the ni.
The Chinese remainder theorem asserts that if the ni are pairwise coprime, and if a1, …, ak are integers such that 0 ≤ ai < ni for every i, then there is one and only one integer x, such that 0 ≤ x < N and the remainder of the Euclidean division of x by ni is ai for every i.
This may be restated as follows in term of congruences: If the ni are pairwise coprime, and if a1, …, ak are any integers, then there exists an integer x such that
and any two such x is congruent modulo N.
In abstract algebra, the theorem is often restated as: if the ni are pairwise coprime, the map
- defines a ring isomorphism
between the ring of integers modulo N and the direct product of the rings of integers modulo the ni. This means that for doing a sequence of arithmetic operations in one may do the same computation independently in each and then get the result by applying the isomorphism (from the right to the left). This may be much faster than the direct computation if N and the number of operations are large. This is widely used, under the name multi-modular computation, for linear algebra over the integers or the rational numbers.
The theorem can also be restated in the language of combinatorics as the fact that the infinite arithmetic progressions of integers form a Helly family.
The process to solve systems of congruences with the Chinese remainder theorem
For a system of congruences with co-prime moduli, the process is as follows
Chinese Remainder Theorem Example
p1:x=2 (mod 3)
p2:x=3 (mod 5)
p3:x=2 (mod 7)
From p1, x=3t+2, for some integer t.
Substituting this into p2 gives 3t=1 (mod 5).
Looking up 1/3 in the division table modulo 5, this reduces to a simpler equation
p4: t=2 (mod 5)
which, in turn, is equivalent to t=5s+2 for an integer s.
Substitution into x=3t+2 yields x=15s+8.
This now goes into p3:15s+8=2 (mod 7).
Casting out 7 gives s=1 (mod 7). From here, s=7u+1 and,
Note that 105=lcm(3,5,7). Thus we have solutions 23,128,233,…