Floor of the power of a radical

Question

Good morning Stack Exchange,

I have encountered a problem that I have no idea how to solve. This is what the question asks:

Determine how many integers $2000 \leq n \leq 2010$ are such that $7$ divides $\lfloor\frac{\sqrt{2}}{4}(1+\sqrt{2})^n\rfloor$.

I truely have no idea where to even start. I have looked online for a bit, and I have found similar problems which are solved by reducing the problem to one about linear recurrences. There is also a "trick" I have tried to apply which exploits the fact that $\sqrt{2}-1<1$, but it has all been in vain. The factor of $\frac{\sqrt{2}}{4}$ thwarts all of my attempts. The only "answer" I can come up with is that the congruences modulo $7$ are probably in a cycle of period $7$, so the numbers satisfying the answer are about $1$ in $7$ i.e. $2$. Can anybody help me? A solution would be great, but even hints will be gladly received.

Answer 1

You mentioned the right applicable tools.

• $a_n:=(1+\sqrt2)^n+(1-\sqrt 2)^n$ is always an integer and follows a nice recursion
• The disturbing $(1-\sqrt 2)^n$ is always sufficiently small and you know exactly when it is positive and when negative
• Note that $\frac{\sqrt 2}4a_n\approx \frac{a_{n+1}-a_n}4 $ with manageable error (cf. above).

Answer 2

To Hagen von Eitzen's answer, I would add the following consideration. Note that there exists a ring homomorphism $\Bbb Z[\sqrt 2]\to\Bbb Z/7\Bbb Z$ such that $\sqrt 2\mapsto 4$. Consequently: \begin{align} a_n &=(1+\sqrt 2)^n+(1-\sqrt 2)^n\\ &\equiv 5^n+4^n\pmod 7 \end{align} for every $n\in\Bbb N$. Since for $n\geq 2000$ we have $$\left\lfloor\frac{\sqrt{2}}{4}(1+\sqrt{2})^n\right\rfloor= \begin{cases} \frac{a_{n+1}-a_n}4&n\equiv 0\pmod 2\\ \frac{a_{n+1}-a_n}4-1&n\equiv 1\pmod 2 \end{cases}$$ the required values of $n$ are $\{2003,2004,2005,2009,2010\}$.

---

The same values of $n$ can be obtained by using a recurrence relation. For if $(1+\sqrt 2)^n=u_n+\sqrt 2v_n$ with $u_n,v_n\in\Bbb Z$, then $u_0=1$, $v_0=0$ and \begin{align} u_{n+1}&=u_n+2v_n\\ v_{n+1}&=u_n+v_n \end{align} Consequently, $\frac 14(a_{n+1}-a_n)=v_n$ and $v_n\bmod 7$ is a periodic sequence of period $6$ with values: \begin{array}{c|cc} n&u_n\bmod 7&v_n\bmod 7\\ \hline 0&1&0\\ 1&1&1\\ 2&3&2\\ 3&0&5\\ 4&3&5\\ 5&6&1 \end{array} By periodicity, we get: \begin{array}{c|ccc} n&u_n\bmod 7&v_n\bmod 7&\lfloor\frac{\sqrt{2}}{4}(1+\sqrt{2})^n\rfloor\bmod 7\\ \hline 2000&3&2&2\\ 2001&0&5&4\\ 2002&3&5&5\\ 2003&6&1&0\\ 2004&1&0&0\\ 2005&1&1&0\\ 2006&3&2&2\\ 2007&0&5&4\\ 2008&3&5&5\\ 2009&6&1&0\\ 2010&1&0&0 \end{array}