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. M

    Finding Integer with Chinese Remainder Theorem

    Consider a certain integer between ## 1 ## and ## 1200 ##. Then ## x\equiv 1\pmod {9}, x\equiv 10\pmod {11} ## and ## x\equiv 0\pmod {13} ##. Applying the Chinese Remainder Theorem produces: ## n=9\cdot 11\cdot 13=1287 ##. This means ## N_{1}=\frac{1287}{9}=143, N_{2}=\frac{1287}{11}=117 ## and...
  2. chwala

    Use Remainder theorem to find factors of ##(a-b)^3+(b-c)^3+(c-a)^3##

    My first approach; ##(a-b)^3+(b-c)^3+(c-a)^3=a^3-3a^2b+3ab^2-b^3+b^3-3b^2c+3bc^2-c^3+c^3-3c^2a+3ca^2-a^3## ##=-3a^2b+3ab^2-3b^2c+3bc^2-3c^2a+3ca^2## what i did next was to add and subtract ##3abc## ...just by checking the terms ( I did not use...
  3. chwala

    Factor and remainder theorem problem

    ##0=1+a+b+c## ##20=8+4a+2b+c## it follows that, ##13=3a+b## and, ##0=k^3+ak^2+bk+c##...1 ##0=(k+1)^3+a(k+1)^2+(k+1)b+c##...2 subtracting 1 and 2, ##3k^2+k(3+2a)+14-2a=0##
  4. V

    MHB How to solve Chinese Remainder Theorem

    Dear How to solve the CRT for cryptography as below - (1) Find x such that x = 2(mod3) x = 5(mod9) x = 7(mod11) (2) Find x such that x = 2(mod3) x = 4(mod7) x = 5(mod11) (3) Find x such that x^2 = 26(mod77) (4) Find x such that x^2 = 38(mod77) Please help me by provide your advice and...
  5. F

    Chinese remainder theorem (CRT) question, flat shapes

    Homework Statement By hand, find the 4 square roots of 340 mod 437. (437 = 23 * 19). Homework Equations Chinese remainder theorem (CRT) The Attempt at a Solution So this is the wrong way I did it was first I solved ##x^2 \equiv 340 (\operatorname{mod} 19)## and ##x^2 \equiv 340...
  6. F

    Chinese Remainder theorem for 2 congruences

    Homework Statement Let ##a, b, m, n## be integers with ##\gcd(m,n) = 1##. Let $$c \equiv (b-a)\cdot m^{-1} (\operatorname{mod} n)$$ Prove that ##x = a + cn## is a solution to ##x \equiv a (\operatorname{mod} m)## and ##x \equiv b (\operatorname{mod} n)##, (2.24). and that every solution to...
  7. S

    MHB About a variant of the Chinese Remainder Theorem

    Let $m$ and $m'$ be positive integers, and $d=gcm(m,m')$. (i) The system: $x \equiv b (mod \ m)$ $x \equiv b' (mod \ m')$ has a solution if and only if $b \equiv b' (mod \ d)$ (ii) two solutions of the system are congruent $mod \ l$, where $l = lcm(m,m')$. I can prove part (i), but can...
  8. J

    Understanding the Remainder Theorem for Polynomial Division

    Homework Statement What is the remainder when -3x^3 + 5x - 2 is divided by x? The Attempt at a Solution Not sure how to complete this one, I would assume that it is the same as x+0? How would you divide the last term, (-2). Please show your steps as this will help me a lot! Thanks!
  9. Schaus

    Using Remainder Theorem to find remainder

    Homework Statement (y4 - 5y2 + 2y - 15) / (3y - √(2)) The answer says (2√(2)/3)-(1301/81)...
  10. FritoTaco

    Long Division and Remainder Theorem

    NO TEMPLATE BECAUSE MOVED FROM ANOTHER FORUM Hello, I've been trying to figure out how it works for complicated problems, I know how to use long division, but I'm not understanding how this process is done for a problem like I have. Instructions: Write the function in the form ƒ(x) = (x -...
  11. S

    A tricky remainder theorem problem

    Homework Statement A polynomial P(x) is divided by (x-1), and gives a remainder of 1. When P(x) is divided by (x+1), it gives a remainder of 3. Find the remainder when P(x) is divided by (x^2 - 1) Homework Equations Remainder theorem The Attempt at a Solution I know that P(x) = (x-1)A(x) +...
  12. terryds

    What is the remainder when polynomial f(x) is divided by x^3-x?

    Homework Statement [/B] Polynomial f(x) is divisible by ##x^2-1##. If f(x) is divided by ##x^3-x##, then the remainder is... A. ##(x^2-x)f(-1)## B. ##(x-x^2)f(-1)## C. ##(x^2-1)f(0)## D. ##(1-x^2)f(0)## E. ##(x^2+x)f(1)## Homework Equations Remainder theorem The Attempt at a Solution [/B]...
  13. NoName3

    MHB Understanding the Chinese Remainder Theorem for $\mathbb{Z}^{\times} _{20}$

    How do I show that $\mathbb{Z}^{\times} _{20} ≅ \mathbb{Z}_{2} \times \mathbb{Z}_{4}$? I read that the chinese remainder theorem is the way to go but there are many versions and I can't find the right one. Most versions that I have found are statements between multiplicative groups, not from...
  14. T

    MHB What is meant by the unique integers Q and R in the quotient remainder theorem?

    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$$. When is says that $$Q$$ and $$R$$ are unique, what does that mean? That they are different from each other?
  15. T

    MHB Quotient remainder theorem problem.

    For any int $$n $$ , prove that $$ 4 | n (n^2 - 1) (n + 2)$$. I know I have to use the quotient remainder theorem, but I'm wondering how to go about this problem. I'm not sure how to phrase this problem in English.
  16. Julio1

    MHB Problem Chinese remainder Theorem

    Find the set of solutions $x=x(r,s,t)$ such that $(r+2\mathbb{N})\cap (s+3\mathbb{N})\cap (t+5\mathbb{N})=x+n\mathbb{N}.$ Hello MHB :). Any hints for the problem?
  17. Julio1

    MHB Can $\varphi$ be used to prove the Chinese remainder theorem?

    Show that if $\text{gcd}(b,c)=1$, then $\forall r,s\in \mathbb{N}, \exists x\in \{1,...,bc\}$ such that $x\in (r+b\mathbb{N})\cap (s+c\mathbb{N}).$ Hello :). Can define an function $\varphi: \{1,...,bc\}\to \mathbb{Z}/b\mathbb{Z}\times \mathbb{Z}/c\mathbb{Z}$ at follow $x\mapsto ([x]_b,[x]_c)$...
  18. M

    How can the Lagrange remainder theorem be applied to series with skipped terms?

    I have a few questions about the remainder theorem. 1: For series that "skip" terms (example: 1+x^2+x^4+x^6) the theorem says the n+1 derivative and x^(n+1)/(n+1)!. For example if you have 1 + x^2 where you know the next term would be x^4 you could treat it as a third order or a...
  19. B

    Points of Convergence for Lagrange Remainder Theorem

    Homework Statement At what points ##x## in the interval ##(-1,1]## can one use the Lagrange Remainder Theorem to verify the expansion ##ln(1+x)=\sum_{k=1}^{\infty} (-1)^{k+1}{\frac{x^k}{k!}}##Homework Equations The Attempt at a Solution Now I know that ##ln(1+x)=\sum_{k=1}^{\infty}...
  20. J

    MHB Remainder theorem questions

    Q2.) Show all working out. a) Find the remainder when x^3+2x^2-5x-3 is divided by x-2. b) Find the remainder when x^3-3x^2-x+3 is divided by x-3.
  21. J

    MHB Factor and remainder theorem question

    Q1.) Use the factor and remainder theorems to find solutions to: 1x^3+1x^2+-9x+D=0
  22. A

    Solving Polynomial Remainders

    Homework Statement Find each remainder: a. (x^3 + 5x^2 - 7x + 1) ÷ (x+2)(x-1)b. (2x^3 + x^2 - 4x - 2) ÷ (x^2 + 4x + 3)Homework Equations N/A. (We've used Long Division and Synthetic Division for previous questions.) The Attempt at a Solution How would i go about solving these? I'm pretty stuck.
  23. F

    Remainder Theorem Thinking Question

    Homework Statement When a polynomial is divided by (x+2), the remainder is -19. When the same polynomial is divided by (x-1), the remainder is 2. Determine the remainder when the polynomial is divided by (x-1)(x+2)Homework Equations The Attempt at a Solution had the polynomial been a real...
  24. matqkks

    What are some practical applications of the Chinese Remainder Theorem?

    What is the most tangible way to introduce the Chinese Remainder Theorem? What are the practical and really interesting examples of this theorem. I am looking for examples which have a real impact on students.
  25. matqkks

    MHB How Can the Chinese Remainder Theorem Be Applied to Diophantine Equations?

    Chinese Remainder Theorem What is the most tangible way to introduce the Chinese Remainder Theorem? What are the practical and really interesting examples of this theorem. I am looking for examples which have a real impact on students.
  26. M

    Extended euclidean algorithm and Chinese Remainder theorem

    Homework Statement Solve x \cong 1 mod 7 x \cong 4 mod 6 x \cong 3 mod 5 by (and I have to use this method) using Euclidean algorithm to find the largest common divisor, then the extended euclidean algorithm to find a linear combination, then a solution to each of the three...
  27. S

    Question on remainder theorem

    Homework Statement If a , b, c are distinct and p(x) is a polynomial in x which leaves remainders a,b,c on division by (x-a),(x-b),(x-c) respectively. Then the remainder on division of p(x) by(x-a)(x-b)(x-c) is Homework Equations As it is given that p(x) gives remainder a when divided by...
  28. S

    Applying Chinese Remainder Theorem to polynomials

    Homework Statement Find all integers x such that 7x \equiv 11 mod 30 and 9x \equiv 17 mod 25 Homework Equations I guess the Chinese Remainder theorem and Bezout's theorem would be used here. The Attempt at a Solution I can do this if the x-terms didn't have a...
  29. E

    Generalization of Chinese Remainder Theorem

    Is there a generalization for the Chinese Remainder Theorem if the modular bases are not coprime? Or even to some extent, if the modular bases are increasing by the same common ratio? I searched it up but could not find anything.
  30. R

    (Z/10557Z)* as Abelian Groups using Chinese Remainder Theorem

    If I was to try to work this out I would use the Chinese Remainder Theorem and since 10557 = 3^3 . 17 . 23 end up with (Z/10557Z)* isomorphic to (Z/27Z)* x (Z/17Z)* x (Z/23Z)* isomorphic to C18 x C16 x C22 where Cn represents the Cyclic group order n. How would I then write this as Cn1 x Cn2...
  31. M

    Number theory: ( remainder theorem.)

    Homework Statement A) Find the remainder of 2^n and 3^n when divided by 5. B)Conclude the remainder of 2792^217 when divided by 5. C)solve in N the following : 1) 7^n+1 Ξ 0(mod5) 2) 2^n+3^n Ξ 0(mod5) The Attempt at a SolutionA) I know that for the first two I have to get 2^n=5k+r and...
  32. S

    Taylor Series Remainder Theorem

    1. Prove that the MacLaurin series for cosx converges to cosx for all x. Homework Equations Ʃ(n=0 to infinity) ((-1)^n)(x^2n)/((2n)!) is the MacLaurin series for cosx |Rn(x)|\leqM*(|x|^(n+1))/((n+1)!) if |f^(n+1)(x)|\leqM lim(n->infinity)Rn=0 then a function is equal to its Taylor series...
  33. I

    Mod or quotient remainder theorem (QRT)

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

    Remainder theorem question - combine divisor

    Homework Statement when f(x) is divided by (x+1), remainder is -9; when f(x) is divided by (x-3), remainder is -1; what is the remainder if f(x) is divided by (x+1)(x-3)? Homework Equations f(x) = divider * q(x) + remainder The Attempt at a Solution f(x) = (x+1) * a(x) -9 f(x) =...
  35. S

    Chinese Remainder Theorem on large exponents

    Say I have a^27,654,321 modulo 100,000,000 (where Euler's Theorem no longer helps because totient(100,000,000) = 40,000,000 which is larger than my exponent). How do I use the Chinese Remainder Theorem here to shrink down my massive a^b term I have here? It seems like I need to first split up...
  36. C

    Remainder Theorem and Error Help Why are these 2 examples different?

    So we had two examples in class, but I don't understand why they're different. And the professor is away today, which means I won't see him until the entire weekend has passed (a nightmare for students like me who obsess over a problem). 1. For which x is the approximation sin(x) ≈ x - (x^3)/6...
  37. S

    Analysis problem using the Lagrange Remainder Theorem

    Homework Statement Prove that for every pair of numbers x and h, \left|sin\left(x+h\right)-\left(sinx+hcosx\right)\right|\leq\frac{h^{2}}{2} The Attempt at a Solution Let f(x)= \left|sin\left(x+h\right)-\left(sinx-hcosx\right)\right|? and then to center the taylor polynomial around 0...
  38. P

    Chinese Remainder Theorem (I think?)

    Given system of congruences, x^3 \equiv y_1 \mod n_1 x^3 \equiv y_2 \mod n_2 x^3 \equiv y_3 \mod n_3 You are given y_1, y_2, y_3, n_1, n_2, n_3. The n_i's are pairwise relatively prime. Solve for x. I think there might be a connection between the fact that the exponent of x is 3 and...
  39. F

    Topology and the Chinese Remainder Theorem?

    Is there anywhere in topology where one would see the Chinese Remainder Theorem?
  40. Z

    Remainder theorem only works with quadratics divided by linear?

    Homework Statement The remainder theorem can't really be applied when dividing by something other than a linear equation since you wouldn't know what a is, right? Homework Equations The Attempt at a Solution
  41. M

    Chinese Remainder Theorem

    Homework Statement Find a satisfying a 1 (mod 2), a 2 (mod 3), with 0 < a < 6 Begin with the Mod 2 calculation Homework Equations The Attempt at a Solution I found that U1=3 and U2=4, but then it says "Now take the appropriate linear combination of {U1, U2} to...
  42. J

    Find and Test Primes using the Chinese Remainder Theorem and Binary Search

    The Chinese remainder theorem tells us that the system of equations: \begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align} Uniquely determines all numbers in the range: X<N=n_1n_2\ldots n_k and that all solutions are...
  43. F

    Finding value of polynomial using the remainder theorem

    Homework Statement Find the indicated value of the polynomial using the Remainder Theorem p(x)=2x^3-2x^2+11x-100; find p(3) Homework Equations p(x)=2x^3-2x^2+11x-100 The Attempt at a Solution Synthetic division 3] 2 -2 11 -100 6 12 69 2 4 23 [-31 answer: p(3)=-31 im not...
  44. C

    Chinese Remainder Theorem, Solving For Multiplicative Inverses

    So I am working on solving sets of linear congruence with the chinese remainder theorem. When I go to solve for the inverses I am meeting a bit of trouble. What do I do when the a term is larger that m? Example 77x=1(mod3) 33y=1(mod7) 21z=1(mod11) where x,y,z are the inverses I am trying...
  45. R

    Chinese remainder theorem

    (a) Let R and S be rings with groups of units R∗ and S ∗ respectively. Prove that (R × S)∗ = R∗ × S ∗ . (b) Prove that the group of units of Zn consists of all cosets of k with k coprime to n. Denote the order of (Zn )∗ by φ(n); this is Euler’s φ-function. (c) Now suppose that m and n are...
  46. F

    Mac Series f(x)=sinh (x), remainder theorem help

    Homework Statement (a)Use Definition 10.8.1 to find the Maclaurin series for f(x) = sinh x. Express your answer using Σ notation. (b) Find the interval of convergence for the series found in part (a). (c) Use the Remainder Theorems 10.7.4 and 10.9.2 to show that the series found in part (a)...
  47. A

    The Chinese Remainder Theorem for moduli that aren't relatively prime

    Hello, I am looking into proving that the Chinese Remainder Theorem will work for two pairs of congruences IFF a congruent to b modulo(gcd(n,m)) for x congruent to a mod(n) and x congruent to b mod(m). I have gotten one direction, that given a solution to the congruences mod(m*n), then a...
  48. S

    Finding the Lagrange Remainder Theorem from the Integral Form of a Taylor Series

    Homework Statement I am looking for some help in finding the Lagrange Remainder Theorem from the integral form of the remainder of a Taylor series Homework Equations Integral form of Taylor Series: Rn,a(x) = x∫a [f(n+1)(t)]/n! *(x-t)dt The Attempt at a Solution We are given the...
  49. A

    Proof of the Remainder Theorem: Is this proof of the Remainder Theorem valid?

    Homework Statement Prove that for any polynomial function f and number a, there exists a polynomial function g and number b such that: f(x) = (x-a)g(x) + b Homework Equations N/A The Attempt at a Solution Proof: Let P(n) be the statement that for some natural number n, f(x) =...
  50. S

    The Remainder Theorem and The Factor Theorem

    Homework Statement I understand How to do The remainder Theorem and The factor Theorem but I don't understand what they mean or what they are doing. I don't think I will be able to apply them without knowing what they mean. Can someone explain them to me? Homework Equations The...
Back
Top