What is Remainder theorem: Definition and 71 Discussions

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 Sun-tzu in the Sun-tzu Suan-ching in the 3rd century CE.
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.

View More On Wikipedia.org
Recent contents Top users
  1. D

    Remainder Theorem: Solve x^80 - 8x^30 + 9x^24 + 5x + 6 Divided by (x+1)

    Homework Statement Find the remainder when (x^80 - 8x^30 + 9x^24 + 5x + 6) is divided by (x+1) Homework Equations The Attempt at a Solution So I'm not really sure where to start. I tried starting by doing long polynomial division, but I get stuck. How do I start this?
  2. C

    Proving m mod d = n mod d with Quotient Remainder Theorem

    Homework Statement Prove that is m, n, and d are integers and d divides (m-n) then m mod d = n mod d. Homework Equations Quotient Remainder Theorem: Given any integer n and positive integer d, there exists unique integers q and r such that n=dq + r and 0\leqr<d and n mod d = r. The...
  3. S

    Chinese Remainder Theorem: How Can It Help Solve Modulo Residue Problems?

    Chinese remainder theorem, urgent! Homework Statement This is an attempt to make the Chinese Remainder Theorem more concrete. Let m = 206 and n = 125. You may use the fact that 89n - 54m = 1. (a) What does the Chinese Remainder Theorem have to say about pairs of residues modulo 206 and...
  4. S

    What is the solution expressed in the Chinese Remainder Theorem?

    Homework Statement I am trying to learn the Chinese Remainder Theorem from the following website: http://www.libraryofmath.com/chinese-remainder-theorem.html The only thing I don't understand is why the end result is expressed as another linear congruence. In the first example, the...
  5. D

    Yes, that was exactly what I couldn't get. Thank you for clarifying it for me!

    Hi, I can not see how this is implied... Let m and n be positive integers, with gcd(m, n) = 1. The the system of congruences x = a (mod m) and x = b (mod n ) has a solution. Moreover, any two solutions are congruent modulo mn. pf. Since gcd(m,n) = 1, there exist integers r...
  6. B

    Chinese Remainder Theorem

    This doesn't actually require the use of the CRT, since it actually wants you to sort of derive it for a system of two equations. So while using the CRT will help me solve this fairly quickly and easily, that's not what I'm after Homework Statement Let gcd(m,n)=1. Given integers a,b, show...
  7. K

    Using the Lagrange Remainder Theorem (advanced calc/real analysis)

    Hi everyone. This is my first post here and I was wondering if any of you could help me. The question is to prove that 1 + \frac{x}{3} - \frac{x^2}{9} < (1 + x)^\frac{1}{3} < 1 + \frac{x}{3} if x>0. The question is in a section on the lagrange remainder theorem. The fact that the first...
  8. M

    How can the Polynomial Remainder Theorem be applied in real-life situations?

    I know how the polynomial remainder theorem works but I can't see how knowing this is useful in any way. So I have f(X). I know that if I divide the statement in f(X) by X - a the remainder will be a. How is this useful knowledge though? What can I discover using this principle that I wouldn't...
  9. D

    The Chinese Remainder Theorem (the CRT)

    Find the lowest number that has a remainder of 1 when divided by 2, 2 when divided by 3, 3 when divided by 4, 4 when divided by 5, and 5 when divided by 6. It is possible to solve this by applying the general algorithm that solves Chinese Remainder problems. But, for this special...
  10. C

    Where did the six come from in the Chinese Remainder Theorem?

    I need help making sense of my notes: x congruent 4 mod 11 x congruent 3 mod 13 ai mi Mi yi aiMiyi 4 11 13 6 4*13*6 3 13 11 6 3*11*6 I'm not sure where the six came from
  11. N

    Remainder Theorem with 2 unknowns.

    Homework Statement When rx^3 + gx^2 +4x + 1 is divided by x-1, the remainder is 12. When it is divided by x+3, the remainder is -20. Find the values of r and g. Homework Equations The Attempt at a Solution r=f(1) =r(1)^3 + g(1)^2 + 4(1) +5 =r + g +9 r=12 r+g+9=12 r+g= 3...
  12. E

    Proving C(n,m) is an Integer: Number Theory & Chinese Remainder Theorem?

    Homework Statement How would you prove using number theory that C(n,m) is an integer where n => m =>1? Do you need the Chinese Remainder Theorem? It seems like it should follow easily from what C(n,m) represents but it is hard for me for some reason. Homework Equations The Attempt...
  13. T

    Discrete Mathematics with possible Quotient Remainder Theorem

    Homework Statement For all integers m, m^{}2=5k, or m^{}2=5k+1, or m^{}2=5k+4 for some integer k. Relevant equations I'm pretty sure we have to use the Quotient Remainder THM, which is: Given any integer n and positive integer d, there exists unique integers q and r such that...
  14. mattmns

    Number Theory: Inverse of 0 mod n? Chinese Remainder Theorem

    I am doing a Chinese remainder theorem question and one of the equations is x \equiv 0 (mod 7). This would mean that x is a multiple of 7, but how do I use it in conjunction with the Chinese remainder theorem? Do I just ignore that equation, use the CRT on the rest of the system, and then once...
  15. S

    Find a Degree Three Polynomial with x-2 Remainder of 3 - Hint: Work Backwards!

    Find a polynomial of degree three that when divided by x - 2 has a remainder of 3. You will really have to think on this one. Hint: Work backwards! ok here's the thing I've tried I've looked at other problems but I can barely work problems forward, backwards...well your talking to me here my...
  16. E

    Solve the Remainder Theorem with x^2-4x^2+3

    remainder theorem...? Find the value of 'a' and 'b' and the remaining factor if the expression ax^3-11x^2+bx+3 is divisible by x^2-4x^2+3 do i simplify x^2-4x^2+3 and then substitute for x? im so lostt!
  17. B

    Division with polynomials involving the remainder theorem

    Two questions, first, I solved something, but I was just playing around with the numbers, and I didn't really know what I was doing, nor did I really understand it after I was done. The question is as follows: When x + 2 is divided into f(x), the remainder is 3. Determine the remainder when x...
  18. C

    Chinese Remainder Theorem: A Powerful Tool in Number Theory

    Chinese Remainder Theorem! I'm pretty sure that the following is in fact the Chinese remainder Theorem: If n= (m1)(m2)...(mk) [basically, product of m's (k of them)] where each m is relatively prime in pairs, then there is an isomorphism from Zn to ( Zm1 X Zm2 X ... X Zmk). Zn...
  19. B

    Chinese remainder theorem problem

    I'm having a lot of trouble setting up the equations for the following question where I need to use the chinese remainder theorem. Q. Fifteen pirates steal a stack of identical gold coins. When they try to divide them evenly, two coins are left over. A fight erupts and one of the pirates is...
  20. M

    What is the remainder when x^X^x^x... is divided by x-700^(1/700)?

    whats the remainder when x^X^x^x... is divided by x-700^(1/700) leaving answer in whole number
  21. J

    Inverse chinese remainder theorem

    hi all I am new on the forum I wonder if is possible to find a method that proofs that a number IS NOT a solution of a set of congruences Maybe using the chinese remainder theorem?? best regards japam
Back
Top