Problem 50182. Compute the Euler totient function

Created by ChrisR

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:r><w:t>The Euler totient function </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"phi(n)\"/></w:customXmlPr><w:r><w:t>\\varphi(n)</w:t></w:r></w:customXml><w:r><w:t> gives the number of integers smaller than </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"n\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t> that are relatively prime to </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"n\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t>---that is, that share no common factors with </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"n\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t> other than 1. For example, </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"phi(12) = 4\"/></w:customXmlPr><w:r><w:t>\\varphi(12) = 4</w:t></w:r></w:customXml><w:r><w:t> because 1, 5, 7, and 11 share no common factors other than 1. If </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"p\"/></w:customXmlPr><w:r><w:t>p</w:t></w:r></w:customXml><w:r><w:t> is a prime number, then </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"phi(p) = p-1\"/></w:customXmlPr><w:r><w:t>\\varphi(p) = p-1</w:t></w:r></w:customXml><w:r><w:t> because all numbers smaller than </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"p\"/></w:customXmlPr><w:r><w:t>p</w:t></w:r></w:customXml><w:r><w:t> are relatively prime to </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"p\"/></w:customXmlPr><w:r><w:t>p</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>Write a function to compute the Euler totient function. </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>Note: I now realize that </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/656\"><w:r><w:t>Cody Problem 656</w:t></w:r></w:hyperlink><w:r><w:t> also deals with the totient function. Apologies to Freddy.</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.4333px; 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: rgb(0, 0, 0); white-space: normal; "><div style="block-size: 123px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 61.5px; transform-origin: 407px 61.5px; vertical-align: baseline; "><div style="block-size: 63px; 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.5px; text-align: left; transform-origin: 384px 31.5px; 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: 79.7333px 7.91667px; transform-origin: 79.7333px 7.91667px; unicode-bidi: normal; ">The Euler totient function <img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD8AAAAmCAYAAABzhkOMAAACkklEQVRoge1Z25GDMAzcHtIBDdAAFaQCOqCDdEAL1JAS6CEtUENa4D7svQifHzIxDHPjneHHEMmSVg87QEVFRUXF4ejtUwoTgKagvMPQw2y2JBoALwBtYblF0QOYD5LdAlhwUQa0AN44dnM9DAMuhwXA4wQ980l61Ohhon47QdcdwIoL0X8BMP5jfUEwEt2JOkcYphVBB5NHspU0AAa7HuvZE4zxWjRW3+Cs360ud92HIg4fYCj0wjaHRiucm1kRbjML0u2ts9+8rawVn1mgtfpX8aQo3Yj97QIj9nTWHx7Br8C3iKz7QKcyauzdA0yx5DtNO8vRuwENX7Ct0PSom0+zWJffd8iLAPVSzoItdWm8Rt4bOwYq0niFyR2JJ7aUJGbxm2+MX4T8Gdv8pixtLjON1Ljhk3cutRh1n3L+5pvIS/kL/lKWQdEaxICowXxe8beC851rYCt+49Isx3jJON9ARGO0eZxtPGnnUx4qanLTbhvKMZ4p5XM8Eu980HSZX0jaxSjvGigd5rY6VmjNtCUp7+Iu3mvHVh8Tg5AFxd2sjK4cdHqEnUJoqq40zieHLZBBuSF+TqDT1X1e5q5rPCkpo8JWlPLwE+kiJft7aFCSxkyI05+BdLtVFKzabl67Uxc3QMNjUSA7YnRlPfE5UQblbvWmboLozKxTpKQxvSYp2VuBE4yjNLlMCobSQtYTH03le221f2HnVVkHY9RsHzlXj1Y5naDFBH8hA4xxD/uE2MFDjWa4IVOKnCI1eZ1CA8OUM461E3bO9C5SlMwBT4hHokPBe8JQi9uLCcfdsLD7ZFX4GNjiit2KwKRPyT8sCNaiYsipsDlI9elcjIXlbarwEf+ElLzJvcxNbUVFRcXl8AOhCgwX4v7BgwAAAABJRU5ErkJggg==" alt="phi(n)" style="width: 31.5px; height: 19px;" width="31.5" height="19"><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: 132.25px 7.91667px; transform-origin: 132.25px 7.91667px; unicode-bidi: normal; "> gives the number of integers smaller than n<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: 84.4px 7.91667px; transform-origin: 84.4px 7.91667px; unicode-bidi: normal; "> that are relatively prime to n<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: 61.3667px 7.91667px; transform-origin: 61.3667px 7.91667px; unicode-bidi: normal; ">---that is, that share no common factors with n<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: 85.95px 7.91667px; transform-origin: 85.95px 7.91667px; unicode-bidi: normal; "> other than 1. For example, <img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAIIAAAAmCAYAAAAIjkMFAAADhUlEQVR4nO2bcZGzMBDFnwccYKAGUFAFOKiDOsACGioBD7VQDbVw3x/hTbf5CNksORp6+c0wN9NL0rB52ewuFKhUKpVKpVKpVAqkn68SGAG0n57EX6SHM76Wbr60nABcAFznK9a3BXCf+30jDXR22JUewKRs281tf+AWNkYr2vtXbKFPAB74Ts+QYsNdOAF4Im7spQWN3UQzj81Fn+AWVo7xwLoY+rnvN3GB3oa78YBzUWu0cBPmX+1N3OCE4C90B7e4HOcWGWdSzPEonJC2mXahh1uoJqFPB91NtHOb0G7n/38UczjP7Y5+RDR4bbyihPAAMCT20Qrhqhj7JsaKBYWWuZbGCOfdGhQkBO6y1KhVK4Qe8R0sd0ZMCAOc5zgqZ7zHYlmF0MEZUxqR5/gV6zWBcZ6I5Ttz3QSFoFlgq3BLoIW7R7keWWx4gXOVd7zvumEe/IpXUBdKvx7Qp4ySnELg0aBx+YwpLEFji1f9YstlFeGE/2s0m23InexH2txd0lD3QFusfB4jpxCYWmqDwBxz3nJZ7vcKt+n8YHiTDSkCf2DuFt/FTuJz2Z6GseyuXELoDXN4wubFcnmE1ConU8WlfmYbyvz97P2PLtZ3P7IAVJIQmEYxgtYy4TgBo0wVlzDZ0K/QSWQ+7p9h7FOaRxix7C5jUNhHgKliCJMNZZrlZwIy8paGlRUsf0KfFAKLWJbi0FGEwAxnQPiYkVVVdTDK+vxSBS4UEK6Vgj8lhC0iAOyZzt5Zg1zobMGodP1rx4I/iBSPb3hWtiyVOqsQtooAWPZuGvbOGljfWbukt1YFo/Im/IWTu14O0iM+eWsEbhFCh7gIWqwXwCjeT9YRcr4bkbyZ5FnvC4HZwkN8xmg1tnv4ZDCVVCHwMbef6UgaOG+31obfu9bmSJiOV0b/fhzAwWTayFpDLDWj10h11QyENDdBEdD7hK4n3sW8BKumqZlGqZiEIF09d4RckB7OQCOcUTVnP11tykTOeH+P4I5wAEURaM/fmMu/I+1VutIxZ14d3AJzF8kFGeC8BQWhhfm8htj56X9vr+iz1l/C4/GID5xCZIs7NHFADD4VK93AI2zPGL4emTZaomgJn2SWiibj+LOE0kYrI8p8+4cZ0LdkCtlh2pjzAcyEcn7cQhj3VALIOnVORpRj+AHlzKVIZJXsN34FVEqeXmOCSqVSqVQqlUolxD+nOt9IeLButwAAAABJRU5ErkJggg==" alt="phi(12) = 4" style="width: 65px; height: 19px;" width="65" height="19"><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: 175.283px 7.91667px; transform-origin: 175.283px 7.91667px; unicode-bidi: normal; "> because 1, 5, 7, and 11 share no common factors other than 1. If p<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: 77.0083px 7.91667px; transform-origin: 77.0083px 7.91667px; unicode-bidi: normal; "> is a prime number, then <img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKoAAAAmCAYAAABUBAAhAAADuUlEQVR4nO2cYZGDMBCFnwcc1EANoKAKcFAHdYAFNFQCHmoBDbVw9yO8YZsDAskC4brfDNM52iZh87LZTdIDDMMwDMMwDMMwjFNR9dcWPACUG5VtfBEVgGbD8gsAT2w3EAw9SmTqVCoA7Q71FABeAG471GWsp4TTwQ+A+8Ft+cMVwBvAZaf6LjvXZ4S5YBAor+yE2sHFj3vywD4e3AhzgRMlX7MUagXn3Yqd6y3gjGHxal6UyFSoHYD6oLobuHjVyIcshXqDa9BR2R3rvx5Uv/GXzYRawsV7srMZazwwP7U2fYPW1sc6a7g4s+ive/93278XEiCn/73jYy00bZEL6kK9w03bL3xmzzWGzmdg3GE8w+6wPqFhx/BhuNTUwQm/hot5f/rXUAfFtIE8FK6UGFnbFjmgKlR6wqd3n0aTHuo18VnM3F8CH6aF6xiZjMnOC8W/LVwnprQh5Yp9/rF2pNoiB9SESpH6BrlgGLmSVtyXn2eDYqZd+TB+O/z3Q8nSE+vDD6LhUVM3HjRtkQMqQpVrXL6B2eH+FqhcxNUSKsOLsXbIspd0Dj3OGabFMTRtQSqkD8DYzZRkoRYY4h3/gelNxzJ4GSNpCZXhxNSUzWx+yXRHoWa5r7wATVsQf4co5ood+MlClbGOnwDwPV+MV/EdP2GJFSoz9THvTaSXCSUrZxaqti2IhkeN3cBJFmqHcTEC0wnT3HZYrFArUeaUuGRbQ8QskZGjs35tW+RAklDl1D437fsFSyP5MQu9wdpMlMJaMtUteVBOczEcnfVr2yIHkoQqv+wLS3pNGZfI0T5V4Rvr1zAp/qkOpndfWu4rog3k6Kxf2xY5kCRUGWv6QmW234l7BQYjzhnpiXVT0pz3BoZ4bGyZZooYr54DW9giB5JjVGbv/ugdC+Y5JXFLbwp63aVLGXPLYyzrFahTwqnxjIeotW2RC8nhipzKaRhZaAVnlAZO1Eu8FOPUpQ2i95Ze8Nrf71aUQ2p8zgRnQtsWOXDDEK5woEWtxpQYDj+0XqE1ht8jrRnFDZaLhV69hXuoB1yHxK7ZvXHeAynatjiarZa7ACyLQ0PwZyGhkaN9qqbC+eI3kuWZzVyRwXyqV+JJrDnkhkOq1+Au2xljU0DXFv+eqWWpWHgsbYrQVuEanoG6ckfTFv8eBvOaxmoxvlMjtwpTj8Xdse3/DtgaTVt8BVsZq8GnWOXvvJkJ3hB3OqfCuT2ppi2+gguGbGyLGMk/ZTV2xXTO2TtU0xaGYRiGYRiGYRjGt/ILHfEYyCx3N+MAAAAASUVORK5CYII=" alt="phi(p) = p-1" style="width: 85px; height: 19px;" width="85" height="19"><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: 108.533px 7.91667px; transform-origin: 108.533px 7.91667px; unicode-bidi: normal; "> because all numbers smaller than p<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: 70.7917px 7.91667px; transform-origin: 70.7917px 7.91667px; unicode-bidi: normal; "> are relatively prime to p<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: 1.94167px 7.91667px; transform-origin: 1.94167px 7.91667px; unicode-bidi: normal; ">.</div><div style="block-size: 21px; 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.5px; text-align: left; transform-origin: 384px 10.5px; 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: 166.333px 7.91667px; transform-origin: 166.333px 7.91667px; unicode-bidi: normal; ">Write a function to compute the Euler totient function. </div><div style="block-size: 21px; 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.5px; text-align: left; transform-origin: 384px 10.5px; 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: 73.5083px 7.91667px; transform-origin: 73.5083px 7.91667px; unicode-bidi: normal; ">Note: I now realize that <a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/656">Cody Problem 656</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: 174.517px 7.91667px; transform-origin: 174.517px 7.91667px; unicode-bidi: normal; "> also deals with the totient function. Apologies to Freddy.</div></div></div>

Solve

Solution Stats

21 Solutions
9 Solvers

Last Solution submitted on Nov 24, 2021

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Problem Tags

number theory primes

Community Treasure Hunt

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

Start Hunting!

Problem 50182. Compute the Euler totient function

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author150

Problem Tags

Community Treasure Hunt

Problem 50182. Compute the Euler totient function

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author150

Problem Tags

Community Treasure Hunt

Players