{"id":952,"date":"2023-01-18T17:49:22","date_gmt":"2023-01-18T17:49:22","guid":{"rendered":"https:\/\/math.hmc.edu\/su\/?page_id=952"},"modified":"2026-04-06T22:11:58","modified_gmt":"2026-04-06T22:11:58","slug":"math55","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/su\/math55\/","title":{"rendered":"Math 55: Discrete Math &#8211; Spring 2026"},"content":{"rendered":"<div class=\"wp-block-image wp-duotone-unset-1\">\n<figure class=\"alignright size-full is-resized\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" width=\"692\" height=\"700\" src=\"https:\/\/i0.wp.com\/math.hmc.edu\/su\/wp-content\/uploads\/sites\/10\/2026\/01\/Screenshot-2026-01-16-at-8.12.14-AM.png?resize=692%2C700&#038;ssl=1\" alt=\"\" class=\"wp-image-1553\" style=\"width:253px;height:auto\" srcset=\"https:\/\/i0.wp.com\/math.hmc.edu\/su\/wp-content\/uploads\/sites\/10\/2026\/01\/Screenshot-2026-01-16-at-8.12.14-AM.png?w=692&amp;ssl=1 692w, https:\/\/i0.wp.com\/math.hmc.edu\/su\/wp-content\/uploads\/sites\/10\/2026\/01\/Screenshot-2026-01-16-at-8.12.14-AM.png?resize=297%2C300&amp;ssl=1 297w\" sizes=\"auto, (max-width: 692px) 100vw, 692px\" \/><\/figure>\n<\/div>\n\n\n<p><strong>Professor Francis Su<\/strong><br>Section 1, Spring 2026<\/p>\n\n\n\n<p><strong>Meetings:<\/strong> MW 1:15pm &#8211; 2:30pm<\/p>\n\n\n\n<p><strong>Course Webpage<\/strong>: <a href=\"https:\/\/math.hmc.edu\/su\/math55\/\">https:\/\/math.hmc.edu\/su\/math55\/<\/a><\/p>\n\n\n\n<p><strong>My Email:<\/strong> (my last name) at math.hmc.edu<\/p>\n\n\n\n<p><strong>Graders: <\/strong>Joshua Zhong, Aidan Deshong, Lily Surjadinata can be reached at g.hmc.edu<\/p>\n\n\n\n<p><strong>Office Hours<\/strong>: Mondays 3:30 &#8211; 5:00pm at my office (Shan 3416) or by appointment.<br><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Course Description<\/h2>\n\n\n\n<p>This course is an introduction to combinatorics, number theory, and graph theory with an emphasis on creative problem solving and learning to read and write rigorous proofs. Topics include: combinations, permutations, inclusion-exclusion, strong induction, recurrences, the Euclidean algorithm, unique factorization, modular arithmetic, Euler&#8217;s theorem, RSA encryption, planar and Eulerian graphs, and graph coloring. My goal is to create an inclusive classroom climate where everyone feels responsible for the participation and the joy that others experience in learning.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Text<\/h2>\n\n\n\n<p>There is no required textbook to buy.  <\/p>\n\n\n\n<p>We will use portions of Oscar Levin&#8217;s <em><a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4.html\">Discrete Mathematics: An Open Introduction<\/a><\/em> (4th edition), which is available as an <a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4\/dmoi4.html\" target=\"_blank\" rel=\"noreferrer noopener\">interactive online ebook<\/a>. (<em>There is <a href=\"https:\/\/discrete.openmathbooks.org\/pdfs\/dmoi4.pdf\">a PDF<\/a> available as well, but BEWARE: the homework problems sometimes differ, so be sure to use the online text for homework<\/em>).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Coursework<\/h2>\n\n\n\n<p>There are weekly homeworks, one midterm and one final exam. Each component (homework, midterm, final) is worth at least 30% of your final grade, with the &#8220;best&#8221; component worth 40%. A component of the midterm will be in-class. Final exam will be in class.<\/p>\n\n\n\n<p>Every assignment (except the last one) has an automatic 24 hour extension&#8211;you do not need to formally request this extension.<\/p>\n\n\n\n<p>The learning you are doing in this class takes place in a larger framework of school and life. Sometimes life takes precedence. Similarly, &#8216;success&#8217; by whatever measure is not the most important thing in this course either. Every assessment of your work in this class is a measure of mathematical progress, not a measure of your mathematical promise. Joy, wonder, and expanding your mind through struggle&#8212;these are more important!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Tutoring<\/h2>\n\n\n\n<p>Academic Excellence Tutors are available Mon, Tue, Fri evenings at <a href=\"https:\/\/www.hmc.edu\/learning-programs\/academic-excellence\/\">these times and locations<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Honor Code<\/h2>\n\n\n\n<p>The HMC Honor Code applies in all matters of conduct concerning this course. Though&nbsp;cooperation on homework assignments is encouraged, you are expected to&nbsp;write up all your solutions individually to ensure your own understanding. Your solutions should acknowledge the assistance of other people or resources of any kind.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">AI Policy<\/h2>\n\n\n\n<p>(1) Online resources, including artificial intelligence,&nbsp;<strong>may be consulted for <em>supplemental<\/em> learning<\/strong> that is not directly related to assigned problems (e.g., questions about a general topic). However:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Such resources, especially AI, should be viewed with a healthy skepticism&#8211;they can be wrong, or they may rely on ideas we have not covered in this class.<\/li>\n\n\n\n<li>&#8220;Supplemental&#8221; means they should <em>not<\/em> be a substitute for face-to-face interaction with me or your peers. Be sure you&#8217;re getting out and talking with others!<\/li>\n\n\n\n<li>An over-reliance on AI is bad for you. Outsourcing your thinking to a bot is giving up your agency to think, to reason, and to be human.<\/li>\n<\/ul>\n\n\n\n<p>(2)&nbsp;<strong>You must not use AI or other resources to locate solutions for any assigned work<\/strong>. You may check your answers using the &#8216;Activate&#8217; button in the Levin e-text, but <strong>you may not use published solutions for the text<\/strong>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Doing any of these things will be regarded as a violation of the HMC honor code. <\/li>\n\n\n\n<li>In addition, you will miss the joy of discovering a solution for yourself, which is one of the best feelings in the world.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Lecture Notes<\/h2>\n\n\n\n<p>I will not be recording lectures, but <a href=\"https:\/\/drive.google.com\/drive\/u\/1\/folders\/1csDjP2wfZhgQaqd1bYbnw8sJD-PCOd1O\">lecture notes are here<\/a> (HMC access only).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Homeworks<\/h2>\n\n\n\n<p>Homeworks will be assigned and due Tuesdays at 1:15pm via <a href=\"https:\/\/www.gradescope.com\/courses\/1099517\/assignments\">Gradescope<\/a>.<\/p>\n\n\n\n<p>Some of you may find LaTeX helpful in typesetting your homework. If so, there is a LaTeX class for homework <a href=\"https:\/\/www.hmc.edu\/mathematics\/student-mathematics-resources\/communicating-mathematics-through-homework\/\">here<\/a>.<\/p>\n\n\n<style>.kt-accordion-id952_9c101e-83 .kt-accordion-inner-wrap{column-gap:var(--global-kb-gap-md, 2rem);row-gap:10px;}.kt-accordion-id952_9c101e-83 .kt-accordion-panel-inner{border-top:0px solid transparent;border-right:0px solid transparent;border-bottom:0px solid transparent;border-left:0px solid transparent;background:#ffffff;padding-top:var(--global-kb-spacing-sm, 1.5rem);padding-right:var(--global-kb-spacing-sm, 1.5rem);padding-bottom:var(--global-kb-spacing-sm, 1.5rem);padding-left:var(--global-kb-spacing-sm, 1.5rem);}.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header{border-top-color:#555555;border-top-style:solid;border-right-color:#555555;border-right-style:solid;border-bottom-color:#555555;border-bottom-style:solid;border-left-color:#555555;border-left-style:solid;border-top-left-radius:6px;border-top-right-radius:6px;border-bottom-right-radius:6px;border-bottom-left-radius:6px;background:#313131;font-size:18px;line-height:24px;color:#eeeeee;padding-top:14px;padding-right:16px;padding-bottom:14px;padding-left:16px;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle )  > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap .kt-blocks-accordion-icon-trigger:after, .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle )  > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap .kt-blocks-accordion-icon-trigger:before{background:#eeeeee;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-blocks-accordion-icon-trigger{background:#eeeeee;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-blocks-accordion-icon-trigger:after, .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-blocks-accordion-icon-trigger:before{background:#313131;}.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header:hover, \n\t\t\t\tbody:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83 .kt-blocks-accordion-header:focus-visible{color:#444444;background:#eeeeee;border-top-color:#eeeeee;border-top-style:solid;border-right-color:#eeeeee;border-right-style:solid;border-bottom-color:#eeeeee;border-bottom-style:solid;border-left-color:#eeeeee;border-left-style:solid;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle ) .kt-accordion-header-wrap .kt-blocks-accordion-header:hover .kt-blocks-accordion-icon-trigger:after, .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle ) .kt-accordion-header-wrap .kt-blocks-accordion-header:hover .kt-blocks-accordion-icon-trigger:before, body:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle ) .kt-blocks-accordion--visible .kt-blocks-accordion-icon-trigger:after, body:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle ) .kt-blocks-accordion-header:focus-visible .kt-blocks-accordion-icon-trigger:before{background:#444444;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-accordion-header-wrap .kt-blocks-accordion-header:hover .kt-blocks-accordion-icon-trigger, body:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-accordion-header-wrap .kt-blocks-accordion-header:focus-visible .kt-blocks-accordion-icon-trigger{background:#444444;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-accordion-header-wrap .kt-blocks-accordion-header:hover .kt-blocks-accordion-icon-trigger:after, .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-accordion-header-wrap .kt-blocks-accordion-header:hover .kt-blocks-accordion-icon-trigger:before, body:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-accordion-header-wrap .kt-blocks-accordion-header:focus-visible .kt-blocks-accordion-icon-trigger:after, body:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-accordion-header-wrap .kt-blocks-accordion-header:focus-visible .kt-blocks-accordion-icon-trigger:before{background:#eeeeee;}.kt-accordion-id952_9c101e-83 .kt-accordion-header-wrap .kt-blocks-accordion-header:focus-visible,\n\t\t\t\t.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header.kt-accordion-panel-active{color:#313131;background:#eeeeee;border-top-color:#abb8c3;border-top-style:solid;border-right-color:#abb8c3;border-right-style:solid;border-bottom-color:#abb8c3;border-bottom-style:solid;border-left-color:#abb8c3;border-left-style:solid;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle )  > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header.kt-accordion-panel-active .kt-blocks-accordion-icon-trigger:after, .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basiccircle ):not( .kt-accodion-icon-style-xclosecircle ):not( .kt-accodion-icon-style-arrowcircle )  > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header.kt-accordion-panel-active .kt-blocks-accordion-icon-trigger:before{background:#313131;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-blocks-accordion-header.kt-accordion-panel-active .kt-blocks-accordion-icon-trigger{background:#313131;}.kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-blocks-accordion-header.kt-accordion-panel-active .kt-blocks-accordion-icon-trigger:after, .kt-accordion-id952_9c101e-83:not( .kt-accodion-icon-style-basic ):not( .kt-accodion-icon-style-xclose ):not( .kt-accodion-icon-style-arrow ) .kt-blocks-accordion-header.kt-accordion-panel-active .kt-blocks-accordion-icon-trigger:before{background:#eeeeee;}@media all and (max-width: 1024px){.kt-accordion-id952_9c101e-83 .kt-accordion-panel-inner{border-top:0px solid transparent;border-right:0px solid transparent;border-bottom:0px solid transparent;border-left:0px solid transparent;}}@media all and (max-width: 1024px){.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header{border-top-color:#555555;border-top-style:solid;border-right-color:#555555;border-right-style:solid;border-bottom-color:#555555;border-bottom-style:solid;border-left-color:#555555;border-left-style:solid;}}@media all and (max-width: 1024px){.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header:hover, \n\t\t\t\tbody:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83 .kt-blocks-accordion-header:focus-visible{border-top-color:#eeeeee;border-top-style:solid;border-right-color:#eeeeee;border-right-style:solid;border-bottom-color:#eeeeee;border-bottom-style:solid;border-left-color:#eeeeee;border-left-style:solid;}}@media all and (max-width: 1024px){.kt-accordion-id952_9c101e-83 .kt-accordion-header-wrap .kt-blocks-accordion-header:focus-visible,\n\t\t\t\t.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header.kt-accordion-panel-active{border-top-color:#abb8c3;border-top-style:solid;border-right-color:#abb8c3;border-right-style:solid;border-bottom-color:#abb8c3;border-bottom-style:solid;border-left-color:#abb8c3;border-left-style:solid;}}@media all and (max-width: 767px){.kt-accordion-id952_9c101e-83 .kt-accordion-inner-wrap{display:block;}.kt-accordion-id952_9c101e-83 .kt-accordion-inner-wrap .kt-accordion-pane:not(:first-child){margin-top:10px;}.kt-accordion-id952_9c101e-83 .kt-accordion-panel-inner{border-top:0px solid transparent;border-right:0px solid transparent;border-bottom:0px solid transparent;border-left:0px solid transparent;}.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header{border-top-color:#555555;border-top-style:solid;border-right-color:#555555;border-right-style:solid;border-bottom-color:#555555;border-bottom-style:solid;border-left-color:#555555;border-left-style:solid;}.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header:hover, \n\t\t\t\tbody:not(.hide-focus-outline) .kt-accordion-id952_9c101e-83 .kt-blocks-accordion-header:focus-visible{border-top-color:#eeeeee;border-top-style:solid;border-right-color:#eeeeee;border-right-style:solid;border-bottom-color:#eeeeee;border-bottom-style:solid;border-left-color:#eeeeee;border-left-style:solid;}.kt-accordion-id952_9c101e-83 .kt-accordion-header-wrap .kt-blocks-accordion-header:focus-visible,\n\t\t\t\t.kt-accordion-id952_9c101e-83 > .kt-accordion-inner-wrap > .wp-block-kadence-pane > .kt-accordion-header-wrap > .kt-blocks-accordion-header.kt-accordion-panel-active{border-top-color:#abb8c3;border-top-style:solid;border-right-color:#abb8c3;border-right-style:solid;border-bottom-color:#abb8c3;border-bottom-style:solid;border-left-color:#abb8c3;border-left-style:solid;}}<\/style>\n<div class=\"wp-block-kadence-accordion alignnone\"><div class=\"kt-accordion-wrap kt-accordion-id952_9c101e-83 kt-accordion-has-45-panes kt-active-pane-0 kt-accordion-block kt-pane-header-alignment-left kt-accodion-icon-style-basic kt-accodion-icon-side-right\" style=\"max-width:none\"><div class=\"kt-accordion-inner-wrap\" data-allow-multiple-open=\"true\" data-start-open=\"none\">\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-1 kt-pane952_a84136-28\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #1 &#8211; Due Tue Jan 27<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read<\/strong> the syllabus above, and my <a rel=\"noreferrer noopener\" href=\"https:\/\/math.hmc.edu\/su\/wp-content\/uploads\/sites\/10\/2020\/08\/Guidelines-for-Good-Mathematical-Writing.pdf\" target=\"_blank\">handout on good mathematical writing<\/a>. And <a href=\"http:\/\/www.scientificamerican.com\/article\/the-secret-to-raising-smart-kids1\/\">this article<\/a> if you haven&#8217;t seen it before.<\/p>\n\n\n\n<p><strong>Read<\/strong> Levin <a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4\/ch_counting.html\" target=\"_blank\" rel=\"noreferrer noopener\">Sections 3.1-3.4<\/a>.<\/p>\n\n\n\n<p><strong>Answer the following:<\/strong><\/p>\n\n\n\n<p><strong>Q1.<\/strong> Based on the <a href=\"https:\/\/math.hmc.edu\/su\/wp-content\/uploads\/sites\/10\/2020\/08\/Guidelines-for-Good-Mathematical-Writing.pdf\">handout<\/a>, why is it important to write in complete sentences?<\/p>\n\n\n\n<p><strong>Q2.<\/strong> What qualities characterize a well-written solution?<\/p>\n\n\n\n<p><strong>Q3.<\/strong> Describe the difference in meaning between these three sentences: <br>&#8220;Let A=B.&#8221; <br>&#8220;Therefore A=B.&#8221; <br>&#8220;A=B.&#8221;<\/p>\n\n\n\n<p>Also, do the following problems from Levin at end of each Section. The numbers refer to what Levin calls <strong>&#8220;Practice Problems&#8221;<\/strong>, unless it is marked with an <strong>&#8220;a&#8221;<\/strong> which refers to <strong>&#8220;Additional Problems&#8221;<\/strong>. <\/p>\n\n\n\n<p>Levin <strong>3.2 ( 2, a2 ) 3.3 ( 3, 7, 8, a2 )<\/strong><\/p>\n\n\n\n<p>IMPORTANT: the problems refer to the <a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4\/dmoi4.html\" target=\"_blank\" rel=\"noreferrer noopener\">interactive online ebook<\/a>. Do NOT use the PDF, because it has different problems.<\/p>\n\n\n\n<p>(Note that the ebook version offers interactive opportunities to check your answers on some problems, but on your submitted solutions you will need to do more than just give answers. You will need to explain your reasoning well in order to get full credit. Caution: pressing the &#8220;Activate&#8221; button on a problem may change the problem, especially if you select &#8216;randomize&#8217;. But you should solve the original problem, which you can see by pressing &#8216;Reset&#8217;.)<\/p>\n\n\n\n<p>Submit your homework on Gradescope (see link above).<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-32 kt-pane952_8e8823-70\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #2 &#8211; Due Tue Feb 3<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read<\/strong> Levin <a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4\/ch_counting.html\">Sections 3.5-3.6<\/a>.<\/p>\n\n\n\n<p>Do the following:<\/p>\n\n\n\n<p><strong>Levin 3.1 ( 7, 10, a1 ) 3.4 ( 4, 8, a1 ) 3.6 ( a3, a9, a13 ).<\/strong><\/p>\n\n\n\n<p>Note on problem 3.4.8: the Board members are part of the group of businesspeople.<\/p>\n\n\n\n<p>IMPORTANT: the problems refer to the <a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4\/dmoi4.html\" target=\"_blank\" rel=\"noreferrer noopener\">interactive online ebook<\/a>. Do NOT use the PDF, because it has different problems.<\/p>\n\n\n\n<p>The ebook offers interactive opportunities to check answers on many problems. You can use expressions like n! or * (times) or even C(n,k) for (n choose k) and it will evaluate them properly. But in your solutions you must give more explanation than just the answers&#8212;you should justify each answer.<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-33 kt-pane952_97f7c9-7c\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #3 &#8211; due Tue Feb 10<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read<\/strong> Levin <a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4\/ch_counting.html\">Sections 3.5-3.6, 3.8.<\/a><\/p>\n\n\n\n<p><strong>Do the following:<\/strong><\/p>\n\n\n\n<p><strong>Levin 3.5 ( 6, 9, a2 ) 3.6 ( a6, a8 ) 3.8 ( 2, 3, 8, a2 )<\/strong><\/p>\n\n\n\n<p>You may express answers in (n choose k) notation but do not leave answers in multichoose notation.<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-34 kt-pane952_c35cb3-09\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #4 &#8211; due Tue Feb 17<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read<\/strong> Levin <a href=\"https:\/\/discrete.openmathbooks.org\/dmoi4\/sec_seq-induction.html\">Sections 4.5 and 4.6<\/a>.<\/p>\n\n\n\n<p><strong>Do the following:<\/strong><\/p>\n\n\n\n<p><strong>Levin 4.5 ( a6, a7, a9, a11, a12, a14 ) 4.6 ( a6, a8 ) and:<\/strong><\/p>\n\n\n\n<p><strong>Question A.<\/strong> In just a few sentences, state 2 things you find notable or interesting about induction arguments that you hadn&#8217;t appreciated before.<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-35 kt-pane952_e95ea7-dd\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #5 &#8211; due Tue Feb 24<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read<\/strong> Levin Section 4.1 and 4.4.<\/p>\n\n\n\n<p><strong>Do the following:<\/strong><\/p>\n\n\n\n<p><strong>Levin 4.1 ( 4, a12) 4.4 ( 4, a3, a4, a7 ) and Questions B and C and D below<\/strong>:<\/p>\n\n\n\n<p><strong>Question B. <\/strong>Recall the field goals and touchdown problem from the last problem set (2.5.9).&nbsp;<\/p>\n\n\n\n<p>a. Let <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=a_n+%3D+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"a_n = \" class=\"latex\" \/> the number of ways to get <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> points using just 3-point field goals. Explain why this sequence has generating function <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=A%28x%29+%3D+1%2B+x%5E3+%2B+x%5E6+%2B+x%5E9+%2B+%5Ccdots&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"A(x) = 1+ x^3 + x^6 + x^9 + &#92;cdots\" class=\"latex\" \/> and then explain why this expression is equal to <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=1%2F%281-x%5E3%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"1\/(1-x^3)\" class=\"latex\" \/>.<\/p>\n\n\n\n<p>b. Similarly, let <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=b_n+%3D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"b_n =\" class=\"latex\" \/> the number of ways to get <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> points using 7-point touchdowns. Explain why this sequence has generating function <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=B%28x%29%3D1%2F%281-x%5E7%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"B(x)=1\/(1-x^7)\" class=\"latex\" \/>.<\/p>\n\n\n\n<p>c. Let <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=c_n+%3D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"c_n =\" class=\"latex\" \/> the number of ways to get <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> points using both field goals and touchdowns. This sequence has generating function <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=C%28x%29%3DA%28x%29B%28x%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"C(x)=A(x)B(x)\" class=\"latex\" \/>. Use this Wolfram Alpha <a href=\"https:\/\/www.wolframalpha.com\/input?i=series+expansion+of+1%2F%28%281-x%5E3%29*%281-x%5E7%29%29\">link<\/a> to compute its power series. Under \u201cSeries Expansion at x=0\u201d look for the button \u201cMore terms\u201d and press it 3 times to see more of the series. Explain why the series is missing a term for <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x%5E%7B11%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"x^{11}\" class=\"latex\" \/> and why the series has a coefficient of 2 for <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x%5E%7B21%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"x^{21}\" class=\"latex\" \/>.<\/p>\n\n\n\n<p><strong>Question C. <\/strong>Write out the generating function <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=K%28x%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"K(x)\" class=\"latex\" \/> for the Fibonacci Sequence: <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=F_0%3D0%2C+F_1%3D1&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"F_0=0, F_1=1\" class=\"latex\" \/>, and <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=F_n%3DF_%7Bn-1%7D%2BF_%7Bn-2%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"F_n=F_{n-1}+F_{n-2}\" class=\"latex\" \/>.&nbsp; Then show <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=K%28x%29+%3D+x%2F%281-x-x%5E2%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"K(x) = x\/(1-x-x^2)\" class=\"latex\" \/>.<\/p>\n\n\n\n<p><strong>Question D.<\/strong> Sicherman dice are a pair of six-sided dice with non-standard numbers. One die has faces 1, 2, 2, 3, 3, 4, and the other has faces 1, 3, 4, 5, 6, 8.&nbsp;Use generating functions to explain why this pair of dice together behaves the same way as a pair of standard dice (i.e., the number of ways to get the sum N is the same for a pair of Sicherman dice as for a pair of regular dice). Feel free to use a computational tool (like Wolfram Alpha, which can multiply polynomials).<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-38 kt-pane952_290e0f-46\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #6 &#8211; due Tue Mar 3<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Problem 6A<\/strong>. For integers <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=a%2C+b&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"a, b\" class=\"latex\" \/> where <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=a%3C0&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"a&lt;0\" class=\"latex\" \/>, show that the set <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=A+%3D+%5C%7B+n+%5Cin+%7B%5Cmathbb+Z%7D+%3A+a+-+n+b+%5Cgeq+0+%5C%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"A = &#92;{ n &#92;in {&#92;mathbb Z} : a - n b &#92;geq 0 &#92;}\" class=\"latex\" \/> is not empty by producing a specific integer <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> that works for each case: <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=b%3C0&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"b&lt;0\" class=\"latex\" \/> and <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=b+%3E+0&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"b &gt; 0\" class=\"latex\" \/>. (This fact can be used to prove the division algorithm for the case where <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=a%3C0&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"a&lt;0\" class=\"latex\" \/>.)<\/p>\n\n\n\n<p><strong>Problem 6B.<\/strong> Consider the cubes: 1, 8, 27, 64, 125, 216 &#8230; When divided by 9, what remainders are possible? Show that a cube of the form <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%283m%2B1%29%5E3&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"(3m+1)^3\" class=\"latex\" \/> for an integer <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=m&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"m\" class=\"latex\" \/>) must have remainder 1 when divided by 9.<\/p>\n\n\n\n<p><strong>Problem 6C.<\/strong> Prove the <strong>Integer Combination Theorem<\/strong> that we discussed in class: If d|a and d|b, then for any integers x and y, show that d|(ax+by).<\/p>\n\n\n\n<p><em>Hint:<\/em> you&#8217;ll want to appeal to the definition of &#8220;divides&#8221;.<\/p>\n\n\n\n<p><strong>Problem 6D. <\/strong>Find gcd(300, 18) using the Euclidean algorithm. Then find integers x and y such that 300x + 18y = gcd(300, 18) using the method discussed in class.<\/p>\n\n\n\n<p><strong>Problem 6E.<\/strong> Use the Euclidean algorithm to find the gcd of consecutive Fibonacci Numbers: <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=gcd%28F_%7Bn%7D%2C+F_%7Bn%2B1%7D%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"gcd(F_{n}, F_{n+1})\" class=\"latex\" \/>.<\/p>\n\n\n\n<p><strong>Problem 6F.<\/strong> Let N be a positive integer. By looking at examples, make a conjecture about gcd(N, N+1), then prove it.<\/p>\n\n\n\n<p><strong>Problem 6G.<\/strong> A <em>prime<\/em> is a positive integer greater than 1 that has no other positive divisors besides itself and 1. Show that every number N &gt; 1 can be expressed as a (finite) product of primes.<\/p>\n\n\n\n<p><em>Hint:<\/em> Do this by strong induction on N. Thus your inductive hypothesis will be: &#8220;Assume that this can be done for all N less than or equal to K.&#8221; Then in the inductive step, you&#8217;ll want to show that it can be done for N=K+1.<\/p>\n\n\n\n<p>(We use this fact as a starting point for the proof that the factorization is actually unique.)<\/p>\n\n\n\n<p><strong>Problem 6H. <\/strong>The primes less than 15 are 2, 3, 5, 7, 11, 13. Use this list to determine whether the number 221 is prime by: <br>(a) checking if any prime on the list are divisors of 221, and<br>(b) explaining why you do not have to check if any other numbers are divisors of 221.<br>(Hint: if 221 had any factors &gt;= 15, why would have to have a prime factor smaller than 15?)<\/p>\n\n\n\n<p><strong>Problem 6I. <\/strong>How many divisors does a prime power <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=p%5En&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"p^n\" class=\"latex\" \/> have? How many divisors does a product of <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=k&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"k\" class=\"latex\" \/> distinct primes (like <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=p_1+p_2+%5Ccdots+p_k&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"p_1 p_2 &#92;cdots p_k\" class=\"latex\" \/>) have? Explain why.<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-37 kt-pane952_7bcc9d-a7\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">Exam<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p>The exam has 2 components. One portion will be in class on Mar 9, which should take less than one hour. The other portion will be take-home due Mar 12.<\/p>\n\n\n\n<p>An 8.5&#215;11 sheet of notes (front and back, prepared by you) will be allowed, but do not use anything else during the exam period (no internet, no AI, etc).<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-39 kt-pane952_c455da-e9\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #7 &#8211; due Tue Mar 31<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Problem 7A<\/strong>. Find gcd(300, 18) and lcm(300, 18) by first factoring 300 and 18 into primes to find the gcd, and then using the gcd-lcm theorem to find the lcm.<\/p>\n\n\n\n<p><strong>Problem 7B. <\/strong>Show that if a number <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"N\" class=\"latex\" \/> is composite, then it must have a prime factor less than or equal to <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Csqrt%7BN%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;sqrt{N}\" class=\"latex\" \/>. (Hint: if the conclusion were false, show that leads to a contradiction.)<\/p>\n\n\n\n<p><strong>Problem 7C. <\/strong>How many prime numbers are there between 1 and 100, inclusive? Between 1001 and 1100, inclusive? Between 10001 and 10100 inclusive? [Feel free to consult <a href=\"https:\/\/cis.temple.edu\/~beigel\/cis573\/alizzy\/prime-list.html\">a list of primes<\/a>.] How do the actual counts compare to the number of primes predicted by the Prime Number Theorem? Recall that the Prime Number Theorem says that the function <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=pi%28N%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"pi(N)\" class=\"latex\" \/>, the number of primes less than or equal to <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"N\" class=\"latex\" \/>, is approximately <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=N%2Fln%28N%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"N\/ln(N)\" class=\"latex\" \/>.<\/p>\n\n\n\n<p><strong>Problem 7D. <\/strong>Without a calculator, determine: (a) 2143 mod 10, (b) 2143 mod 5, (c) 2143 mod 7.<\/p>\n\n\n\n<p><strong>Problem 7E. <\/strong>Without a calculator, determine <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=2143%5E%7B2143%7D+%5Cmod+7&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"2143^{2143} &#92;mod 7\" class=\"latex\" \/>.<\/p>\n\n\n\n<p><strong>Problem 7F. <\/strong>Without a calculator, determine the last digit of <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=2143%5E%7B2143%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"2143^{2143}\" class=\"latex\" \/>.<\/p>\n\n\n\n<p><strong>Problem 7G. <\/strong>You have 1205 crates of soda cans. Each crate has 16 soda cans in it. You have to repackage all the soda cans into packages of 12 cans each. After making as many complete packages as possible, how many soda cans will be left over? Solve this problem without a calculator, and make your life easy using (mod 12) arithmetic.<\/p>\n\n\n\n<p><strong>Problem 7H. <\/strong>Use Wilson&#8217;s theorem to help you find the remainder when 99! is divided by 101.<\/p>\n\n\n\n<p><strong>Problem 7I. <\/strong>Show that the equation <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x%5E4+%2B+1+%3D+3+y%5E4&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"x^4 + 1 = 3 y^4\" class=\"latex\" \/> can never be solved in integers x and y. <br>(Hint: if the equation cannot be solved in integers mod 5, it cannot be solved in integers. Also, 5 is prime.)<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-45 kt-pane952_d1facc-2e\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #8 &#8211; due Tue Apr 7<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Problem 8A. <\/strong>(a) Fill out a multiplication table for numbers mod 8. Which numbers mod 8 have inverses? In which rows do all the numbers 0, 1, 2, &#8230; , 7 appear exactly once? Explain what you see. <br>(b) Fill out a multiplication table for numbers mod 9. Which numbers mod 9 have inverses? In which rows do all the numbers 0, 1, 2, &#8230; , 8 appear exactly once? Explain what you see.<\/p>\n\n\n\n<p><strong>Problem 8B.<\/strong> Fill out a table of powers of numbers mod 7, like so:<br><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cunderline%7B+n+%7C+n%5E2+n%5E3+n%5E4+n%5E5+n%5E6+n%5E7+%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;underline{ n | n^2 n^3 n^4 n^5 n^6 n^7 }\" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=0+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"0 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=1+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"1 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=2+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"2 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=3+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"3 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=4+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"4 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=5+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"5 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=6+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"6 | \" class=\"latex\" \/><br>Then notice: which numbers mod 7 have some power equal to 1? And explain how one of the columns in your table shows the truth of Fermat&#8217;s Theorem.<\/p>\n\n\n\n<p><strong>Problem 8C.<\/strong> Fill out a table of powers of numbers mod 6, like so:<br><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cunderline%7B+n+%7C+n%5E2+n%5E3+n%5E4+n%5E5+n%5E6%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;underline{ n | n^2 n^3 n^4 n^5 n^6}\" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=0+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"0 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=1+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"1 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=2+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"2 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=3+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"3 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=4+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"4 | \" class=\"latex\" \/><br><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=5+%7C+&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"5 | \" class=\"latex\" \/><br>Then notice: which numbers mod 6 have some power equal to 1? And explain how one (or more) of the columns in your table show the truth of Euler&#8217;s Theorem.<\/p>\n\n\n\n<p><strong>Problem 8D.<\/strong> Mod 11, the inverse of 3 is 4. Solve the congruence <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=3+x+%5Cequiv+7+%5Cmod+11&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"3 x &#92;equiv 7 &#92;mod 11\" class=\"latex\" \/> by multiplying both sides of the congruence by 4 and finding <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=x&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"x\" class=\"latex\" \/>.<\/p>\n\n\n\n<p><strong>Problem 8E. <\/strong>According to Euler&#8217;s theorem, if <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cgcd%28a%2CN%29%3D1&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;gcd(a,N)=1\" class=\"latex\" \/>, then <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=a%5E%7B%5Cphi%28N%29%7D+%5Cequiv+1+%5Cmod+N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"a^{&#92;phi(N)} &#92;equiv 1 &#92;mod N\" class=\"latex\" \/>. This gives us a method for finding the inverse of a number <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=a&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"a\" class=\"latex\" \/> as <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=a%5E%7B%5Cphi%28N%29-1%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"a^{&#92;phi(N)-1}\" class=\"latex\" \/>. Mod 7, which column in the table of Problem BB gives the inverses of n? Verify that these are, in fact, inverses of the corresponding numbers.<\/p>\n\n\n\n<p><strong>Problem 8F.<\/strong> Look at <a href=\"https:\/\/proofwiki.org\/wiki\/Euler_Phi_Function\/Table\">this table<\/a> of Euler&#8217;s totient function. For which <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"N\" class=\"latex\" \/> is <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cphi%28N%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;phi(N)\" class=\"latex\" \/> an even number? Make a conjecture and prove it.<\/p>\n\n\n\n<p><strong>Problem 8G.<\/strong> The Google search function will find 66^2 mod 119 by <a href=\"https:\/\/www.google.com\/search?q=66%5E2+mod+119\">typing it in the search box, like this<\/a>. But it won&#8217;t compute 66^77 mod 119, because the power is too large. So compute 66^77 mod 119 by the method discussed in class to compute large powers, using the fact that 77 = 64+8+4+1, because the binary expansion of 77 is 1001101. (Feel free to use Google to compute squares mod 119 when needed.)<\/p>\n\n\n\n<p><strong>Problem 8H.<\/strong> Using N=119, determine <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cphi%28N%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;phi(N)\" class=\"latex\" \/> and verify that the public key E=5 is relatively prime to <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cphi%28N%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;phi(N)\" class=\"latex\" \/>. Then determine the corresponding private key D, where 0&lt;=D&lt; <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cphi%28N%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;phi(N)\" class=\"latex\" \/>, that corresponds to E. (You can find D from E the same way that you can find E from D as discussed in the class notes.)<\/p>\n\n\n\n<p><strong>Problem 8I.<\/strong> Using the N and the public key E in the prior problem, encrypt the message M=19 to get an encrypted message C. What is C? Then use the private key D you found in the prior problem to decrypt C and verify that you get M.<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-18 kt-pane952_bc75c2-4f\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\"><mark class=\"kt-highlight\">=== Below this line: homeworks are tentative ===<\/mark><\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p>Below this line, all homeworks are <strong>TENTATIVE<\/strong>. This means they are likely to be assigned, but there is no guarantee that they will until you see them moved above.<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-40 kt-pane952_b7ee1f-0d\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #9 &#8211; due Tue Apr 14<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read<\/strong>: Levin Sections 2.1 and 2.4. <\/p>\n\n\n\n<p><strong>Do the following:<\/strong> <br><strong>Levin 2.1 ( a3, a5 , a13, a14, a15 ) and 2.4 ( a1, a3. a4, a10 )<\/strong><\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-41 kt-pane952_99e159-c1\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #10 &#8211; due Tue Apr 21<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read <\/strong>Levin Sections 2.2 and 2.3<\/p>\n\n\n\n<p><strong>Do the following:<\/strong><\/p>\n\n\n\n<p><strong>Levin 2.1 ( a7 )<\/strong> You&#8217;ll need to read the section to learn the definition of <em>bipartitite<\/em>.<br><strong>Levin 2.2 ( a3, a4, a7, a9 )<\/strong> <br><strong>Levin 2.3 ( a2, a3, a5, a11 )<\/strong><\/p>\n\n\n\n<p>I&#8217;m not a fan of the <em>minimal criminal<\/em> terminology from the text. It refers to a minimal counterexample, as you can see from reading section 2.2.<\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-42 kt-pane952_a3ea0d-b9\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">HW #11 &#8211; due Tue Apr 28 (no extension)<\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p><strong>Read <\/strong>Levin <strong>Section 2.5.<\/strong><\/p>\n\n\n\n<p><strong>Do the following:<\/strong><\/p>\n\n\n\n<p><strong>Problem Z.&nbsp;<\/strong>Answer the second &#8220;Investigate!&#8221; problem in the Section 2.5, about the math department&#8217;s 10 classes.&nbsp;<strong>Also do:<\/strong> Levin 2.5&nbsp;(&nbsp; a3, a6 parts acd, a10, a11 ). See the notes on the problems below:<\/p>\n\n\n\n<p><strong>2.5.a3:<\/strong> In addition to giving the chromatic number of each graph, exhibit a coloring with that number of colors and give a brief argument why it can&#8217;t be fewer.<br><strong>2.5.a6:<\/strong> In part (a) color the tree with 2 colors. In part (c), use the fact that in a tree, paths between any 2 vertices are unique.<br><strong>2.5.a10:<\/strong> A hint here is to notice there are odd cycles in the graph.<br><strong>2.5.a11: <\/strong>You should assume G is a connected graph (the statement is false without this additional condition).<br><\/p>\n<\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-kadence-pane kt-accordion-pane kt-accordion-pane-44 kt-pane952_dd55df-7d\"><div class=\"kt-accordion-header-wrap\"><button class=\"kt-blocks-accordion-header kt-acccordion-button-label-show\" type=\"button\"><span class=\"kt-blocks-accordion-title-wrap\"><span class=\"kt-blocks-accordion-title\">Final Exam <\/span><\/span><span class=\"kt-blocks-accordion-icon-trigger\"><\/span><\/button><\/div><div class=\"kt-accordion-panel kt-accordion-panel-hidden\"><div class=\"kt-accordion-panel-inner\">\n<p>The exam will be in-person during Finals Week.<\/p>\n<\/div><\/div><\/div>\n<\/div><\/div><\/div>\n\n\n\n<div style=\"height:46px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Professor Francis SuSection 1, Spring 2026 Meetings: MW 1:15pm &#8211; 2:30pm Course Webpage: https:\/\/math.hmc.edu\/su\/math55\/ My Email: (my last name) at math.hmc.edu Graders: Joshua Zhong, Aidan Deshong, Lily Surjadinata can be reached at g.hmc.edu Office Hours: Mondays 3:30 &#8211; 5:00pm at my office (Shan 3416) or by appointment. Course Description This course is an introduction to [&hellip;]<\/p>\n","protected":false},"author":20,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[],"class_list":["post-952","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/pages\/952","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/comments?post=952"}],"version-history":[{"count":190,"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/pages\/952\/revisions"}],"predecessor-version":[{"id":1587,"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/pages\/952\/revisions\/1587"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/media?parent=952"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/su\/wp-json\/wp\/v2\/tags?post=952"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}