$2.(4^{2n})-4^n≡1$ اثبات کنید

Question

اثبات کنید که $$ \forall n \in N , 2(4^{2n}) - 4^{n} \equiv 1 \pmod 9$$

Comments

در خود سوال نوشته با استقرا اثبات کنید. آیا راه دیگه ای هم به جز استقرا هست؟

Answer 1

اول به ازای $n=1$ ثابت میکنیم $9 \mid 2*4^{2n}-4^n-1$

فرض میکنیم $9 \mid 2*4^{2k}-4^k-1$ ثابت میکنیم حکم به ازای k+1 نیز برقرار است :

$$2*4^{2k+2}-4^{k+1}-1= 16*2*4^{2k}-4*4^k-1$$ $$= (2*4^{2k}-4^k-1)+15*2*4^{2k}-3*4^k$$ $$= (2*4^{2k}-4^k-1)+3(10*4^{2k}-4^k)$$

چون $(10*4^{2k}-4^k)$ همیشه بر 3 بخش پذیر است پس عبارت بالا همیشه بر 9 بخش پذیر است پس حکم به ازای k+1 نیز برقرار است .

Answer 2

روش غیر استقرایی:

$n=1 \Rightarrow 4^1 \equiv 4 \pmod 9$

$n=2 \Rightarrow 4^2 \equiv 7 \pmod 9$

$n=3 \Rightarrow 4^3 \equiv 1 \pmod 9$

پس می توانیم بگوییم:

$4^3 \equiv 1 \pmod 9 \Rightarrow (4^3)^k \equiv 1 \pmod 9 \Rightarrow 4^{3k } \equiv 1 \pmod 9$

با ضرب دو همنهشتی اول به عبارتی که به دست اوردیم داریم:

$4^{3k+1} \equiv 4 \pmod 9$

$4^{3k+2} \equiv 7 \pmod 9$

پس این گونه اعداد بر اساس باقیمانده بر ۹ به سه قسمت تقسیم می شوند.

حالت۱:(از ضرب همنهشتی ها استفاده کنید.

$n=3k \Rightarrow 2(4^{2n}) - 4^{n} \equiv 1 (mod 9)$

برای دو حالت دیگر نیز این کار را انجام دهید تا به جواب مطلوب برسید.