2^n = k(mod 7)

[Rock'n'roller]

If [tex]n \equiv x(mod 3) (x = 0, 1, 2)[/tex] and [tex]f(x) = \frac{1}{2}x^2 + \frac{1}{2}x + 1[/tex] prove that

[tex]2^n \equiv f(x)(mod 7)[/tex]

[broniran]

Since [tex]2\in 3 mod 7[/tex], we can obtain [tex]2^{3k+e}\equiv 2^e(mod7)[/tex]. Now we have 3 cases:
1 case: [tex]n=3k \Rightarrow x=0[/tex].
[tex]2^{3k}\equiv1(mod7)[/tex] and [tex]f(x)=\frac{1}{2}.0+\frac{1}{2}.0+1=1[/tex]- true
2 case: [tex]n=3k+1\Rightarrow x=1[/tex].
[tex]2^{3k+1}\equiv2(mod7)[/tex] and [tex]f(x)=\frac{1}{2}+\frac{1}{2}+1=2[/tex]- true
3 case: [tex]n=3k+2\Rightarrow x=2[/tex]
[tex]2^{3k+2}\equiv2^2\equiv 4(mod7)[/tex] and [tex]f(x)=\frac{1}{2}.4+\frac{1}{2}.2+1=4[/tex]- true