{"id":65053,"date":"2025-07-29T10:36:33","date_gmt":"2025-07-29T07:36:33","guid":{"rendered":"https:\/\/wpcalc.com\/en\/?p=65053"},"modified":"2025-07-29T10:36:33","modified_gmt":"2025-07-29T07:36:33","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 class=\"text-lg font-display font-bold\">Chinese Remainder Theorem Solver<\/h2><\/div><div class=\"relative group inline-block\">\n  <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=\"This calculator solves systems of simultaneous congruences using the Chinese Remainder Theorem (CRT). It is useful for students and professionals in number theory, cryptography, and modular arithmetic applications.\" aria-label=\"Add to Favorites\" data-favorite-icon=\"icon icon-arithmetic\">\n    <span class=\"icon icon-shape-star-empty\"><\/span>\n  <\/button>\n  <div class=\"absolute right-full -translate-y-1\/2 top-1\/2 mr-2 w-max max-w-xs px-3 py-2 bg-gray-800 text-white text-xs rounded shadow-lg opacity-0 group-hover:opacity-100 transition-opacity duration-200 z-10 pointer-events-none\">\n   <span class=\"favorite-tooltip\" id=\"favorite-tooltip\"><\/span>\n  <\/div>\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=\"number\" name=\"number_of_congruences\" id=\"field-1\" min=\"2\" step=\"1\" 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=\"number\" name=\"modulus_1\" id=\"field-3\" min=\"1\" step=\"any\" 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=\"number\" name=\"modulus_2\" id=\"field-5\" min=\"1\" step=\"any\" 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 class=\"copy-result\" data-tooltip=\"Copy Result\"><span class=\"copy-icon icon icon-document-copy\"><\/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 class=\"copy-result\" data-tooltip=\"Copy Result\"><span class=\"copy-icon icon icon-document-copy\"><\/span><\/button><\/div><\/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\"><h2 class=\"text-sm text-gray-500 text-center mb-2\">How did this result make you feel?<\/h2><div class=\"grid grid-cols-3 sm:flex sm:flex-row sm:justify-around gap-4 sm:items-center sm:flex-wrap\"><button 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\">\ud83d\ude00 <\/span><span class=\"reaction-description font-medium\">Like <\/span><\/button><button 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\">\ud83d\udca1 <\/span><span class=\"reaction-description font-medium\">Helpful <\/span><\/button><button 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\">\ud83d\ude15 <\/span><span class=\"reaction-description font-medium\">Confused <\/span><\/button><button 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\">\ud83d\ude1e <\/span><span class=\"reaction-description font-medium\">Disappointed <\/span><\/button><button 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\">\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><ins class=\"adsbygoogle\"\n     style=\"display:block; text-align:center; margin: 32px 0;\"\n     data-ad-layout=\"in-article\"\n     data-ad-format=\"fluid\"\n     data-ad-client=\"ca-pub-1721569815777345\"\n     data-ad-slot=\"6317458308\"><\/ins>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script>\n<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>Formula of the Chinese Remainder Theorem Calculator<\/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\\[\nx \\equiv a_1 \\pmod{m_1} \\\\\nx \\equiv a_2 \\pmod{m_2} \\\\\n\\vdots \\\\\nx \\equiv a_k \\pmod{m_k} \\\\[1.5em]\nM = m_1 \\cdot m_2 \\cdots m_k \\\\\nM_i = \\frac{M}{m_i}, \\quad y_i \\equiv M_i^{-1} \\pmod{m_i} \\\\[1.5em]\nx \\equiv \\sum_{i=1}^{k} a_i \\cdot M_i \\cdot y_i \\pmod{M}\n\\]\n<\/div>\r\n\t<\/figure>\r\n\t<br \/>\n<strong>Where:<\/strong><\/p>\n<ul>\n<li>$$a_i$$ are the remainders<\/li>\n<li>$$m_i$$ are pairwise coprime moduli<\/li>\n<li>$$M$$ is the product of all $$m_i$$<\/li>\n<li>$$M_i$$ is $$M$$ divided by $$m_i$$<\/li>\n<li>$$y_i$$ is the modular inverse of $$M_i \\mod m_i$$<\/li>\n<li>$$x$$ is the unique solution modulo $$M$$<\/li>\n<\/ul>\n<p>\r\n<\/section>\n<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<strong><br \/>\nGiven:<\/strong><\/p>\n<ul>\n<li>\\( x \\equiv 2 \\mod 3 \\)<\/li>\n<li>\\( x \\equiv 3 \\mod 5 \\)<\/li>\n<li>\\( x \\equiv 2 \\mod 7 \\)<\/li>\n<\/ul>\n<p><strong>Steps:<\/strong><\/p>\n<ol>\n<li>$$M = 3 \\times 5 \\times 7 = 105$$<\/li>\n<li>$$M_1 = \\frac{105}{3} = 35 \\quad\\Rightarrow\\quad y_1 = 2 \\quad (\\text{since } 35 \\cdot 2 \\equiv 1 \\mod 3)$$<\/li>\n<li>$$M_2 = \\frac{105}{5} = 21 \\quad\\Rightarrow\\quad y_2 = 1 \\quad (\\text{since } 21 \\cdot 1 \\equiv 1 \\mod 5)$$<\/li>\n<li>$$M_3 = \\frac{105}{7} = 15 \\quad\\Rightarrow\\quad y_3 = 1 \\quad (\\text{since } 15 \\cdot 1 \\equiv 1 \\mod 7)$$<\/li>\n<li>$$x \\equiv (2 \\cdot 35 \\cdot 2 + 3 \\cdot 21 \\cdot 1 + 2 \\cdot 15 \\cdot 1) \\mod 105$$<\/li>\n<li>$$x \\equiv (140 + 63 + 30) \\mod 105 = 233 \\mod 105 = 23$$<\/li>\n<\/ol>\n<p><strong>\\( \\boxed{x \\equiv 23 \\mod{105}} \\)<\/strong><\/p>\n<p>\n\r\n<\/section>\n<p>The Chinese Remainder Theorem provides a method for solving systems of modular equations with pairwise coprime moduli. It has applications in cryptography (RSA, Shamir\u2019s secret sharing), computer algebra systems, and algorithm optimization. This calculator automates the full solution using modular inverses.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This calculator solves systems of simultaneous congruences using the Chinese Remainder Theorem (CRT). It is useful for students and professionals in number theory, cryptography, and modular arithmetic applications.<\/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":3,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/65053\/revisions"}],"predecessor-version":[{"id":65056,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/65053\/revisions\/65056"}],"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}]}}