{"id":37565,"date":"2025-06-26T02:35:23","date_gmt":"2025-06-26T02:35:23","guid":{"rendered":"https:\/\/gaviki.com\/blog\/?p=37565"},"modified":"2025-06-26T02:35:25","modified_gmt":"2025-06-26T02:35:25","slug":"finding-multiplicative-inverses-modulo-n","status":"publish","type":"post","link":"https:\/\/gaviki.com\/blog\/finding-multiplicative-inverses-modulo-n\/","title":{"rendered":"Finding Multiplicative Inverses Modulo n"},"content":{"rendered":"\n<p>(Finding Multiplicative Inverses Modulo n; The Extended Euclidean Algorithm) Recall that e Zn has a multiplicative inverse if and only if gcd(a,n) = 1. Moreover, by Theorem 1.4, if gcd(a,n) = 1, then there exist integers r, s \u00e2\u201a\u00ac Z such that ar + ns = 1. Reducing modulo n, we have that ar + ns = 1 (mod n). But ns = 0 (mod n), so ar = 1 (mod n). Therefore, we may use the Extended Euclidean Algorithm to find the numbers r and s such that ar + ns = 1, and by the above argument, (reduced modulo n) will be the multiplicative inverse of a in Zn. Using the above argument, find the multiplicative inverse of 14 \u00e2\u201a\u00ac Z3.<\/p>\n\n\n\n<p><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-cyan-blue-color\">The Correct Answer and Explanation is:<\/mark><\/strong><\/p>\n\n\n\n<p>To find the multiplicative inverse of 14 in <strong>\u2124\u2083<\/strong>, we need to determine a number <strong>r<\/strong> such that:<\/p>\n\n\n\n<p><strong>14r \u2261 1 (mod 3)<\/strong><\/p>\n\n\n\n<p>This means that the product of 14 and <strong>r<\/strong>, when divided by 3, leaves a remainder of 1. But first, we must check whether 14 has a multiplicative inverse modulo 3. A number <strong>a<\/strong> has an inverse modulo <strong>n<\/strong> if and only if <strong>gcd(a, n) = 1<\/strong>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Step 1: Check gcd(14, 3)<\/h3>\n\n\n\n<p>Since 14 and 3 are relatively prime:<\/p>\n\n\n\n<p><strong>gcd(14, 3) = 1<\/strong><\/p>\n\n\n\n<p>So 14 does have an inverse in \u2124\u2083.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Step 2: Use the Extended Euclidean Algorithm<\/h3>\n\n\n\n<p>We will find integers <strong>r<\/strong> and <strong>s<\/strong> such that:<\/p>\n\n\n\n<p><strong>14r + 3s = 1<\/strong><\/p>\n\n\n\n<p>Using the Euclidean Algorithm:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>14 \u00f7 3 = 4 remainder 2 \u2192 14 = 4\u00b73 + 2<\/li>\n\n\n\n<li>3 \u00f7 2 = 1 remainder 1 \u2192 3 = 1\u00b72 + 1<\/li>\n\n\n\n<li>2 \u00f7 1 = 2 remainder 0 \u2192 2 = 2\u00b71 + 0<\/li>\n<\/ol>\n\n\n\n<p>So gcd is 1. Now work backwards:<\/p>\n\n\n\n<p>From step 2:<br><strong>1 = 3 \u2212 1\u00b72<\/strong><br>Substitute for 2 from step 1:<br><strong>1 = 3 \u2212 1\u00b7(14 \u2212 4\u00b73)<\/strong><br>= 3 \u2212 1\u00b714 + 4\u00b73<br>= (5\u00b73) \u2212 1\u00b714<br>So:<br><strong>1 = 5\u00b73 \u2212 1\u00b714<\/strong><br>\u2192 <strong>1 = (\u22121)\u00b714 + 5\u00b73<\/strong><\/p>\n\n\n\n<p>Thus:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>r = \u22121<\/strong><\/li>\n\n\n\n<li><strong>s = 5<\/strong><\/li>\n<\/ul>\n\n\n\n<p>So <strong>14\u00b7(\u22121) + 3\u00b75 = 1<\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Step 3: Reduce r mod 3<\/h3>\n\n\n\n<p>Since <strong>r = \u22121<\/strong>, we reduce it modulo 3:<\/p>\n\n\n\n<p><strong>\u22121 mod 3 = 2<\/strong><\/p>\n\n\n\n<p>Thus, the <strong>multiplicative inverse of 14 in \u2124\u2083 is 2<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Final Answer:<\/h3>\n\n\n\n<p><strong>The multiplicative inverse of 14 in \u2124\u2083 is 2.<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Explanation:<\/h3>\n\n\n\n<p>We used the Extended Euclidean Algorithm to find integers <strong>r<\/strong> and <strong>s<\/strong> such that <strong>14r + 3s = 1<\/strong>, which is equivalent to finding the inverse of 14 modulo 3. Once we found that <strong>r = \u22121<\/strong>, we reduced it modulo 3 to get <strong>2<\/strong>, because <strong>\u22121 and 2 are congruent modulo 3<\/strong>. Therefore, <strong>14\u00b72 \u2261 1 (mod 3)<\/strong>, which verifies that 2 is the inverse of 14 in \u2124\u2083.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"852\" height=\"1024\" src=\"https:\/\/gaviki.com\/blog\/wp-content\/uploads\/2025\/06\/learnexams-banner8-919.jpeg\" alt=\"\" class=\"wp-image-37566\" srcset=\"https:\/\/gaviki.com\/blog\/wp-content\/uploads\/2025\/06\/learnexams-banner8-919.jpeg 852w, https:\/\/gaviki.com\/blog\/wp-content\/uploads\/2025\/06\/learnexams-banner8-919-250x300.jpeg 250w, https:\/\/gaviki.com\/blog\/wp-content\/uploads\/2025\/06\/learnexams-banner8-919-768x923.jpeg 768w\" sizes=\"auto, (max-width: 852px) 100vw, 852px\" \/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>(Finding Multiplicative Inverses Modulo n; The Extended Euclidean Algorithm) Recall that e Zn has a multiplicative inverse if and only if gcd(a,n) = 1. Moreover, by Theorem 1.4, if gcd(a,n) = 1, then there exist integers r, s \u00e2\u201a\u00ac Z such that ar + ns = 1. Reducing modulo n, we have that ar + [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-37565","post","type-post","status-publish","format-standard","hentry","category-quiz-questions"],"_links":{"self":[{"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/posts\/37565","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/comments?post=37565"}],"version-history":[{"count":1,"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/posts\/37565\/revisions"}],"predecessor-version":[{"id":37567,"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/posts\/37565\/revisions\/37567"}],"wp:attachment":[{"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/media?parent=37565"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/categories?post=37565"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gaviki.com\/blog\/wp-json\/wp\/v2\/tags?post=37565"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}