1

Question taken from the book by Andre Weil, titled Introductory number theory, chapter 5, question #V.3.

Prove by induction that, if $n$ is a positive integer, then $2^{2n+1}\equiv 9n^2-3n + 2\pmod{54}$.

Take base case, $n=1, 2^3\equiv 9-3+ 2\pmod{54}$ $\implies 8\equiv 8\pmod{54}$.

So, the base case should be a value that yields LHS $\geq 54$.

$n=3, 2^7\equiv 9.9-3.3+ 2\pmod{54}$ $ \implies 128\equiv 81-9+2\pmod{54}$ $\implies 128\equiv 74\pmod{54}$ $\implies 20\equiv 20\pmod{54}$.

Assume, it is true for $n=k$, get: $2^{2k+1}\equiv 9k^2-3k + 2\pmod{54}$.

Need show that it is true also for $n=k+1$.

$2^{2k+3}\equiv 9(k+1)^2-3(k+1) + 2\pmod{54}$

$\implies 2^{2k+1}.2^2\equiv 9(k)^2 +18k +9-3(k)-3 + 2\pmod{54}$

As LHS is proved, so need take the RHS, and show: $\implies 9(k)^2 +18k +9-3(k)-3 + 2\equiv 9(k)^2 -3(k)+ 2 \pmod{54}$

$\implies 9(k)^2 +18k -3k +8 \equiv 9(k)^2 -3(k)+ 2 \pmod{54}$

$\implies 18k +6 \equiv 0 \pmod{54}$

$\implies 3k +1 \equiv 0 \pmod{9}$

Why got such a wrong result?

Edit. As per the selected answer, get: $2^{2k+3} \equiv 9k^2 +18k +9-3k-3 + 2\pmod{54}$
But, $2^{2k+1} \equiv 9(k)^2 -3(k)+ 2 \pmod{54}$
So, $2^{2k+3} = 4.2^{2k+1}\equiv 4.(9(k)^2 -3(k)+ 2) \pmod{54}$
So, $9k^2 +15k +8\equiv 4.(9(k)^2 -3(k)+ 2) \pmod{54}$ $9k^2 +15k +8\equiv 36k^2 -12k+ 8 \pmod{54}$ $0\equiv 27k^2 -27k\pmod{54}$ $0\equiv 27k(k-1)\pmod{54}$ $0\equiv 54k'\pmod{54}$ $0\equiv 0\pmod{54}$

jiten
  • 4,524
  • @Sil the LHS (& RHS too, though is zero) is divided by $6$, but the modulus is not affected? I can show by the selected answer's approach that $\mod 54$ should be $\mod 9$, not $\mod 54$ after LHS is divided by $6$. $4(9k^2 -3k +2) - (9k^2 + 15k + 8 ) \equiv 0(\mod 54)\implies 27k^2 -27k\equiv 0 (\mod 54)\implies 27k(k-1) \equiv 0(\mod 54) \implies k(k-1) \equiv 0 (\mod 2)$. Had we not divided by $27$, it would be $k(k-1) \equiv 0 (\mod 54)$. Please correct me if wrong. – jiten Apr 21 '21 at 12:08
  • Yes it was a typo, you had all modulus $54$ except one which was $9$ that I missed, Siong already fixed that. I've just changed the horrible formatting from $\equiv 0(\mod 54)$ to $\equiv 0\pmod {54}$. – Sil Apr 22 '21 at 16:37

3 Answers3

1

Alternatively if induction is not mandatory, $$2^{2n+1}-2=2(4^n-1)$$

$$(1+3)^n-1\equiv\binom n13^1+\binom n23^2\pmod{27}\equiv\dfrac{9n^2-3n}2 $$

$$\implies2(4^n-1)\equiv9n^2-3n\pmod{54}$$

lab bhattacharjee
  • 274,582
1

Key Idea The trick is to eliminate the exponential $\,g_n = 2^{2n+1}\,$ in $\,f_n = g_n-9n^2+3n-2.\,$ Since $\,g_{n+1} = \color{#C00}4 g_n\,$ it will be eliminated in $\,f_{n+1}-\color{#c00}4f_n = 27n(n\!-\!1)$. But $\,54\mid 27n(n\!-\!1)\,$ by $\,2\mid n(n\!-\!1)$ so we conclude that $\,54\mid f_{n+1}\,$ if $\,54\mid f_{n},\,$ i.e. the induction step. $ $ QED

Bill Dubuque
  • 272,048
-1

Hint:

$$2^{2(n+1)+1} -(9(n+1)^2-3(n+1)+2)$$

$$\equiv36n^2-12n-8-(9n^2+18n+9-3n-3+2)$$

$$\equiv27n(n-1)$$

$$\equiv0\pmod{2\cdot27}$$

lab bhattacharjee
  • 274,582