Prove that $3^{2n} +7$ is divisible by 8












1












$begingroup$



Prove by induction that $3^{2n} +7$ is divisible by 8 for $n in Bbb N$



So I think I have completed this proof but it doesn't seem very thorough to me - is my proof valid?




If $n=1$ then $3^{2n} +7 = 16 = 2(8)$ so true when $n=1$



Assume true for $n=k$ so $$ 8vert 3^{2k} +7$$



If $n=k+1$
$$3^{2(k+1)} +7$$
$$3^{2k+2} +7$$
If $3^{2n} +7$ is divisble by 8 then $3^{2n} +7=8A$ where $A in Bbb Z$, and thus $3^{2k+2} +7=8B$ where $B in Bbb Z$
$$3^2 times 3^{2k}+7$$
$$3^2 times (8A)=72A$$
$$72A =8(9A)=9B$$



So by induction $3^{2n} +7$ is divisibe by 8 $forall n in Bbb N$










share|cite|improve this question











$endgroup$












  • $begingroup$
    Not following. Yes, you may assume (inductively) that $3^{2n}+7=8A$ and yes, you want to argue that this implies that $3^{3k+2}+7=8B$, but where do you argue that? It is simply not true that $3^2times 3^{2k}+7=3^2times (8A)$.
    $endgroup$
    – lulu
    Jan 9 at 18:57












  • $begingroup$
    Do you know modular arithmetic / congruences?
    $endgroup$
    – Bill Dubuque
    Jan 9 at 18:59










  • $begingroup$
    You made an error. Note that $3^2cdot 3^{2k}+7 color{red}{neq 3^2cdot left(3^{2k}+7right)}$.
    $endgroup$
    – KM101
    Jan 9 at 18:59












  • $begingroup$
    Not relevant to the proof by induction, but it is worth noting that there is a very simple proof of this fact using basic binomial expansion: $3^{2n}+7=9^n+7=(1+8)^n+7$ and after expansion all your terms are divisible by $8$.
    $endgroup$
    – AlephNull
    Jan 9 at 19:03
















1












$begingroup$



Prove by induction that $3^{2n} +7$ is divisible by 8 for $n in Bbb N$



So I think I have completed this proof but it doesn't seem very thorough to me - is my proof valid?




If $n=1$ then $3^{2n} +7 = 16 = 2(8)$ so true when $n=1$



Assume true for $n=k$ so $$ 8vert 3^{2k} +7$$



If $n=k+1$
$$3^{2(k+1)} +7$$
$$3^{2k+2} +7$$
If $3^{2n} +7$ is divisble by 8 then $3^{2n} +7=8A$ where $A in Bbb Z$, and thus $3^{2k+2} +7=8B$ where $B in Bbb Z$
$$3^2 times 3^{2k}+7$$
$$3^2 times (8A)=72A$$
$$72A =8(9A)=9B$$



So by induction $3^{2n} +7$ is divisibe by 8 $forall n in Bbb N$










share|cite|improve this question











$endgroup$












  • $begingroup$
    Not following. Yes, you may assume (inductively) that $3^{2n}+7=8A$ and yes, you want to argue that this implies that $3^{3k+2}+7=8B$, but where do you argue that? It is simply not true that $3^2times 3^{2k}+7=3^2times (8A)$.
    $endgroup$
    – lulu
    Jan 9 at 18:57












  • $begingroup$
    Do you know modular arithmetic / congruences?
    $endgroup$
    – Bill Dubuque
    Jan 9 at 18:59










  • $begingroup$
    You made an error. Note that $3^2cdot 3^{2k}+7 color{red}{neq 3^2cdot left(3^{2k}+7right)}$.
    $endgroup$
    – KM101
    Jan 9 at 18:59












  • $begingroup$
    Not relevant to the proof by induction, but it is worth noting that there is a very simple proof of this fact using basic binomial expansion: $3^{2n}+7=9^n+7=(1+8)^n+7$ and after expansion all your terms are divisible by $8$.
    $endgroup$
    – AlephNull
    Jan 9 at 19:03














1












1








1





$begingroup$



Prove by induction that $3^{2n} +7$ is divisible by 8 for $n in Bbb N$



So I think I have completed this proof but it doesn't seem very thorough to me - is my proof valid?




If $n=1$ then $3^{2n} +7 = 16 = 2(8)$ so true when $n=1$



Assume true for $n=k$ so $$ 8vert 3^{2k} +7$$



If $n=k+1$
$$3^{2(k+1)} +7$$
$$3^{2k+2} +7$$
If $3^{2n} +7$ is divisble by 8 then $3^{2n} +7=8A$ where $A in Bbb Z$, and thus $3^{2k+2} +7=8B$ where $B in Bbb Z$
$$3^2 times 3^{2k}+7$$
$$3^2 times (8A)=72A$$
$$72A =8(9A)=9B$$



So by induction $3^{2n} +7$ is divisibe by 8 $forall n in Bbb N$










share|cite|improve this question











$endgroup$





Prove by induction that $3^{2n} +7$ is divisible by 8 for $n in Bbb N$



So I think I have completed this proof but it doesn't seem very thorough to me - is my proof valid?




If $n=1$ then $3^{2n} +7 = 16 = 2(8)$ so true when $n=1$



Assume true for $n=k$ so $$ 8vert 3^{2k} +7$$



If $n=k+1$
$$3^{2(k+1)} +7$$
$$3^{2k+2} +7$$
If $3^{2n} +7$ is divisble by 8 then $3^{2n} +7=8A$ where $A in Bbb Z$, and thus $3^{2k+2} +7=8B$ where $B in Bbb Z$
$$3^2 times 3^{2k}+7$$
$$3^2 times (8A)=72A$$
$$72A =8(9A)=9B$$



So by induction $3^{2n} +7$ is divisibe by 8 $forall n in Bbb N$







elementary-number-theory induction divisibility






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 9 at 21:35









Maria Mazur

49.7k1361124




49.7k1361124










asked Jan 9 at 18:54









H.LinkhornH.Linkhorn

485213




485213












  • $begingroup$
    Not following. Yes, you may assume (inductively) that $3^{2n}+7=8A$ and yes, you want to argue that this implies that $3^{3k+2}+7=8B$, but where do you argue that? It is simply not true that $3^2times 3^{2k}+7=3^2times (8A)$.
    $endgroup$
    – lulu
    Jan 9 at 18:57












  • $begingroup$
    Do you know modular arithmetic / congruences?
    $endgroup$
    – Bill Dubuque
    Jan 9 at 18:59










  • $begingroup$
    You made an error. Note that $3^2cdot 3^{2k}+7 color{red}{neq 3^2cdot left(3^{2k}+7right)}$.
    $endgroup$
    – KM101
    Jan 9 at 18:59












  • $begingroup$
    Not relevant to the proof by induction, but it is worth noting that there is a very simple proof of this fact using basic binomial expansion: $3^{2n}+7=9^n+7=(1+8)^n+7$ and after expansion all your terms are divisible by $8$.
    $endgroup$
    – AlephNull
    Jan 9 at 19:03


















  • $begingroup$
    Not following. Yes, you may assume (inductively) that $3^{2n}+7=8A$ and yes, you want to argue that this implies that $3^{3k+2}+7=8B$, but where do you argue that? It is simply not true that $3^2times 3^{2k}+7=3^2times (8A)$.
    $endgroup$
    – lulu
    Jan 9 at 18:57












  • $begingroup$
    Do you know modular arithmetic / congruences?
    $endgroup$
    – Bill Dubuque
    Jan 9 at 18:59










  • $begingroup$
    You made an error. Note that $3^2cdot 3^{2k}+7 color{red}{neq 3^2cdot left(3^{2k}+7right)}$.
    $endgroup$
    – KM101
    Jan 9 at 18:59












  • $begingroup$
    Not relevant to the proof by induction, but it is worth noting that there is a very simple proof of this fact using basic binomial expansion: $3^{2n}+7=9^n+7=(1+8)^n+7$ and after expansion all your terms are divisible by $8$.
    $endgroup$
    – AlephNull
    Jan 9 at 19:03
















$begingroup$
Not following. Yes, you may assume (inductively) that $3^{2n}+7=8A$ and yes, you want to argue that this implies that $3^{3k+2}+7=8B$, but where do you argue that? It is simply not true that $3^2times 3^{2k}+7=3^2times (8A)$.
$endgroup$
– lulu
Jan 9 at 18:57






$begingroup$
Not following. Yes, you may assume (inductively) that $3^{2n}+7=8A$ and yes, you want to argue that this implies that $3^{3k+2}+7=8B$, but where do you argue that? It is simply not true that $3^2times 3^{2k}+7=3^2times (8A)$.
$endgroup$
– lulu
Jan 9 at 18:57














$begingroup$
Do you know modular arithmetic / congruences?
$endgroup$
– Bill Dubuque
Jan 9 at 18:59




$begingroup$
Do you know modular arithmetic / congruences?
$endgroup$
– Bill Dubuque
Jan 9 at 18:59












$begingroup$
You made an error. Note that $3^2cdot 3^{2k}+7 color{red}{neq 3^2cdot left(3^{2k}+7right)}$.
$endgroup$
– KM101
Jan 9 at 18:59






$begingroup$
You made an error. Note that $3^2cdot 3^{2k}+7 color{red}{neq 3^2cdot left(3^{2k}+7right)}$.
$endgroup$
– KM101
Jan 9 at 18:59














$begingroup$
Not relevant to the proof by induction, but it is worth noting that there is a very simple proof of this fact using basic binomial expansion: $3^{2n}+7=9^n+7=(1+8)^n+7$ and after expansion all your terms are divisible by $8$.
$endgroup$
– AlephNull
Jan 9 at 19:03




$begingroup$
Not relevant to the proof by induction, but it is worth noting that there is a very simple proof of this fact using basic binomial expansion: $3^{2n}+7=9^n+7=(1+8)^n+7$ and after expansion all your terms are divisible by $8$.
$endgroup$
– AlephNull
Jan 9 at 19:03










4 Answers
4






active

oldest

votes


















3












$begingroup$

No, it is not correct. It sholud be done something like this:
$$3^{2k}= 8A-7$$ sobegin{eqnarray} 3^{2k+2}+7 &=& 9cdot 3^{2k}+7\ &=& 9cdot (8A-7)+7 \ &=& 72A-56\ &=& 8(9A-7)end{eqnarray}






share|cite|improve this answer









$endgroup$





















    1












    $begingroup$

    An option:



    Step $n+1$:



    $3^{2n+2}+7 =9 cdot 3^{2n} +7=$



    $(8+1)cdot 3^{2n} +7=$



    $(3^{2n}+7) +8;$



    The first term is divisible by $8$ by hypothesis, so is the second term.






    share|cite|improve this answer









    $endgroup$





















      0












      $begingroup$

      Posting this community wiki answer as a protest - instructors should not ask for proofs by induction when there are much more straightforward ones like
      $$
      3^{2n} + 7 = 9^n + 7 equiv 1^n + 7 equiv 0 pmod{8} .
      $$



      Save induction for questions where it's really important.






      share|cite|improve this answer











      $endgroup$





















        0












        $begingroup$

        You've got the right idea. Here's how to view the inductive step intuitively as multiplication



        $$begin{align}
        3^{large 2k} &= color{#c00}{-7} + 8aqquad {rm i.e.} P(k)\
        times 3^{large 2} &= color{#c00} 1 + 8phantom{I_{I_{I_I}}}\
        hline
        Rightarrow 3^{large 2(k+1)} &= {-7} + 8(cdots) {rm i.e.} P(k!+!1)
        end{align}qquad $$



        Renark $ $ Note $, -7! +! 8a = 1! +! 8(a!-!1) $ so viewed this way, instead of $, color{#c00}{-7 times 1},$ we get $,1times 1,,$ so the above boils down to $, (1+8j)(1+8k) = 1+8n,,$ i.e. $bmod 8!: 1^2equiv 1, $ so the result boils down to $,9equiv 1,Rightarrow, 9^nequiv 1^nequiv 1,$ by the Congruence Power Rule.






        share|cite|improve this answer











        $endgroup$














          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067826%2fprove-that-32n-7-is-divisible-by-8%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          4 Answers
          4






          active

          oldest

          votes








          4 Answers
          4






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          3












          $begingroup$

          No, it is not correct. It sholud be done something like this:
          $$3^{2k}= 8A-7$$ sobegin{eqnarray} 3^{2k+2}+7 &=& 9cdot 3^{2k}+7\ &=& 9cdot (8A-7)+7 \ &=& 72A-56\ &=& 8(9A-7)end{eqnarray}






          share|cite|improve this answer









          $endgroup$


















            3












            $begingroup$

            No, it is not correct. It sholud be done something like this:
            $$3^{2k}= 8A-7$$ sobegin{eqnarray} 3^{2k+2}+7 &=& 9cdot 3^{2k}+7\ &=& 9cdot (8A-7)+7 \ &=& 72A-56\ &=& 8(9A-7)end{eqnarray}






            share|cite|improve this answer









            $endgroup$
















              3












              3








              3





              $begingroup$

              No, it is not correct. It sholud be done something like this:
              $$3^{2k}= 8A-7$$ sobegin{eqnarray} 3^{2k+2}+7 &=& 9cdot 3^{2k}+7\ &=& 9cdot (8A-7)+7 \ &=& 72A-56\ &=& 8(9A-7)end{eqnarray}






              share|cite|improve this answer









              $endgroup$



              No, it is not correct. It sholud be done something like this:
              $$3^{2k}= 8A-7$$ sobegin{eqnarray} 3^{2k+2}+7 &=& 9cdot 3^{2k}+7\ &=& 9cdot (8A-7)+7 \ &=& 72A-56\ &=& 8(9A-7)end{eqnarray}







              share|cite|improve this answer












              share|cite|improve this answer



              share|cite|improve this answer










              answered Jan 9 at 18:57









              Maria MazurMaria Mazur

              49.7k1361124




              49.7k1361124























                  1












                  $begingroup$

                  An option:



                  Step $n+1$:



                  $3^{2n+2}+7 =9 cdot 3^{2n} +7=$



                  $(8+1)cdot 3^{2n} +7=$



                  $(3^{2n}+7) +8;$



                  The first term is divisible by $8$ by hypothesis, so is the second term.






                  share|cite|improve this answer









                  $endgroup$


















                    1












                    $begingroup$

                    An option:



                    Step $n+1$:



                    $3^{2n+2}+7 =9 cdot 3^{2n} +7=$



                    $(8+1)cdot 3^{2n} +7=$



                    $(3^{2n}+7) +8;$



                    The first term is divisible by $8$ by hypothesis, so is the second term.






                    share|cite|improve this answer









                    $endgroup$
















                      1












                      1








                      1





                      $begingroup$

                      An option:



                      Step $n+1$:



                      $3^{2n+2}+7 =9 cdot 3^{2n} +7=$



                      $(8+1)cdot 3^{2n} +7=$



                      $(3^{2n}+7) +8;$



                      The first term is divisible by $8$ by hypothesis, so is the second term.






                      share|cite|improve this answer









                      $endgroup$



                      An option:



                      Step $n+1$:



                      $3^{2n+2}+7 =9 cdot 3^{2n} +7=$



                      $(8+1)cdot 3^{2n} +7=$



                      $(3^{2n}+7) +8;$



                      The first term is divisible by $8$ by hypothesis, so is the second term.







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Jan 9 at 19:08









                      Peter SzilasPeter Szilas

                      11.7k2822




                      11.7k2822























                          0












                          $begingroup$

                          Posting this community wiki answer as a protest - instructors should not ask for proofs by induction when there are much more straightforward ones like
                          $$
                          3^{2n} + 7 = 9^n + 7 equiv 1^n + 7 equiv 0 pmod{8} .
                          $$



                          Save induction for questions where it's really important.






                          share|cite|improve this answer











                          $endgroup$


















                            0












                            $begingroup$

                            Posting this community wiki answer as a protest - instructors should not ask for proofs by induction when there are much more straightforward ones like
                            $$
                            3^{2n} + 7 = 9^n + 7 equiv 1^n + 7 equiv 0 pmod{8} .
                            $$



                            Save induction for questions where it's really important.






                            share|cite|improve this answer











                            $endgroup$
















                              0












                              0








                              0





                              $begingroup$

                              Posting this community wiki answer as a protest - instructors should not ask for proofs by induction when there are much more straightforward ones like
                              $$
                              3^{2n} + 7 = 9^n + 7 equiv 1^n + 7 equiv 0 pmod{8} .
                              $$



                              Save induction for questions where it's really important.






                              share|cite|improve this answer











                              $endgroup$



                              Posting this community wiki answer as a protest - instructors should not ask for proofs by induction when there are much more straightforward ones like
                              $$
                              3^{2n} + 7 = 9^n + 7 equiv 1^n + 7 equiv 0 pmod{8} .
                              $$



                              Save induction for questions where it's really important.







                              share|cite|improve this answer














                              share|cite|improve this answer



                              share|cite|improve this answer








                              answered Jan 9 at 19:12


























                              community wiki





                              Ethan Bolker
























                                  0












                                  $begingroup$

                                  You've got the right idea. Here's how to view the inductive step intuitively as multiplication



                                  $$begin{align}
                                  3^{large 2k} &= color{#c00}{-7} + 8aqquad {rm i.e.} P(k)\
                                  times 3^{large 2} &= color{#c00} 1 + 8phantom{I_{I_{I_I}}}\
                                  hline
                                  Rightarrow 3^{large 2(k+1)} &= {-7} + 8(cdots) {rm i.e.} P(k!+!1)
                                  end{align}qquad $$



                                  Renark $ $ Note $, -7! +! 8a = 1! +! 8(a!-!1) $ so viewed this way, instead of $, color{#c00}{-7 times 1},$ we get $,1times 1,,$ so the above boils down to $, (1+8j)(1+8k) = 1+8n,,$ i.e. $bmod 8!: 1^2equiv 1, $ so the result boils down to $,9equiv 1,Rightarrow, 9^nequiv 1^nequiv 1,$ by the Congruence Power Rule.






                                  share|cite|improve this answer











                                  $endgroup$


















                                    0












                                    $begingroup$

                                    You've got the right idea. Here's how to view the inductive step intuitively as multiplication



                                    $$begin{align}
                                    3^{large 2k} &= color{#c00}{-7} + 8aqquad {rm i.e.} P(k)\
                                    times 3^{large 2} &= color{#c00} 1 + 8phantom{I_{I_{I_I}}}\
                                    hline
                                    Rightarrow 3^{large 2(k+1)} &= {-7} + 8(cdots) {rm i.e.} P(k!+!1)
                                    end{align}qquad $$



                                    Renark $ $ Note $, -7! +! 8a = 1! +! 8(a!-!1) $ so viewed this way, instead of $, color{#c00}{-7 times 1},$ we get $,1times 1,,$ so the above boils down to $, (1+8j)(1+8k) = 1+8n,,$ i.e. $bmod 8!: 1^2equiv 1, $ so the result boils down to $,9equiv 1,Rightarrow, 9^nequiv 1^nequiv 1,$ by the Congruence Power Rule.






                                    share|cite|improve this answer











                                    $endgroup$
















                                      0












                                      0








                                      0





                                      $begingroup$

                                      You've got the right idea. Here's how to view the inductive step intuitively as multiplication



                                      $$begin{align}
                                      3^{large 2k} &= color{#c00}{-7} + 8aqquad {rm i.e.} P(k)\
                                      times 3^{large 2} &= color{#c00} 1 + 8phantom{I_{I_{I_I}}}\
                                      hline
                                      Rightarrow 3^{large 2(k+1)} &= {-7} + 8(cdots) {rm i.e.} P(k!+!1)
                                      end{align}qquad $$



                                      Renark $ $ Note $, -7! +! 8a = 1! +! 8(a!-!1) $ so viewed this way, instead of $, color{#c00}{-7 times 1},$ we get $,1times 1,,$ so the above boils down to $, (1+8j)(1+8k) = 1+8n,,$ i.e. $bmod 8!: 1^2equiv 1, $ so the result boils down to $,9equiv 1,Rightarrow, 9^nequiv 1^nequiv 1,$ by the Congruence Power Rule.






                                      share|cite|improve this answer











                                      $endgroup$



                                      You've got the right idea. Here's how to view the inductive step intuitively as multiplication



                                      $$begin{align}
                                      3^{large 2k} &= color{#c00}{-7} + 8aqquad {rm i.e.} P(k)\
                                      times 3^{large 2} &= color{#c00} 1 + 8phantom{I_{I_{I_I}}}\
                                      hline
                                      Rightarrow 3^{large 2(k+1)} &= {-7} + 8(cdots) {rm i.e.} P(k!+!1)
                                      end{align}qquad $$



                                      Renark $ $ Note $, -7! +! 8a = 1! +! 8(a!-!1) $ so viewed this way, instead of $, color{#c00}{-7 times 1},$ we get $,1times 1,,$ so the above boils down to $, (1+8j)(1+8k) = 1+8n,,$ i.e. $bmod 8!: 1^2equiv 1, $ so the result boils down to $,9equiv 1,Rightarrow, 9^nequiv 1^nequiv 1,$ by the Congruence Power Rule.







                                      share|cite|improve this answer














                                      share|cite|improve this answer



                                      share|cite|improve this answer








                                      edited Jan 9 at 19:21

























                                      answered Jan 9 at 19:05









                                      Bill DubuqueBill Dubuque

                                      213k29196654




                                      213k29196654






























                                          draft saved

                                          draft discarded




















































                                          Thanks for contributing an answer to Mathematics Stack Exchange!


                                          • Please be sure to answer the question. Provide details and share your research!

                                          But avoid



                                          • Asking for help, clarification, or responding to other answers.

                                          • Making statements based on opinion; back them up with references or personal experience.


                                          Use MathJax to format equations. MathJax reference.


                                          To learn more, see our tips on writing great answers.




                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function () {
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067826%2fprove-that-32n-7-is-divisible-by-8%23new-answer', 'question_page');
                                          }
                                          );

                                          Post as a guest















                                          Required, but never shown





















































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown

































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown







                                          Popular posts from this blog

                                          Bressuire

                                          Cabo Verde

                                          Gyllenstierna