{"id":65053,"date":"2025-07-29T10:36:33","date_gmt":"2025-07-29T07:36:33","guid":{"rendered":"https:\/\/wpcalc.com\/en\/?p=65053"},"modified":"2026-09-30T20:21:42","modified_gmt":"2026-09-30T17:21:42","slug":"chinese-remainder-theorem","status":"publish","type":"post","link":"https:\/\/wpcalc.com\/en\/mathematics\/chinese-remainder-theorem\/","title":{"rendered":"Chinese Remainder Theorem Calculator"},"content":{"rendered":"<section class=\"not-prose calculator-box\" aria-labelledby=\"calculator-title\"><div class=\"flex items-baseline sm:items-center justify-between gap-2 sm:gap-3\"><div class=\"flex flex-col sm:flex-row sm:items-center gap-2\"><span class=\"icon icon-calculator text-primary-700! text-base! dark:text-primary-300!\" aria-hidden=\"true\"><\/span><h2 id=\"calculator-title\" class=\"text-lg font-display font-bold\">Chinese Remainder Theorem Solver<\/h2><\/div><div class=\"calcdash-favorite group\">\n  <button type=\"button\" class=\"favorite\" id=\"favorite\" data-favorite-id=\"65053\" data-favorite-title=\"Chinese Remainder Theorem\" data-favorite-url=\"https:\/\/wpcalc.com\/en\/mathematics\/chinese-remainder-theorem\/\" data-favorite-excerpt=\"Solves a system of simultaneous congruences using the Chinese Remainder Theorem. Enter the remainders and pairwise coprime moduli to get the smallest non-negative solution.\" aria-label=\"Add to Favorites\" data-favorite-icon=\"icon icon-arithmetic\">\n    <span class=\"icon icon-shape-star-empty\" aria-hidden=\"true\"><\/span>\n  <\/button>\n  <div class=\"calcdash-favorite__tip\" aria-hidden=\"true\">\n   <span class=\"favorite-tooltip\" id=\"favorite-tooltip\"><\/span>\n  <\/div>\n  <span class=\"sr-only\" role=\"status\" id=\"favorite-status\"><\/span>\n<\/div><\/div><form action=\"https:\/\/wpcalc.com\/en\/mathematics\/chinese-remainder-theorem\/\" method=\"POST\" class=\"calculator\" id=\"calculator-65053\" data-post=\"65053\"><fieldset class=\"fieldset-input\"><legend class=\"sr-only\">Input Fields<\/legend><div class=\"field is-single\" id=\"input-1\"><label for=\"field-1\">Number of congruences<\/label><input type=\"text\" name=\"number_of_congruences\" id=\"field-1\" data-number inputmode=\"decimal\" autocomplete=\"off\" spellcheck=\"false\" min=\"2\" value=\"2\"\/><\/div><div class=\"field has-term\" id=\"input-2\"><label for=\"field-2\">remainder 1<\/label><div class=\"term\">a\u2081<\/div>  <div class=\"absolute bottom-0 left-16 top-8 w-2 h-0.5 bg-blue-500\"><\/div><input type=\"number\" name=\"remainder_1\" id=\"field-2\" step=\"any\" value=\"2\"\/><\/div><div class=\"field has-term\" id=\"input-3\"><label for=\"field-3\">modulus 1<\/label><div class=\"term\">n\u2081<\/div>  <div class=\"absolute bottom-0 left-16 top-8 w-2 h-0.5 bg-blue-500\"><\/div><input type=\"text\" name=\"modulus_1\" id=\"field-3\" data-number inputmode=\"decimal\" autocomplete=\"off\" spellcheck=\"false\" min=\"1\" value=\"3\"\/><\/div><div class=\"field has-term\" id=\"input-4\"><label for=\"field-4\">remainder 2<\/label><div class=\"term\">a\u2082<\/div>  <div class=\"absolute bottom-0 left-16 top-8 w-2 h-0.5 bg-blue-500\"><\/div><input type=\"number\" name=\"remainder_2\" id=\"field-4\" step=\"any\" value=\"3\"\/><\/div><div class=\"field has-term\" id=\"input-5\"><label for=\"field-5\">modulus 2<\/label><div class=\"term\">n\u2082<\/div>  <div class=\"absolute bottom-0 left-16 top-8 w-2 h-0.5 bg-blue-500\"><\/div><input type=\"text\" name=\"modulus_2\" id=\"field-5\" data-number inputmode=\"decimal\" autocomplete=\"off\" spellcheck=\"false\" min=\"1\" value=\"5\"\/><\/div><\/fieldset><div class=\"buttons\"><button type=\"submit\" data-text=\"Re-Calculate\" id=\"calculate-button\" data-post=\"65053\">Calculate<\/button><button type=\"reset\">Reset<\/button><\/div><div class=\"field is-checkbox hidden!\" id=\"field-auto-calc\"><input type=\"checkbox\" id=\"auto-calc\"><label for=\"auto-calc\">Calculate automatically<\/label><small>If enabled, the result will update automatically when you change any value.<\/small><\/div><div class=\"fieldset-result is-hidden\" aria-labelledby=\"result-title\" aria-live=\"polite\" role=\"region\"> <h3 class=\"result-title bg-gradient-to-r from-primary-50 to-gray-50 dark:from-primary-900 dark:to-gray-800\" id=\"result-title\"><span class=\"icon icon-s-pulse\" aria-hidden=\"true\"><\/span> Your Results<\/h3><div class=\"result-box\"><div class=\"field-result\" id=\"output-1\"><span class=\"field-title\"><span>Smallest non-negative solution<\/span><span class=\"result-term\">x<\/span><\/span><span class=\"field-value\" id=\"result-1\"><\/span><button type=\"button\" class=\"copy-result\" data-tooltip=\"Copy Result\" aria-label=\"Copy Result\"><span class=\"copy-icon icon icon-document-copy\" aria-hidden=\"true\"><\/span><\/button><\/div><div class=\"field-result\" id=\"output-2\"><span class=\"field-title\"><span>Modulo (LCM of moduli)<\/span><span class=\"result-term\">N<\/span><\/span><span class=\"field-value\" id=\"result-2\"><\/span><button type=\"button\" class=\"copy-result\" data-tooltip=\"Copy Result\" aria-label=\"Copy Result\"><span class=\"copy-icon icon icon-document-copy\" aria-hidden=\"true\"><\/span><\/button><\/div><\/div><div class=\"result-actions\"><button type=\"button\" class=\"copy-link\"><svg viewBox=\"0 0 20 20\" fill=\"currentColor\" aria-hidden=\"true\"><path d=\"M12.232 4.232a2.5 2.5 0 0 1 3.536 3.536l-1.225 1.224a.75.75 0 0 0 1.061 1.06l1.224-1.224a4 4 0 0 0-5.656-5.656l-3 3a4 4 0 0 0 .225 5.865.75.75 0 0 0 .977-1.138 2.5 2.5 0 0 1-.142-3.667l3-3Z\"\/><path d=\"M11.603 7.963a.75.75 0 0 0-.977 1.138 2.5 2.5 0 0 1 .142 3.667l-3 3a2.5 2.5 0 0 1-3.536-3.536l1.225-1.224a.75.75 0 0 0-1.061-1.06l-1.224 1.224a4 4 0 1 0 5.656 5.656l3-3a4 4 0 0 0-.225-5.865Z\"\/><\/svg><span class=\"copy-link__text\">Copy link to this calculation<\/span><\/button><span class=\"sr-only\" role=\"status\" id=\"copy-link-status\"><\/span><\/div><\/div><a href=\"#respond\" class=\"hidden transition-opacity duration-300 opacity-0 w-50 text-sm justify-center items-center gap-2 px-4 py-2 rounded bg-gray-200 text-gray-700 hover:bg-gray-300\" id=\"leave-comment\"><span class=\"icon icon-comments\" aria-hidden=\"true\"><\/span>Leave a Comment<\/a><\/form><\/section><section id=\"calc-reactions\" class=\"not-prose hidden my-12 bg-gradient-to-r from-primary-50 to-gray-50 border border-indigo-100 rounded-xl px-6 py-4 shadow-sm\" data-post=\"65053\" aria-live=\"polite\" aria-labelledby=\"calc-reactions-title\"><p id=\"calc-reactions-title\" class=\"text-sm text-gray-500 text-center mb-2\">How did this result make you feel?<\/p><div role=\"group\" aria-labelledby=\"calc-reactions-title\" class=\"grid grid-cols-3 sm:flex sm:flex-row sm:justify-around gap-4 sm:items-center sm:flex-wrap\"><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"like\"><span class=\"reaction-count\" data-reaction-count=\"like\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\ude00 <\/span><span class=\"reaction-description font-medium\">Like <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"helpful\"><span class=\"reaction-count\" data-reaction-count=\"helpful\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\udca1 <\/span><span class=\"reaction-description font-medium\">Helpful <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"confused\"><span class=\"reaction-count\" data-reaction-count=\"confused\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\ude15 <\/span><span class=\"reaction-description font-medium\">Confused <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"disappointed\"><span class=\"reaction-count\" data-reaction-count=\"disappointed\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\ude1e <\/span><span class=\"reaction-description font-medium\">Disappointed <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"inaccurate\"><span class=\"reaction-count\" data-reaction-count=\"inaccurate\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\u274c <\/span><span class=\"reaction-description font-medium\">Inaccurate <\/span><\/button><\/div><div id=\"reaction-message\" class=\"hidden mt-8 rounded-md border border-primary-100 bg-white\/50 backdrop-blur-sm px-4 py-2 text-sm text-center shadow-sm\"><\/div><\/section><div class=\"calcdash-ad not-prose calcdash-ad--calc_result calcdash-ad--in-article\"><ins class=\"adsbygoogle\" style=\"display:block\" data-ad-client=\"ca-pub-1721569815777345\" data-ad-slot=\"6317458308\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\"><\/ins><script>(adsbygoogle = window.adsbygoogle || []).push({});<\/script><\/div>\n<style id=\"wpcoderpro-inline-1\">.formula-box {\r\n\tborder-bottom: none !important;\r\n}<\/style><section class=\"formula-box\" aria-labelledby=\"formula-title\">\r\n\t<div id=\"formula-title\" class=\"not-prose font-display mb-4\"><span class=\"icon icon-formula\" aria-hidden=\"true\"><\/span><h2>Chinese Remainder Theorem Formula<\/h2><\/div>\r\n\t<figure class=\"not-prose formula\">\r\n\t\t<figcaption class=\"formula-title\">Formula<\/figcaption>\r\n\t\t<div class=\"text-base text-gray-800\" id=\"formula\">\n\\[ x \\equiv a_1 \\pmod{n_1} \\\\ x \\equiv a_2 \\pmod{n_2} \\\\ \\vdots \\\\ x \\equiv a_k \\pmod{n_k} \\\\[1.5em] N = n_1 \\cdot n_2 \\cdots n_k, \\quad N_i = \\frac{N}{n_i}, \\quad y_i \\equiv N_i^{-1} \\pmod{n_i} \\\\[1.5em] x \\equiv \\sum_{i=1}^{k} a_i \\, N_i \\, y_i \\pmod{N} \\]\n<\/div>\r\n\t<\/figure>\r\n\t<\/p>\n<p><strong>Where:<\/strong><\/p>\n<ul>\n<li>\\(a_i\\) \u2014 the remainders (the values \\(x\\) must be congruent to)<\/li>\n<li>\\(n_i\\) \u2014 the moduli, which must be pairwise coprime (their greatest common divisor is 1 for any two of them)<\/li>\n<li>\\(N\\) \u2014 the product of all moduli, which equals their least common multiple when they are coprime<\/li>\n<li>\\(N_i\\) \u2014 the product of all moduli except \\(n_i\\)<\/li>\n<li>\\(y_i\\) \u2014 the modular inverse of \\(N_i\\) modulo \\(n_i\\), i.e. the number with \\(N_i y_i \\equiv 1 \\pmod{n_i}\\)<\/li>\n<li>\\(x\\) \u2014 the unique solution modulo \\(N\\)<\/li>\n<\/ul>\n<p>The theorem states that when the moduli are pairwise coprime, the system has exactly one solution in the range \\(0 \\le x &lt; N\\). The formula builds this solution by combining each remainder with the inverse of the corresponding partial product.<\/p>\n<p>\r\n<\/section>\n<style id=\"wpcoderpro-inline-459\">.calculation-box {\r\n\tborder-bottom: none !important;\r\n}<\/style><section id=\"calculation\" class=\"calculation-box\" aria-labelledby=\"calculation-title\">\r\n\t<div id=\"calculation-title\" class=\"not-prose font-display\"><span class=\"icon icon-unordered-list\" aria-hidden=\"true\"><\/span><h2>Chinese Remainder Theorem \u2013 Calculation Example<\/h2><\/div>\r\n\r\n<\/p>\n<p><strong>Example:<\/strong> find \\(x\\) such that \\(x \\equiv 2 \\pmod{3}\\) and \\(x \\equiv 3 \\pmod{5}\\) \u2014 these are the calculator's default values.<\/p>\n<p>\\[ N = 3 \\times 5 = 15 \\]<\/p>\n<p>\\[ N_1 = \\frac{15}{3} = 5, \\quad y_1 = 2 \\; (\\text{since } 5 \\cdot 2 = 10 \\equiv 1 \\pmod{3}) \\]<\/p>\n<p>\\[ N_2 = \\frac{15}{5} = 3, \\quad y_2 = 2 \\; (\\text{since } 3 \\cdot 2 = 6 \\equiv 1 \\pmod{5}) \\]<\/p>\n<p>\\[ x \\equiv (2 \\cdot 5 \\cdot 2) + (3 \\cdot 3 \\cdot 2) \\pmod{15} \\equiv 20 + 18 = 38 \\equiv 8 \\pmod{15} \\]<\/p>\n<p><strong>Result:<\/strong> \\(x = 8\\) modulo \\(15\\). Indeed, \\(8 \\div 3 = 2\\) remainder \\(2\\) and \\(8 \\div 5 = 1\\) remainder \\(3\\), so both congruences hold. The next solution is \\(8 + 15 = 23\\), then \\(38\\), and so on.<\/p>\n<p>\n\r\n<\/section>\n<h2>How to Use the Calculator<\/h2>\n<ol>\n<li>Enter the <strong>Number of congruences<\/strong> (at least 2). More remainder\/modulus pairs appear automatically.<\/li>\n<li>For the first congruence, type the remainder into <strong>remainder 1<\/strong> (\\(a_1\\)) and the modulus into <strong>modulus 1<\/strong> (\\(n_1\\)).<\/li>\n<li>Repeat for <strong>remainder 2<\/strong> \/ <strong>modulus 2<\/strong> and any additional pairs.<\/li>\n<li>Read the <strong>Smallest non-negative solution<\/strong> \\(x\\) and the <strong>Modulo (LCM of moduli)<\/strong> \\(N\\). Every number of the form \\(x + kN\\) (\\(k = 0, 1, 2, \\dots\\)) also satisfies the system.<\/li>\n<\/ol>\n<h2>What Is the Chinese Remainder Theorem?<\/h2>\n<p>The Chinese Remainder Theorem (CRT) is a classical result in number theory, first described by the Chinese mathematician Sunzi around the 3rd\u20135th century CE. It answers the question: given several divisors and the remainders left after dividing an unknown number by each of them, can the number be recovered? The theorem says yes \u2014 provided the moduli are pairwise coprime \u2014 and the answer is unique within a range whose length is the product of all the moduli.<\/p>\n<p>A concrete way to picture it: if an egg basket holds \\(x\\) eggs, and counting them 3 at a time leaves 2, while counting 5 at a time leaves 3, then \\(x \\equiv 2 \\pmod{3}\\) and \\(x \\equiv 3 \\pmod{5}\\). The CRT pins \\(x\\) down uniquely modulo 15 \u2014 in this case \\(x = 8, 23, 38, \\dots\\)<\/p>\n<p>The theorem matters because it shows that a system of many small congruences is equivalent to one congruence with a large modulus. This lets you replace arithmetic with a huge modulus by parallel arithmetic with several small, convenient moduli, then recombine the results. The recombination step uses modular inverses, which you can compute separately with the <a href=\"https:\/\/wpcalc.com\/en\/mathematics\/multiplicative-inverse-modulo\/\">Multiplicative Inverse Modulo calculator<\/a>; inverses of this kind are also related to <a href=\"https:\/\/wpcalc.com\/en\/mathematics\/fermats-little-theorem\/\">Fermat's Little Theorem<\/a> and <a href=\"https:\/\/wpcalc.com\/en\/mathematics\/eulers-theorem\/\">Euler's Theorem<\/a>.<\/p>\n<h2>Interpreting the Result<\/h2>\n<p>The calculator returns the smallest non-negative solution \\(x\\) and the combined modulus \\(N\\). The full solution set is \\(x, x + N, x + 2N, \\dots\\), and if negative answers make sense in your problem, \\(x - N\\) and smaller values work too. Because the solution is unique modulo \\(N\\), two different inputs that produce the same \\(x \\pmod{N}\\) describe exactly the same system.<\/p>\n<h2>Assumptions and Limitations<\/h2>\n<ul>\n<li><strong>Pairwise coprime moduli are required.<\/strong> Every pair of moduli must share no common factor greater than 1; otherwise the calculator reports an error. If two moduli are, say, 4 and 6 (both divisible by 2), the system may have no solution at all, or several solutions modulo their LCM.<\/li>\n<li><strong>Consistency of the system.<\/strong> Even with coprime moduli the theorem always gives a solution \u2014 that is the strength of the CRT. Conflicts between congruences can only arise when the coprimality condition is broken.<\/li>\n<li><strong>Remainders may exceed the modulus.<\/strong> An input like \\(a = 7, n = 5\\) is treated as \\(7 \\equiv 2 \\pmod 5\\); the calculator reduces the final answer modulo \\(N\\) automatically.<\/li>\n<li><strong>Moduli must be positive integers.<\/strong> Values of 0 or negative numbers are rejected.<\/li>\n<li><strong>Large systems.<\/strong> Because \\(N\\) is the product of all moduli, it grows very quickly. With many moduli, the numbers involved can exceed the range where standard floating-point arithmetic is exact.<\/li>\n<\/ul>\n<h2>Where the CRT Is Used<\/h2>\n<p>Beyond pure number theory, the CRT is a working tool in several fields. In cryptography it speeds up RSA decryption by computing the result modulo each prime factor separately and recombining; it also underpins threshold schemes such as Shamir's Secret Sharing. In computer science, it enables residue number systems that perform additions and multiplications in parallel on small moduli, and it appears in hashing, scheduling, and calendar calculations \u2014 the classic \"counting soldiers by rows\" problems that originally motivated Sunzi's work.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Solves a system of simultaneous congruences using the Chinese Remainder Theorem. Enter the remainders and pairwise coprime moduli to get the smallest non-negative solution.<\/p>\n","protected":false},"author":3168,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[7],"tags":[72],"class_list":["post-65053","post","type-post","status-publish","format-standard","hentry","category-mathematics","tag-arithmetic-calculators"],"acf":[],"_links":{"self":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/65053","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/users\/3168"}],"replies":[{"embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/comments?post=65053"}],"version-history":[{"count":4,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/65053\/revisions"}],"predecessor-version":[{"id":66210,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/65053\/revisions\/66210"}],"wp:attachment":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/media?parent=65053"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/categories?post=65053"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/tags?post=65053"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}