In Lucas Sequence, should numerator always be even when calculating $v_{2k}$? In the Lucas Probable prime test one of the steps is to use the formula
$V_{2k}=v_k^2-2Q^k=(v^2_k+DU_k^2)/2$ 
I have found sometimes the numerator $V^2_k+DU_k^2$ is odd. I was wondering if that makes I've made an earlier mistake or if this is to be expected? There are other related formulas, $U_{2k+1}=({PU_{2k}+V_{2k}})/2$ and $V_{2k+1}=({DU_{2k}+PV_{2k}})/2$ where the article contains specific instructions on what to do if the numerator is odd. This makes me think that $v^2_k+DU_k^2$ shouldn't be odd. Also someone pointed out that it definitely should be an integer because $(v^2_k+DU_k^2)=V_k^2-2Q^k$.
If it is in fact correct that the numerator can be odd, what is the correct thing to do when dividing by 2? I've seen


*

*divide by 2 and use the floor function i.e. always round down (example)

*if odd, add on n because all calculations are done module n (described in linked wiki article)

*multiply numerator by n+1 regardless if odd or even


Are all these techniques equivalent? 
An example of when this happens is $n=7$ and $D=5$ then $v_4=7$ which is congruent to 0 then $v_8=\frac{0+5 \cdot 3^2}{2}=\frac{45}{2}$. I think it normally happens to last v term for prime numbers.
In general when dealing in modular arithmetic, is it assumed everything is an integer? 
 A: Firstly it is even before you mod it $7+5\cdot 3^2= 52=7(7)+3$.  As the later is really what modular arithmetic talks with, it's not surprising at all to get an odd resulting numerator. You can then rewrite it as $7(8)-4=52$ , and then dividing by 2, we get: $$7(4)-2=26$$ Which then gives use a remainder in mod of $-2\equiv(7-2)\equiv 5\pmod 7$ 
A: If you're working modulo an odd $n$, it's not meaningful to say that a value is "even" or "odd", since an even number can be converted to an odd number modulo $n$. You also don't need to: you can always divide by $2$.
Of the solutions you suggest, the first one definitely doesn't work: when dividing an odd number by $2$, we shouldn't take the floor. An easy way to see that this is wrong is that it's not consistent when we take a different numerator in the same equivalence class modulo $n$. For example, $3 \equiv 10\pmod{7}$, but if we divide by $2$ and round down, we get $1$ and $5$, and $1 \not\equiv 5 \pmod{7}$.
It's definitely valid to divide an odd $k$ by $2$ by taking $\frac{k+n}{2}$; since $k \equiv k+n \pmod{n}$, this is just taking a different representation of the same number. This explains your second method.
For the third method: Since $2 \cdot \frac{n+1}{2} \equiv n+1 \equiv 1 \pmod n$, $\frac{n+1}{2}$ (an integer!) is the multiplicative inverse of $2$ modulo $n$. So we can always multiply by $\frac{n+1}{2}$ instead of dividing by $2$. I'm not sure this is as efficient as adding $n$ to the numerator, but it is a possibility.
Finally, for the specific application you've got, another approach is to replace the recurrence relations
$$
   \begin{cases}
     U_{2k} = U_k V_k \\
     V_{2k} = \frac12(V_k^2 + D U_k^2)
   \end{cases}
   \qquad
   \begin{cases}
     U_{2k+1} = \frac12(P U_{2k} + V_{2k}) \\
     V_{2k+1} = \frac12(D U_{2k} + PV_{2k})
   \end{cases}
$$
by the modified recurrence relations
$$
   \begin{cases}
     U_{2k}' = 2 U_k' V_k' \\
     V_{2k}' = V_k'^2 + D U_k'^2
   \end{cases}
   \qquad
   \begin{cases}
     U_{2k+1}' = P U_{2k}' + V_{2k}' \\
     V_{2k+1}' = D U_{2k}' + PV_{2k}'
   \end{cases}
$$
We get these recurrence relations by the substitution $(U_k', V_k') = (2^{k-1}U_k, 2^{k-1}V_k)$, which gets rid of the extra $\frac12$'s floating around.
In the end, you'll get $U_{\delta(n)}' = 2^{\delta(n)-1} U_{\delta(n)}$. Since $n$ is odd, we have $U_{\delta(n)}' \equiv 0 \pmod n$ if and only if $U_{\delta(n)} \equiv 0 \pmod n$, so we haven't changed anything - but the new recurrence relations don't require us to divide by $2$.
