# Thread: help with proof for number theory, possibly using induction?

1. ## help with proof for number theory, possibly using induction?

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

2. ## Re: 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 $n>2:$ assume $3^{2^{n-3}}\equiv 2^{n-1}+1\pmod{2^n}\iff 3^{2^{n-3}}= 2^{n-1}+1+2^{n}k$

$\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)$

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

2) A rather nice way is to consider $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)$
$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 $3^{2^k}+1$ is 2

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