Problem 49788. Carmichael Number

Created by Gifari Zulkarnaen

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Carmichael_number\"><w:r><w:t>Carmichael number</w:t></w:r></w:hyperlink><w:r><w:t> is a composite number </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t> which satisfy following relation:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>    </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"true\"/></w:customXmlPr><w:r><w:t>b^{n-1} \\equiv 1\\ (\\textnormal{mod}\\; n)</w:t></w:r></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>for all integers </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/></w:customXmlPr><w:r><w:t>b</w:t></w:r></w:customXml><w:r><w:t> which are coprime to </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>For example, the smallest Carmichael number is 561. It has prime factors 3, 11, and 17, thus it is a composite number (not prime and not 1). The relation </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/></w:customXmlPr><w:r><w:t>b^{560} \\equiv 1\\ (\\textnormal{mod}\\; 561)</w:t></w:r></w:customXml><w:r><w:t> is true for all integers </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/></w:customXmlPr><w:r><w:t>b</w:t></w:r></w:customXml><w:r><w:t> that are not divisible by 3, 11, or 17 (coprime to 561).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Build a function isCarmichael(x) that returns true if x is a Carmichael number and false otherwise.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Hint: Since </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/></w:customXmlPr><w:r><w:t>b^{n-1}</w:t></w:r></w:customXml><w:r><w:t> can become a big number, using a </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Modular_exponentiation\"><w:r><w:t>modular exponentiation</w:t></w:r></w:hyperlink><w:r><w:t> algorithm may help.</w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20.44px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: none solid rgb(0, 0, 0); white-space: normal; "><div style="block-size: 211.4px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 105.7px; transform-origin: 407px 105.7px; vertical-align: baseline; "><div style="block-size: 20.8px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.4px; text-align: left; transform-origin: 384px 10.4px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><a target='_blank' href = "https://en.wikipedia.org/wiki/Carmichael_number"><span style=""><span style="">Carmichael number</span></span></a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style=""> is a composite number </span></span><span style="font-family: STIXGeneral, STIXGeneral-webfont, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);">n</span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style=""> which satisfy following relation:</span></span></div><div style="block-size: 20.8px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.4px; text-align: left; transform-origin: 384px 10.4px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style="">    </span></span><span style="vertical-align:-5px"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAN8AAAAlCAYAAADC8DxTAAAKU0lEQVR4Xu2cZaw1SRGGnwWCu1uCu7st7u7u7i6LyxJcd/Hg7u7uwSFY0ECwIMEdguWBKtLf3LEzd849cruT++P75nRPT3W9JW/VzEHUUSVQJbASCRy0krvWm1YJVAlQwVeVoEpgRRKo4FuR4OttqwQq+KoOVAmsSAKbDj73f07gEOBZwCdXJMdNvu3RgIsDHwP+uskPssK9HxW4BPBx4C9j97HJ4Ds1cDfg2sBpgYMr+MYe+/9/dyLgocBzgW8sPLtOKCVwduDmwBOAX48RzSaDT2vzt1CeQyv4xhz3Ab85CfBI4PAKvIVl1zXhLMCtxgJwLPj83bHDpf59tq3Os9DDgAq+xWRpqKmF/jTwauDfi01f618fCRAEZwTeDuy1vt4oIrEnAv/ok1Qf+K4KXAU4B3Bu4I/A1YEvrJnotwF8RwAuCtwBeAzwrSXLWAW5FHBf4E9LvtdeLH9E4JLA9UJnTwU8D7j3IjnYTBvVsD0VeA/w1qngc56h3ZOBu8ZixrS/7FjwWMCVgfNHAv9M4H3AvYA7Ae8G7g78ZqaHzGU2GXwJuvtE7vpl4IZLBt/JgOcDWmZJlm0YGZn5bM8GLr1C8CnPCwIPB24P/LRLwENh59GBw4DbAY8DVPR/9pxW/v4CAbprAC8L0F0EuD7w9ZlPe1PBdzbgZsBPIqK4ArAX4LtteAkN6h9mPotVL6fXeRpwxxWDT0ck+/5R4IVTwaf7flWERNcE3jYg3RMCLwf+DPw4knk95QsCtB74r2Y+oU0F35GLfOQWwEv3AHzHibP4QCjnzEex8uXWBXwKQgNwRUBj1xrtDXm+y0foONYiny+SXG+uy31XJL6vBfwz1EnPmaAZc2J98fumgq987psCr9gD8Hk+bwTM+SRbtm2sE/guDLwGuG4XT9IHPq89BHh0eLMxYYpot2Zkwmn9yIKjoaeKZTJsDphDRkq6e8z4LfDVjpC3gm+MBP/3G89HL3sT4Afjp23ML9cJfBk16jhMvXaMPvBliCJoJASMpftGPriV/lsCn4P/Nm4/ArgScGPg+0s4xt2A70zhkc+1y32ZXGukpo698Hwygu7xDJHD/65ns9L1pwRMNc4TrKHkkGd4NcCc/kvBB7wT+Bdwgrh+rWDIvxjkR15v3s71ZNHVFZskTFmOB7w3PMZnYt0uvbWzSQLvzNGZ87Mw/BoXo65VsZ2538TPd7q4kj7w+XBvAE4aLObngctFV8nFoor/pgDlj4BE+ndDKL8PYZpw/iJAaFeKQp1zVPCNk2aSYYb9fRS8Z6uxlBzTOAkGmev7AZ8CPguYjtw5CBvB4/neH/gI8L0IawWqhE4z4nG3EhIPDlZSAKlb1hrVj8cGiGUtPdtmt4iGwf27vm2FHwyQCmAbBiyRORYFn1g4bjzzecPAaLDuGTmbe7sHcB1A3Tay6+NA0hnlGvIgB4w+8KU1VqDWnww7Twy8MvI4NyXg3hzhjEVNywkPCgvkIWcOaBjqv6W256wTpmfVu25ye9leeD49k2enRxpirVUSFdxzczwnUpAkDvRQGlVb+zS81rMEU7KnNmQ8I0LcJgiOEbm/c2V7P9TQSY29BJ0gEoAPKGqRnvdtAqDqZLOOZipj04CRzKLg0yBY+3Rft449WQd9OiATrczkPqx9q/c6JqsAXRGEZbqnAKcDPN8dRGMX+GTiHh8HIGWqUPVoMnJW7Z1n7U7hONycvW1aQ91+JvOGOLKfznlg9F7O1U2hAC4Tlklhvwh4cYB7dHPrOKex9F/tJfhsPh8TIueezLVvAHyzIYUE59B1PWepfIay6oT/36W8eheJIfXO2nKCzPLM62MvbSxiWRpbFHz5eHr+T8S9rVvradVrgagXzlKGzzDEgwhY11sIfCcPK6klEO2WG7SCZbtMbtJNa8G0qnVMk8A6g6+L6R7ac9v1o4TXM3zrqxufJjzYhQoP5hsXAl5v8qj4axryOQiXJA3tUHGPOhOJx59HGiXo9MqCUSD2OZNJ4LtshJO6Yi2NG2rWKiRWLCKm53v/NL1b6az9RLgsGnZOAVd5mG3zfYtCQy530EdSZZFar2dNUnZW8BmF+X9dxn634Cvn2wVk+GyHlzmpQ3LndZGb6hX7XmHLtSSu3POOWl9b2FmWGHT7xsAmtc2RFmJsDXClKOu4+X4C31jCJUW1DPCV8u4DX5nLp36pi0ZXRmPLAl/ZVGJbmPmm90zvZtnMEFiDoEfsbB0DEnzKs5XgagNfWWJ4SbCbzebb0jLJMLlJX++pY5oEhhR92qoHzlqk1ODMoT1NuV6Cz5BNHqDrrYNksRN87slGDfN7Gda22tluPV82lXgvPZ+gSd1P+Ukojmm1zEhD/sMweUd42ga+LDFIllidt5zQHBmWmoBKJadbnkNJ9uMaQ4o8l0y8z11GFtmH9jTleiqkbVdDbGGCzzqhYZshYLY6LiPnKyM+PZr1SssqObJ10jLMmFbL00e98klhNHacYRv4UqjW49oK49LMMknWgbRcJsC97y3NpTlbvM6QIs/16BpWW54sQg99cmNoT1Oul97D4rOG+ystD1d6sPQyx4wShHMsb7WxnbvxfGXE18aUZtnMmuaYN0/0or6U0PkyQRN8ZYmhjUqVdpXlsQzRrMHMpSD7cZ0hRZ5LJtbYLJhbHhhi6ob2NPW6RJ0GwNd/uhjDZNsNU+1DtT4scE1vLMJ3Fe93A76hiC85jsSFdTwBacukHT7lSC9qjc9PnbS+M9kEX1liaLp2f6sntHdT1imFMJdirGKd/US4pHytoUlYdHbbxw+ngivv0zW/NOBGVxa0m9+PybnNyCrrxpYgnGud8GuF4vjit+AwL+zyjl161hfxlaC21dImAPdmz3Lbt280LPIlOqjOF2qb4LPX7i1RwS/Bp8W00Oj3KXzT2vLDNoSa6wA+lVGZatXbco25jZJpgx0rdoJ0KYZ6kTW1rvAwPUHbnofmq8x6PZ9Zr2bdz7Y0+z2tHxuuyTWY0pQNE65rzuX+ZSZtDvc5bHuzu8UuJ3XVl2kdeng7bWwO6fucRBnxtYWcZa5q5GAILLiy1NY8Iw2ceaGtc7aitY4m+Py37tcWHmsaMk0ymwrLoqPfxNiGzw7MrdBT1jOBl9CyUdm/HDakS0ZkH+UyWGQ/uaDny77Fcv92KllE1iNpnBx2o6jA7wCs1ZnHlNdtQTSUtCvF/kiv2QF1/Jb52YJW6pr5ke99CjQ9mZ7FjpquArZ9lvlS8Clijn2WGhM9k2/BuNdvj3QSZcTXVsbI/kw/OCUJY5nE82nbny2YAlQD0ptXD73PN0Wp6pz1l4DKpJI6su92/Xe9/jvMkNqGAEtwva2UFXzrf6DL2qHRjN/XMXf68JCiLGsTW7RuhsRnDc83GLFU8G3R6U94FAFoXiLdb2g5V9P7hK1s9BRxZO3SvFOSZRB4Pm0F30af+Sybl+Qwh/rhyPxolptu2SI2jCtDyalm2aHzUSv4tkwL6uNsjgQq+DbnrOpOt0wCFXxbdqD1cTZHAhV8m3NWdadbJoH/ACnP/UQmmrooAAAAAElFTkSuQmCC" width="111.5" height="18.5" style="width: 111.5px; height: 18.5px;"></span></div><div style="block-size: 20.8px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.4px; text-align: left; transform-origin: 384px 10.4px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style="">for all integers </span></span><span style="font-family: STIXGeneral, STIXGeneral-webfont, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);">b</span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style=""> which are coprime to </span></span><span style="font-family: STIXGeneral, STIXGeneral-webfont, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);">n</span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style="">.</span></span></div><div style="block-size: 62.4px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.2px; text-align: left; transform-origin: 384px 31.2px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style="">For example, the smallest Carmichael number is 561. It has prime factors 3, 11, and 17, thus it is a composite number (not prime and not 1). The relation </span></span><span style="vertical-align:-5px"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAPcAAAAlCAYAAACeen93AAANHElEQVR4Xu2dBbAlRxWGvwCFa5DgmiBBAlQhhXuQIMFdgru7uwV3D+6EBJcESIK7F26Fu7vUt9WH6uqd6bE7u+/eN121tW/f7dvTffr8ff4jPbsHS1sksEhgIyWwx0aualnUIoFFAizgXpRgkcCGSmAB94Zu7LKsRQK7Ctw+52LAV4A/LWJfJLBIYH4JzAHuYwOPBB5eTP+xwKOBfxe/P04C/vUBfz4cOAb4a+q3J3Af4MzAz4EzAE8BvjC/eDbqCXHA/hj40UatbPMXc3zgMsDRGS46Vz0HuM8GPBf4JPD3NAMB/Tbgu8WMzgI8AzgR8GDg88B/sz57AS8CVMgHAH8BbgI8CrgN8NHOFS4dlICH5h2B3wBvKGS8SGg9JHA+4BbAk9M+ds561eB2vNsBJwSe3aFE5wFeAfwsKZ5WOW+OdW/gfsB1gE+lD08FvBr4BXB34A+dq9zeHQT2PYGfLMBee0UQM7fuC/C+4LbfSRMl+EdFRKcDXg58HHgX8GWgqf+pk0W+MCAd/0zDmAFilfOmwC9TH2m/FN9F5qBf+52baQE3Bi4FPBD480zP2B3DqpMyu8sDH0pGYtXz0AXcF/jAgIFPBpwTuADwu+Rm/nPA97u6up9nT67pv2qda+C+BnB14PzABVMg7JrAZysDXhd4a/a5NPBxwAsLX+G2wEuTdZduB33Ph7448H7gjcnySMmj3RJ4ZfLFpfXr1IwdyDg+B7x+5onvk9ye+wNfn/lZu2r4vZNrpn4apP0icCPgGyMmoKFQ/57Q8l1ldgPgqx1ja/gOAO6U+qnv7wF+22NOQ/XhBMDTgfcCh40Ft9/TkT8YuGsaTM7/q8qAJ07+837Jsuof2/TBFaJBMk82ga3FlpZr7S+ZaOMhwIuTT3GtNHl9bul5BNgc72bAa5LiPqiFHfSQ6y7t4ibeBbg9YJDw5sBrZ5xBBDaVmwHIMpA546NnHVrlVs8Msrr3U8BtfMgD1kOiqelathkf+x8LuBrwtISVhwFvbjFW5fhT9OGiwCOSLv20TdpdtFzf+VnJj35iioD3VRLHvkJauDRCoEvVz5Wssb8TtIJUIansCkl/WoFKuf2s6bk14M+qWSMGP3mSn2s8Y7LaDjM3uM+bDso7A18aMe+t/pU44MeCW/28RzIsLwFK6qyefw34dYsgdBfVX7NC9tMA1lhtDLMKfTgJ8DzgI8DLxoLbaPbrgEsA107+w9BNvwrwlmS9FYR021SXvzP49vs0oBFzLfz1gAOB01bAfeVE2Zus+tD5zd1fJfhP+nNu4E3J1Zkb3CrehZLS/XHuRe6G8aeCW8YoU9Sg6P4Nae7pfYEnAT8AbpWA1meMVemD2Y/9AV3cRvrfZbkDRGNPRxcbgTGFoMIZRBPcTcD0c/0JKdd3NoyWK4tgLbotc4I7XB/9epnPJrap4BYU+u2t4GgRmpiRhepXa0F1VXWv8hRuX3lP0QeNpGlNjWEjY6iB288emiLTUmVpxxgLoI9k0Eua42l31mS9zIOboskDZbFh+hPvBt6RqHzZb10DalM2s6/C2M9IrczINKJFQZvYpoD7NIBUXPdOo6MuGpw6MhVK1YCq/uouGic6dMThkO/FFH0IVq2RfFXTBtfAnQe+tKRjo9LhH1ig4hgxrr5HnuJyfrFh0hzB7aFSpsKcsxVwzslgRp9CllyIUxTdQ8c03Ng2ZTOHPFPGZTahK7thHED354rJihkQMkCjC2YEWoZhHYJBTq2TWQ3dJz/Xeumume5UueLzpnlKgd3rS6fvK4dPpMImD/Bais60qdbVaPTfANM/rk2job85hlWWWZ18zq5F/fp+w0Ki9kIqb9OtbPV5e2zYFH0IHH2rLRZWA3ec/m6+IDIXfSXgbunUMs1l1ZmArZUzOo6+tIEdUwptxSkB2hum9INBCgMe5mfzfPYpMoH2pVTbDdwyGw+/WopI/19KJ1AvkkDi4WXlnwVFH0wM4F6Jfvq3vqnVgd4RkPJfNfmbHuB3SFmQ3Op5ePiMx6fCCy1eHBDqg88z2Oc+O17ZLLl8fvKNX5AOAQ8XU3sC0DYG3BaDGNxUN42Ue7iZwYjmmM7Peo28eUgJfnEgqGRGjuFhYXxDTByRaj3MvTelePPxpoA7GLFZkZLZ7nhGDdxhRT+cNk5aLp3xhDZJ74BSA6mJzr0J/7enyjEVQcGcPuWyTQ+Yr46NL8tKPbn9vpba/KB+tzQ++nkouJn+zmCbgQxTSkYL16lN2cwh6zRwaabCPbQyrdYi82AfqalA+2H6wvFSGs3fadGNlRgXsRzYJqvyvsBDGlKluW9qKs49y4su/K6pLJmQtNhDJc/FCxqB5CGje5gDRYBrVNSBMeAu5WGe2kNIQ+Ie2ZyT/rQgjiYVVz89zGym0WQ16qfpOQ9TDx4PCrNMzrvGSqbog2lqGcQ50j7vFNVvA/dx02a4kYbc9bW/neiQG+T3TNh7qtqMiH86WQuthouTLkvZPAw8nUs/RkagD26hhZdAXKiHgD5irgTRT6BrUTxQBL/CHxPEGAKSVfedsplD5iK4VUTB3ZbKyRVW0NouCxxVPCgHf+3zEmThm5rybHMP8jyzihogjsyJ0eC2KsSIu6wC3LFkdc2DSFDb/FlZRpVlGDw/8+Apy5/LYJtGrlaGPVUfqvvcBm4trqC8XDoZTYcJqBx0Kk8oxZyR3yFKvdX7Tt3MvusbC27LVMsYRr7PQz4Pv1bm18YgcmaQg9QiDVmgFrGMy4QMpgTUanIMtqi78rH0fINuNuX6mPRzW2o4DibLo8vvl8+dqg+jwK0PIt2WfmhNpd1lLk1/KGixlntI/W1fJV1Vv+3mcw+h5WPB22T5A/wRP9GVel8Hg1C3TCvlzCF+V6tjmAvcziMOJhmrum3wrwR300EXMon5l99fJbjD5zZ2INPYKdfdZLnzFJiT08c1SFC2WMAqadGqwFwT4pRnrEu0vE9ArQbOXEZjwB+Kp450gTs3EjJAc7f64V4B3l3gzou3chDnB1EN3FEfohxrrHaK5Q4Z+4yyPHvH/jWBO0+BWcFjdLwMCkR6yxOjq/52Cpg27btTNnOILPqmwhxzDHi7wJ+Du4ualu5dZGAEkncQGiPBWdp0DuNyyuSWGi/wDkSU7+bxhxpb7euyTtGHmKOswqDmTvGnJnBHCsxAlxFEhV22oO2G/tuubA5Rxu3Sd8pmDpFRPEem0VXEMge4cwprlL2Wb4/nB4U1JWZkXWtkpHxX+9zOPYCjEfP54XNbr6+bairNWozG4pHiwGwKQsZeTtEHb8fJcp6aMlE76UcTuMOXMRptocL3im+ZZ5YueRXOVIZRzuq90iFaueF9p2zmENEEs/pmyjHXsgpzgTunpmZW1JmmlqdcI/AWZcgeDG3R8jl97jBwpr3yW2F5sMxUXNuNxLDwloV6/9pMU1Obog/K13Rb65XUEtx5Cqyp5DQvmDcN5sI36QUAQwA0pu+UzRz6vL6103OBOy/xbCvTjBdv6F+bK4+rqfrhWiWLRrxrbWCuNCBzgTvy71afNbHSCLa1Gb88ZtXlso7Vh3iGOe4mt3mHrpTgzlNg8vicy+c5PHPfCn1MrflQJV1F/+0WLVdm5pC9L+8BHK+oapLlXOD2WVJSS0Wte9B6W/SRs4jYF0s99bHjVVv67AJdxVXHvAdvOtbbdTaZialZAViz7k3r1dIZnTfNJqX1GnKMq477Zhc/txKvnK/j5cxV2UbBVTwrirHMmWu1a9dtx4I7brRpYFtf2FCC2zeumF80WpiDWzpiOZ65O0sJ9TvWiYpvFXBbxmvNvM0CHqndXIU4cV/5TA0VXrnS53XWTUGinF43xWBq33cOFqI8M73MwCpHqa5gMoWjgbCySxoefm3MTR3UiHhzS4C/M/3R2jsPK9YsVbYZ+5Fp6qtbC19rQfmjj3sgSKxb1w3VDTCVaPlo297Eiz09vCxB9eBxPh46sgzr4C1gMVNQ29+x+qDMzbNX3yFYgtt/628cBFh7bCTSCXuS+lqXriL/VVjZTRvDQg1LQd0MrUbUMKuQZiMsBPKVtbU33IyViQUZ+mW+Tad8T50K6mu0LPu0ttxmlaHW3sPb5nzzz9UHLbHWQnfMw97Po2Qz/36+Hi9/mJ4zsGapp+/Dc/2OVavB1qho/fRhffunZa/xggLn7EUUA74+t697qC4bDJNyWyyjfnuwWGzjuv27z1juq/JzfgbYZB0CXJxo8dsqA6fqg+6OdzXc1+qlqVpt+ViFWr63tSQg7dZimlKKl0xurRkus+krgYh5yTK63i68/F9hfaW6xv08wL295Vs8PfG7biqt8VI3euqD93Gx3ButD/9fXPi+ulzPGfK/VmwP8Wz5Vcb+Sf+ND/Q6oBdwb/l9XekEjeD6NtR4b91KB18Gm00C+unesvP6aUT2Ox+2gLtTREuHRQLrKYEF3Ou5b8usFwl0SmABd6eIlg6LBNZTAgu413PfllkvEuiUwP8A3aukU5+AY6cAAAAASUVORK5CYII=" width="123.5" height="18.5" style="width: 123.5px; height: 18.5px;"></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style=""> is true for all integers </span></span><span style="font-family: STIXGeneral, STIXGeneral-webfont, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);">b</span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style=""> that are not divisible by 3, 11, or 17 (coprime to 561).</span></span></div><div style="block-size: 20.8px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.4px; text-align: left; transform-origin: 384px 10.4px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style="">Build a function isCarmichael(x) that returns true if x is a Carmichael number and false otherwise.</span></span></div><div style="block-size: 20.8px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.4px; text-align: left; transform-origin: 384px 10.4px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style="">Hint: Since </span></span><span style="vertical-align:-5px"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAADkAAAAlCAYAAAD4DEFlAAADJ0lEQVRoQ+3Ya6hlcxgG8N+U5BJSQr6QIsqt8IFBcpnGCAlJrk3mopnJrVxCQobkEiHK/VYiRCGTmhFFxgfJB6V84JPcco2IHr1Lu9Xezjrt3bTOOXvV/rBP71n7ff7P877Ps9YiC+BatAAwmoKcLyxPmZwDTIakg3A1HsB7w3qey0zuhbU4HXvjqPkIchv8jutx8yRAhvEd8Rv+6JmMbxgH5MlYhgNxCH7GKfhoPoEMlkjiTqzBmzgf34wAuQNOwmE4GvfjLVyG1XgD6/D9hA9pLCbTy3a4FxfjNuSGf/1Pk0394QXuVDxV4I7AWfi0byD3xHM4Eqfh1Rka3AVP41d8hfuK+UfqcKKIb/sG8sSS3Mc4G5/N0OCheK1qVuB17Ivn63PHgBIamXXB/DAur8XXrh9Lrtmo1+GWYics/DRDR6vwEO6u1Z5tHMk+gzPrwJpb7I/duiDED/hkxKiMBXInRGZp7grcM0ND21bNMbgQH/LvA8CNWIpz8EVHULMpGwtk4tKL2L225macUCljMb7DSwXsSzTz+3ktmh+xMx7F1wU2KeWD2SDoUDsWyHNLZhuxsmxkVzxbc3ZpAXsZkWlmLzZxbUk2W7iZ0cg339+ZsM82SolaZh3rtsbtNewJvpnFMPQk/iwZxvserJNeggNwCS7A+/X3fWqe8z/XVLb8uwM7XUqinOOQwz4Yj+HxOsTsgv+uUQF9j2LsWGSzxkbCRpptrkj23fpyXtV3aW6L14wCeTwiw6SYF0qO7aSSBbNpgMkNW7z7jj84DOSgdUSmeZR5e8j9Grvo6qEdW5p82TCQg9bxRG3TX1o/HYYzq8mySTVX1WPP5DucwB2HgWysI0vjjLKJ9k81co6NxEdjL729hoFsrCN+NszA432JWQnb2Zh3tRZS78C2QQ5aR4J2O8pthSvLXmIfkWlbyr0HOWgdNyGfxtdyIGE22TTzuL5Dlu0F4DaTeQPwSiWZQZDbl9FfhFvLVgY9sxdgRjXRBtm84luO/SoIZJMmfOfNQB6jei/PNti5/Eqys3qmIDsfVc8Lp0z2nKDO7U2Z7HxUPS9cEEz+Ayn4tCacCq9vAAAAAElFTkSuQmCC" width="28.5" height="18.5" style="width: 28.5px; height: 18.5px;"></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style=""> can become a big number, using a </span></span><a target='_blank' href = "https://en.wikipedia.org/wiki/Modular_exponentiation"><span style=""><span style="">modular exponentiation</span></span></a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; "><span style=""> algorithm may help.</span></span></div></div></div>

Solve

Solution Stats

46 Solutions
7 Solvers

Last Solution submitted on Mar 03, 2021

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Problem Tags

exponential integer math mod number theory

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 49788. Carmichael Number

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author1

Problem Tags

Community Treasure Hunt

Problem 49788. Carmichael Number

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author1

Problem Tags

Community Treasure Hunt

Players