If k > 2, and n = 2^{k-3}, show that 3^{n}is not congruent to 1 (mod 2^{k}).

Printable View

- Dec 7th 2012, 06:09 PMalexer1278help with proof for number theory, possibly using induction?
If k > 2, and n = 2

^{k-3}, show that 3^{n}is not congruent to 1 (mod 2^{k}). - Jan 1st 2013, 06:59 AMLordoftheFliesRe: help with proof for number theory, possibly using induction?
Old thread but if you're still interested: there are several ways to do this.

**1)**By induction for $\displaystyle n>2:$ assume $\displaystyle 3^{2^{n-3}}\equiv 2^{n-1}+1\pmod{2^n}\iff 3^{2^{n-3}}= 2^{n-1}+1+2^{n}k$

$\displaystyle \Rightarrow\;\; 3^{2^{n-2}}= (2^{n-1}+1+2^{n}k)^2=2^n+1+2^{n+1}(2^{n-3}+2^{n-1}k+2^{n-1}k^2)$

$\displaystyle \iff 3^{2^{n-2}}\equiv 2^{n}+1\pmod{2^{n+1}}$ etc.

**2)**A rather nice way is to consider $\displaystyle 3^{2^{n-3}}-1=(3^2-1)(3^2+1)(3^4+1)\cdots (3^{2^{n-4}}+1)=2^3 \cdot\displaystyle\prod_1^{n-4} (3^{2^k}+1)$

$\displaystyle 3^2\equiv 1\pmod{4}\Rightarrow 3^{2^k}\equiv 1\pmod{4}\Leftrightarrow 3^{2^k}+1\equiv 2\pmod{4}$ therefore the highest power of 2 dividing $\displaystyle 3^{2^k}+1$ is 2

It follows that $\displaystyle 2^{n-1}$ is the highest power of 2 dividing $\displaystyle \displaystyle 2^3\cdot \prod_1^{n-4} (3^{2^k}+1)$, so $\displaystyle 2^n$ cannot divide $\displaystyle 3^{2^{n-3}}-1$