{"id":284,"date":"2019-09-27T11:06:20","date_gmt":"2019-09-27T16:06:20","guid":{"rendered":"http:\/\/blogs.acu.edu\/mu_sigma\/?p=284"},"modified":"2019-10-04T12:05:42","modified_gmt":"2019-10-04T17:05:42","slug":"problem-4-fall-2019-are-there-infinitely-many","status":"publish","type":"post","link":"https:\/\/blogs.acu.edu\/mu_sigma\/2019\/09\/27\/problem-4-fall-2019-are-there-infinitely-many\/","title":{"rendered":"Problem 4 &#8211; Fall 2019 &#8211; Are There Infinitely Many?"},"content":{"rendered":"<p><span style=\"font-size: xx-large\"><b>Are There Infinitely Many?<\/b><\/span><\/p>\n<p>Are there infinitely many positive integers <i>n<\/i> such that <i>n<\/i> divides (that is, is a factor of) the number <em>2^(n<\/em>)+1?<\/p>\n<p>Solutions are due by Thursday, Oct 3rd at 5:00 PM. \u00a0Please submit all solutions to mathpotw@acu.edu.<\/p>\n<p><span style=\"font-size: large\">Solution to <b>Are There Infinitely Many?<\/b><\/span><\/p>\n<p>A manual check discovers that <i>n<\/i> divides 2<i><sup>n<\/sup><\/i> + 1 for <i>n<\/i> = 1, 3, and 9. This is enough to cause a person to check the number <i>n<\/i> = 27 and find that it works also. So let&#8217;s proceed, using a proof by induction, to show that 3<sup><i>k<\/i><\/sup> divides 2<sup>3<i>k<\/i><\/sup> + 1 for every nonnegative integer <i>k<\/i>.<\/p>\n<p>We have observed that the statement is true for <i>k<\/i> = 0. Now suppose that it is true for some integer <i>k<\/i> &gt;= 0 and use this supposition to show that 3<sup><i>k<\/i>+1<\/sup>divides 2<sup>3<i>k<\/i>+1<\/sup> + 1. But 2<sup>3<i>k<\/i>+1<\/sup> + 1 can be rewritten as (2<sup>3<i>k<\/i><\/sup>)<sup>3<\/sup> + 1, an expression of the form <i>x<\/i><sup>3<\/sup> + 1, and this can be factored into (<i>x<\/i> + 1)(<i>x<\/i><sup>2<\/sup> &#8211; <i>x<\/i> + 1). So we let <i>x<\/i> = 2<sup>3<i>k<\/i><\/sup> and observe that by the induction hypothesis, 3<sup><i>k<\/i><\/sup> divides (<i>x<\/i> + 1). All that remains is to find a factor of 3 in the term (<i>x<\/i><sup>2<\/sup> &#8211; <i>x<\/i> + 1). But<\/p>\n<p>(<i>x<\/i><sup>2<\/sup> &#8211; <i>x<\/i> + 1) = ((<i>x<\/i>+1)<sup>2<\/sup> &#8211; 2<i>x<\/i> &#8211; 1 &#8211; <i>x<\/i> + 1) = ((<i>x<\/i>+1)<sup>2<\/sup> &#8211; 3<i>x<\/i>).Now we see that 3 is a factor of (<i>x<\/i><sup>2<\/sup> &#8211; <i>x<\/i> + 1) because of the induction hypothesis again. The proof is done.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Are There Infinitely Many? Are there infinitely many positive integers n such that n divides (that is, is a factor of) the number 2^(n)+1? Solutions are due by Thursday, Oct 3rd at 5:00 PM. \u00a0Please submit all solutions to mathpotw@acu.edu. Solution to Are There Infinitely Many? A manual check discovers that n divides 2n + [&hellip;]<\/p>\n","protected":false},"author":130,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[181534],"tags":[],"class_list":["post-284","post","type-post","status-publish","format-standard","hentry","category-problem-of-the-week"],"_links":{"self":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts\/284","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/users\/130"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/comments?post=284"}],"version-history":[{"count":5,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts\/284\/revisions"}],"predecessor-version":[{"id":296,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts\/284\/revisions\/296"}],"wp:attachment":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/media?parent=284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/categories?post=284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/tags?post=284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}