8
$\begingroup$

Prove $ \large \left\lfloor \frac{1}2 \left( 2+\sqrt3 \right) ^{2002} \right\rfloor \equiv -1 \pmod7 $

So far my intuion only tells me that this has something to do with $(2+\sqrt3)(2-\sqrt3)=1$, but I don't even know where to begin.

I'm looking for elegant solution.

3 Answers 3

10

Hint: Consider $u_n = \alpha^n + \beta^n$ where $\alpha =2+\sqrt3$ and $\beta=2-\sqrt3$. Note that $0 < \beta <1$ and so $u_n = \lfloor \alpha^n \rfloor $. Find a recursion for $u_n$ and consider it mod 7.

Disclaimer: I haven't tried it myself...

Edit. Here is the solution I had in mind:

$u_n$ is an integer because the $\sqrt3$ terms cancel. In fact, $u_n$ is an even integer because the other terms repeat (just like $z+\bar z = 2x$ for complex numbers).

$v_n := u_n/2 = 1+\lfloor \alpha^n/2 \rfloor$ because $0 < \beta <1$.

$\alpha^2=4\alpha -1$ implies that $u_{n+1}=4u_{n+1}-u_n$ and the same for $v_n$, which is: $1, 2, 7, 26, 97, 362, 1351, \dots$. This sequence must be periodic mod 7, and so it is: $1,2,0,5,6,5,0,2,1,2,\dots$, periodic of period 8.

Finally, $2002 \equiv 2 \bmod 8$ and so $v_{2002} \equiv v_2 = 7 \equiv 0 \bmod 7$.

  • 1
    I enjoyed to struggle with the problem. Really lhf's hint shows the solution clearly. really great view. I added my solution way below for the people who wonder the solution steps .2012-03-11
5

Firstly, I would like to show $\left( 2+\sqrt3 \right) ^{2002} + \left( 2-\sqrt3 \right) ^{2002}=A$ is an even integer.

$\left( 2+\sqrt3 \right) ^{2002} + \left( 2-\sqrt3 \right) ^{2002}=(2 ^{2002}+2002.2^{2001}\sqrt3+\frac{2002.2001}{2}2^{2000}3+\frac{2002.2001.2000}{6}2^{1999}3\sqrt3+....) +(2 ^{2002}-2002.2^{2001}\sqrt3+\frac{2002.2001}{2}2^{2000}3-\frac{2002.2001.2000}{6}2^{1999}3\sqrt3+....)=2.(2 ^{2002}+\frac{2002.2001}{2}2^{2000}3+....)$

as shown above $\sqrt3$ terms will be zero after binom expansion, so A is an even integer.

$0<\left( 2-\sqrt3 \right) <1$ ,

$\frac{1}2 \left( 2+\sqrt3 \right) ^{2002} = \frac{A}2-\frac{1}2\left( 2-\sqrt3 \right) ^{2002}$

$A/2$ is an integer because A is an even integer and $0<\frac{1}2\left( 2-\sqrt3 \right) ^{2002}<1$ ,Thus

$ \lfloor \frac{1}2 \left( 2+\sqrt3 \right) ^{2002} \rfloor=\frac{A}2-1$

$ A \equiv y \pmod7 $ $ \left( 2+\sqrt3 \right) ^{2002} + \left( 2-\sqrt3 \right) ^{2002} \equiv y \pmod7 $

$ \left( (2+\sqrt3 \right)^2) ^{1001} + \left( (2-\sqrt3 \right)^2) ^{1001} \equiv y \pmod7 $

$ \left( (7+2\sqrt3 \right)) ^{1001} + \left( (7-2\sqrt3 \right)) ^{1001} \equiv y \pmod7 $

$ \left( (2\sqrt3 \right)) ^{1001} + \left( (-2\sqrt3 \right)) ^{1001} \equiv y \pmod7 $

$ \left( (2\sqrt3 \right)) ^{1001} - \left( (2\sqrt3 \right)) ^{1001} \equiv y \pmod7 $

$y=0$

and

$ A \equiv 0 \pmod7 $

$ \lfloor \frac{1}2 \left( 2+\sqrt3 \right) ^{2002} \rfloor=\frac{A}2-1$

$ \large \lfloor \frac{1}2 \left( 2+\sqrt3 \right) ^{2002} \rfloor= \frac{A}2-1 \equiv -1 \pmod7 $

  • 0
    Not the solution I had in mind but nice too.2012-03-11
2

$(2+\sqrt 3)^2=7+2\sqrt3$

Now, $(7+4\sqrt3)^{2m+1}+(7-4\sqrt3)^{2m+1}$ $=2\left(7^{2m+1}+\binom {2m+1}27^{2m-1}\cdot4^2\cdot3+\binom{2m+1}47^{2m-3}\cdot4^4\cdot3^2+\cdots+\binom{2m+1}{2m}7\cdot4^{2m}\cdot3^m\right)$ which is divisible by $2\cdot 7=14.$

Consequently, $\frac12(7+4\sqrt3)^{2m+1}+\frac12(7-4\sqrt3)^{2m+1}\equiv0\pmod 7$

Like Mathlover has observed, $0<\frac{7-4\sqrt3}2=\frac{7^2-(4\sqrt3)^2}{2(7+4\sqrt3)}<1\implies 0<\frac12(7-4\sqrt3)^{2m+1}<1$

Hence, $7k-1<\frac12(7+4\sqrt3)^{2m+1}<7k$ some integer $k.$