Menu Close

Prove-that-3-3n-26n-1-is-divisible-by-676-where-n-Z-

Tinku Tara 0 Comments
Pin




Question Number 2545 by Rasheed Soomro last updated on 22/Nov/15
Prove that 3^(3n) −26n−1 is divisible by 676, where n∈Z^+
$$\mathcal{P}{rove}\:{that}\:\mathrm{3}^{\mathrm{3}{n}} −\mathrm{26}{n}−\mathrm{1}\:{is}\:{divisible}\:{by}\:\mathrm{676}, \\ $$$${where}\:{n}\in\mathbb{Z}^{+} \\ $$
Commented by Yozzi last updated on 22/Nov/15
Use induction.
$${Use}\:{induction}. \\ $$
Answered by Yozzi last updated on 22/Nov/15
Let P(n)=3^(3n) −26n−1=(27)^n −26n−1 P(1)=27−26−1=0=676×0 P(2)=27^2 −52−1=676=1×676 P(3)=27^3 −26×3−1=29×676 Let P(n) be the proposition that, ∀n∈Z^+ , P(n)=676m where P(n)=27^n −26n−1 and m∈Z^≥ . For n=1, P(1)=27−26−1=0=676×0 0∈Z^≥ ⇒m=0 ∴ P(n) is true for n=1. Assume P(n) is true for n=k, i.e P(k)=676m m∈Z^≥ . For n=k+1, observe the difference Δ=P(k+1)−P(k). P(k+1)=27^(k+1) −26(k+1)−1 Δ=27×27^k −26k−26−1−27^k +26k+1 Δ=26×27^k −26 Δ=26(27^k −1) ⇒P(k+1)=P(k)+26(27^k −1) P(k+1)=676m+26(27^k −1) Now, 27^k −1=(27−1)(Σ_(r=0) ^(k−1) 27^r )=26(Σ_(r=0) ^(k−1) 27^r ) ∴P(k+1)=676m+676Σ_(r=0) ^(k−1) 27^r P(k+1)=676(m+Σ_(r=0) ^(k−1) 27^r )=676q where q∈Z^+ since {m+Σ_(r=0) ^(k−1) 27^r }∈Z^+ . ⇒ P(k+1) is true if P(k) is true. Since P(1) is true then, by P.M.I, P(n) is true ∀n∈Z^+ .
$${Let}\:{P}\left({n}\right)=\mathrm{3}^{\mathrm{3}{n}} −\mathrm{26}{n}−\mathrm{1}=\left(\mathrm{27}\right)^{{n}} −\mathrm{26}{n}−\mathrm{1} \\ $$$${P}\left(\mathrm{1}\right)=\mathrm{27}−\mathrm{26}−\mathrm{1}=\mathrm{0}=\mathrm{676}×\mathrm{0} \\ $$$${P}\left(\mathrm{2}\right)=\mathrm{27}^{\mathrm{2}} −\mathrm{52}−\mathrm{1}=\mathrm{676}=\mathrm{1}×\mathrm{676} \\ $$$${P}\left(\mathrm{3}\right)=\mathrm{27}^{\mathrm{3}} −\mathrm{26}×\mathrm{3}−\mathrm{1}=\mathrm{29}×\mathrm{676} \\ $$$$ \\ $$$${Let}\:{P}\left({n}\right)\:{be}\:{the}\:{proposition}\:{that},\:\forall{n}\in\mathbb{Z}^{+} , \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:{P}\left({n}\right)=\mathrm{676}{m} \\ $$$${where}\:\:{P}\left({n}\right)=\mathrm{27}^{{n}} −\mathrm{26}{n}−\mathrm{1}\:{and}\:{m}\in\mathbb{Z}^{\geqslant} . \\ $$$${For}\:{n}=\mathrm{1},\:{P}\left(\mathrm{1}\right)=\mathrm{27}−\mathrm{26}−\mathrm{1}=\mathrm{0}=\mathrm{676}×\mathrm{0} \\ $$$$\mathrm{0}\in\mathbb{Z}^{\geqslant} \Rightarrow{m}=\mathrm{0}\:\therefore\:{P}\left({n}\right)\:{is}\:{true}\:{for}\:{n}=\mathrm{1}. \\ $$$$ \\ $$$${Assume}\:{P}\left({n}\right)\:{is}\:{true}\:{for}\:{n}={k},\:{i}.{e} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:{P}\left({k}\right)=\mathrm{676}{m} \\ $$$${m}\in\mathbb{Z}^{\geqslant} . \\ $$$${For}\:{n}={k}+\mathrm{1},\:{observe}\:{the}\:{difference} \\ $$$$\Delta={P}\left({k}+\mathrm{1}\right)−{P}\left({k}\right).\: \\ $$$${P}\left({k}+\mathrm{1}\right)=\mathrm{27}^{{k}+\mathrm{1}} −\mathrm{26}\left({k}+\mathrm{1}\right)−\mathrm{1} \\ $$$$\Delta=\mathrm{27}×\mathrm{27}^{{k}} −\mathrm{26}{k}−\mathrm{26}−\mathrm{1}−\mathrm{27}^{{k}} +\mathrm{26}{k}+\mathrm{1} \\ $$$$\Delta=\mathrm{26}×\mathrm{27}^{{k}} −\mathrm{26} \\ $$$$\Delta=\mathrm{26}\left(\mathrm{27}^{{k}} −\mathrm{1}\right) \\ $$$$\Rightarrow{P}\left({k}+\mathrm{1}\right)={P}\left({k}\right)+\mathrm{26}\left(\mathrm{27}^{{k}} −\mathrm{1}\right) \\ $$$${P}\left({k}+\mathrm{1}\right)=\mathrm{676}{m}+\mathrm{26}\left(\mathrm{27}^{{k}} −\mathrm{1}\right) \\ $$$${Now},\:\mathrm{27}^{{k}} −\mathrm{1}=\left(\mathrm{27}−\mathrm{1}\right)\left(\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\mathrm{27}^{{r}} \right)=\mathrm{26}\left(\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\mathrm{27}^{{r}} \right) \\ $$$$\therefore{P}\left({k}+\mathrm{1}\right)=\mathrm{676}{m}+\mathrm{676}\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\mathrm{27}^{{r}} \\ $$$${P}\left({k}+\mathrm{1}\right)=\mathrm{676}\left({m}+\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\mathrm{27}^{{r}} \right)=\mathrm{676}{q} \\ $$$${where}\:{q}\in\mathbb{Z}^{+} \:{since}\:\left\{{m}+\underset{{r}=\mathrm{0}} {\overset{{k}−\mathrm{1}} {\sum}}\mathrm{27}^{{r}} \right\}\in\mathbb{Z}^{+} . \\ $$$$\Rightarrow\:{P}\left({k}+\mathrm{1}\right)\:{is}\:{true}\:{if}\:{P}\left({k}\right)\:{is}\:{true}. \\ $$$${Since}\:{P}\left(\mathrm{1}\right)\:{is}\:{true}\:{then},\:{by}\:{P}.{M}.{I}, \\ $$$${P}\left({n}\right)\:{is}\:{true}\:\forall{n}\in\mathbb{Z}^{+} . \\ $$$$ \\ $$$$ \\ $$$$ \\ $$
Commented by Rasheed Soomro last updated on 22/Nov/15
NICE^(Very) !
$$\overset{{Very}} {\boldsymbol{{NICE}}}\:! \\ $$
Answered by Rasheed Soomro last updated on 22/Nov/15
AN EASY Approach p(n): 3^(3n) −26n−1 is divisible by 676 Case−1_(−) :For n=1 3^(3n) −26n−1=3^3 −26−1=0 and 676∣0 Hence p(n) is true for n=1 Case−2 : Assume that for n=k , p(n) is true I−e 676 ∣ (3^(3k) −26k−1) Now for n=k+1, we have 3^(3(k+1)) −26(k+1)−1 =3^(3k+3) −26k−26−1 =27.3^(3k) −26k−27 =27.3^(3k) −27(26k)−27+26(26k) =27(3^(3k) −26k−1)+676k ∵ 676 ∣ (3^(3k) −26k−1) [By hypothesis]] and 676 ∣ 676k ∴ 676 ∣ 27(3^(3k) −26k−1)+676k ∴ p(n) is true for n=k+1,if it is true for n=k QED
$$\mathbb{AN}\:\:\:\mathcal{EASY}\:\boldsymbol{\mathrm{Approach}} \\ $$$$\boldsymbol{{p}}\left(\boldsymbol{{n}}\right):\:\:\:\mathrm{3}^{\mathrm{3}\boldsymbol{{n}}} −\mathrm{26}\boldsymbol{{n}}−\mathrm{1}\:\boldsymbol{{is}}\:\boldsymbol{{divisible}}\:\boldsymbol{{by}}\:\mathrm{676} \\ $$$$\underset{−} {\boldsymbol{{Case}}−\mathrm{1}}\::\boldsymbol{{F}}{or}\:\boldsymbol{{n}}=\mathrm{1} \\ $$$$\:\mathrm{3}^{\mathrm{3}\boldsymbol{{n}}} −\mathrm{26}\boldsymbol{{n}}−\mathrm{1}=\mathrm{3}^{\mathrm{3}} −\mathrm{26}−\mathrm{1}=\mathrm{0}\:\boldsymbol{{and}}\:\:\:\:\:\mathrm{676}\mid\mathrm{0} \\ $$$$\boldsymbol{{Hence}}\:\boldsymbol{{p}}\left(\boldsymbol{{n}}\right)\:\boldsymbol{{is}}\:\boldsymbol{{true}}\:\boldsymbol{{for}}\:\boldsymbol{{n}}=\mathrm{1} \\ $$$$\boldsymbol{{Case}}−\mathrm{2}\::\:\boldsymbol{{Assume}}\:\boldsymbol{{that}}\:\boldsymbol{{for}}\:\boldsymbol{{n}}=\boldsymbol{{k}}\:,\:\boldsymbol{{p}}\left(\boldsymbol{{n}}\right)\:\boldsymbol{{is}}\:\boldsymbol{{true}} \\ $$$$\boldsymbol{{I}}−\boldsymbol{{e}}\:\:\:\mathrm{676}\:\mid\:\left(\mathrm{3}^{\mathrm{3}\boldsymbol{{k}}} −\mathrm{26}\boldsymbol{{k}}−\mathrm{1}\right) \\ $$$$\boldsymbol{{Now}}\:\boldsymbol{{for}}\:\boldsymbol{{n}}=\boldsymbol{{k}}+\mathrm{1},\:\boldsymbol{{we}}\:\boldsymbol{{have}} \\ $$$$\:\:\:\:\:\:\:\:\:\mathrm{3}^{\mathrm{3}\left(\boldsymbol{{k}}+\mathrm{1}\right)} −\mathrm{26}\left(\boldsymbol{{k}}+\mathrm{1}\right)−\mathrm{1} \\ $$$$\:\:\:\:\:\:\:=\mathrm{3}^{\mathrm{3}\boldsymbol{{k}}+\mathrm{3}} −\mathrm{26}\boldsymbol{{k}}−\mathrm{26}−\mathrm{1} \\ $$$$\:\:\:\:\:\:\:=\mathrm{27}.\mathrm{3}^{\mathrm{3}\boldsymbol{{k}}} −\mathrm{26}\boldsymbol{{k}}−\mathrm{27} \\ $$$$\:\:\:\:\:\:\:=\mathrm{27}.\mathrm{3}^{\mathrm{3}\boldsymbol{{k}}} −\mathrm{27}\left(\mathrm{26}\boldsymbol{{k}}\right)−\mathrm{27}+\mathrm{26}\left(\mathrm{26}\boldsymbol{{k}}\right) \\ $$$$\:\:\:\:\:\:\:=\mathrm{27}\left(\mathrm{3}^{\mathrm{3}\boldsymbol{{k}}} −\mathrm{26}\boldsymbol{{k}}−\mathrm{1}\right)+\mathrm{676}\boldsymbol{{k}} \\ $$$$\left.\:\:\:\:\:\because\:\:\mathrm{676}\:\mid\:\left(\mathrm{3}^{\mathrm{3}\boldsymbol{{k}}} −\mathrm{26}\boldsymbol{{k}}−\mathrm{1}\right)\:\left[\boldsymbol{{By}}\:\boldsymbol{{hypothesis}}\right]\right] \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{{and}}\:\mathrm{676}\:\mid\:\mathrm{676}\boldsymbol{{k}} \\ $$$$\:\:\:\:\:\:\therefore\:\mathrm{676}\:\mid\:\mathrm{27}\left(\mathrm{3}^{\mathrm{3}\boldsymbol{{k}}} −\mathrm{26}\boldsymbol{{k}}−\mathrm{1}\right)+\mathrm{676}\boldsymbol{{k}} \\ $$$$\therefore\:\:\boldsymbol{{p}}\left(\boldsymbol{{n}}\right)\:\boldsymbol{{is}}\:\boldsymbol{{true}}\:\boldsymbol{{for}}\:\boldsymbol{{n}}=\boldsymbol{{k}}+\mathrm{1},\boldsymbol{{if}}\:\boldsymbol{{it}}\:\boldsymbol{{is}}\:\boldsymbol{{true}}\:\boldsymbol{{for}}\:\boldsymbol{{n}}=\boldsymbol{{k}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{{QED}} \\ $$
Commented by Yozzi last updated on 22/Nov/15
Nicely □
$${Nicely}\:\:\Box \\ $$
Commented by Rasheed Soomro last updated on 23/Nov/15
□ THANKS! Actually I saw this problem and its solution in a book and wanted to share with friends on this platform. Therefore in order to get oppertunity I posted the question. I like your answer because its your own whereas my answer is bookish and not my own.Anyway it is such that it be shared.
$$\Box\:\mathcal{THANK}\mathbb{S}! \\ $$$${Actually}\:{I}\:{saw}\:{this}\:{problem}\:{and}\:{its}\:{solution}\:{in}\:{a}\:{book} \\ $$$${and}\:{wanted}\:{to}\:{share}\:{with}\:{friends}\:{on}\:{this}\:{platform}. \\ $$$${Therefore}\:{in}\:{order}\:{to}\:{get}\:{oppertunity}\:{I}\:{posted}\:{the}\:{question}. \\ $$$$\:\:\:\:\:\mathcal{I}\:{like}\:{your}\:{answer}\:{because}\:{its}\:{your}\:{own}\:{whereas}\:{my} \\ $$$${answer}\:{is}\:{bookish}\:{and}\:{not}\:{my}\:{own}.{Anyway}\:{it}\:{is}\:{such}\:{that} \\ $$$${it}\:{be}\:{shared}. \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *