How are these two equations congruent?

53 Views Asked by At

For the Lucas probable prime test there are two way to calculate $V_{2k}$. I get expected results with $V_{2k}=\frac{V_k^2+DU_k^2}{2}$ but when I try $V_{2k}=V^2_k -2Q^k$ it doesn't work.

Here is a small example. Let n=5. Then P=1 and D=-7 and Q=2. D can be verified using this online calculator.

Initial terms are $U_1=1, V_1=1$
For the purpose of this example I will skip calculating $U_2$ since $V_2$ doesn't rely on it.
So using the formula $V_2=V_k^2-2Q^k=V_1^2-2Q^1=1-2(2)^2=-7$
Since these equations are done mod 5 $V_2\equiv-2\equiv3$

But when I try the other equation it is different: $V_2=\frac{V_k^2+DU_k^2}{2}=\frac{V_2^2+DU_2^2}{2}=\frac{1+(-7)1^2}{2}=-3\equiv2 (mod 5)$

The $V_k^2-2Q^k$ didn't work when I used it. How do I use it properly? I'm guessing it has to do with which numbers are chosen from mod.

1

There are 1 best solutions below

0
On BEST ANSWER

Nothing to do with modular arithmetic: you should have $V_2 = V_1 - 2Q^1 = 1 - 2 \cdot 2 = -3$, not $V_2 = V_1 - 2Q^2$. The exponent on $Q$ should be $k$, not $2k$.