Skip to main content
added 109 characters in body
Source Link
user40023
user40023

Regarding $p$-adic valuation of Lucas sequences, a quite precise result is given in [1].

Theorem. Let $(u_n)_{n \geq 0}$ be a nondegenerate Lucas sequence with $u_0 = 0$, $u_1 = 1$, and $u_{n+2} = a u_{n+1} + b u_n$ for all $n \geq 0$, where $a$ and $b$ are two integers. Furthermore, let $p$ be a prime number not dividing $b$.

Then for any positive integer $n$ we have $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{p\tau(p)}) - 1 & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \mid n, \\ v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \nmid n, \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ where $\Delta := a^2 + 4b$ and $\tau(p)$ is the rank of apparition of $p$ in $(u_n)_{n \geq 0}$, i.e., the least positive integer $m$ such that $p \mid u_m$. Moreover, if $p \geq 3$ then $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ while if $p \geq 5$ then $$v_p(u_n) = \begin{cases} v_p(n) & \text{ if } p \mid \Delta , \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n . \end{cases}$$ Actually, in [1] the theorem is stated for $a$ and $b$ relatively prime. However, as explained in [2], the result holds even if $a$ and $b$ are not coprime.

[1] C. Sanna, The $p$-Adic Valuation of Lucas Sequences, Fibonacci Quart. 54 (2016), no. 2, 118–124. (Free preprint: https://www.researchgate.net/publication/304251918_The_p-adic_valuation_of_Lucas_sequences)

[2] N. Murru, C. Sanna, On the k-regularity of the k-adic valuation of Lucas sequences http://arxiv.org/abs/1603.09310

Regarding $p$-adic valuation of Lucas sequences, a quite precise result is given in [1].

Theorem. Let $(u_n)_{n \geq 0}$ be a nondegenerate Lucas sequence with $u_0 = 0$, $u_1 = 1$, and $u_{n+2} = a u_{n+1} + b u_n$ for all $n \geq 0$, where $a$ and $b$ are two integers. Furthermore, let $p$ be a prime number not dividing $b$.

Then for any positive integer $n$ we have $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{p\tau(p)}) - 1 & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \mid n, \\ v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \nmid n, \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ where $\Delta := a^2 + 4b$ and $\tau(p)$ is the rank of apparition of $p$ in $(u_n)_{n \geq 0}$, i.e., the least positive integer $m$ such that $p \mid u_m$. Moreover, if $p \geq 3$ then $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ while if $p \geq 5$ then $$v_p(u_n) = \begin{cases} v_p(n) & \text{ if } p \mid \Delta , \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n . \end{cases}$$ Actually, in [1] the theorem is stated for $a$ and $b$ relatively prime. However, as explained in [2], the result holds even if $a$ and $b$ are not coprime.

[1] C. Sanna, The $p$-Adic Valuation of Lucas Sequences, Fibonacci Quart. 54 (2016), no. 2, 118–124.

[2] N. Murru, C. Sanna, On the k-regularity of the k-adic valuation of Lucas sequences http://arxiv.org/abs/1603.09310

Regarding $p$-adic valuation of Lucas sequences, a quite precise result is given in [1].

Theorem. Let $(u_n)_{n \geq 0}$ be a nondegenerate Lucas sequence with $u_0 = 0$, $u_1 = 1$, and $u_{n+2} = a u_{n+1} + b u_n$ for all $n \geq 0$, where $a$ and $b$ are two integers. Furthermore, let $p$ be a prime number not dividing $b$.

Then for any positive integer $n$ we have $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{p\tau(p)}) - 1 & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \mid n, \\ v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \nmid n, \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ where $\Delta := a^2 + 4b$ and $\tau(p)$ is the rank of apparition of $p$ in $(u_n)_{n \geq 0}$, i.e., the least positive integer $m$ such that $p \mid u_m$. Moreover, if $p \geq 3$ then $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ while if $p \geq 5$ then $$v_p(u_n) = \begin{cases} v_p(n) & \text{ if } p \mid \Delta , \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n . \end{cases}$$ Actually, in [1] the theorem is stated for $a$ and $b$ relatively prime. However, as explained in [2], the result holds even if $a$ and $b$ are not coprime.

[1] C. Sanna, The $p$-Adic Valuation of Lucas Sequences, Fibonacci Quart. 54 (2016), no. 2, 118–124. (Free preprint: https://www.researchgate.net/publication/304251918_The_p-adic_valuation_of_Lucas_sequences)

[2] N. Murru, C. Sanna, On the k-regularity of the k-adic valuation of Lucas sequences http://arxiv.org/abs/1603.09310

Source Link
user40023
user40023

Regarding $p$-adic valuation of Lucas sequences, a quite precise result is given in [1].

Theorem. Let $(u_n)_{n \geq 0}$ be a nondegenerate Lucas sequence with $u_0 = 0$, $u_1 = 1$, and $u_{n+2} = a u_{n+1} + b u_n$ for all $n \geq 0$, where $a$ and $b$ are two integers. Furthermore, let $p$ be a prime number not dividing $b$.

Then for any positive integer $n$ we have $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{p\tau(p)}) - 1 & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \mid n, \\ v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \nmid n, \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ where $\Delta := a^2 + 4b$ and $\tau(p)$ is the rank of apparition of $p$ in $(u_n)_{n \geq 0}$, i.e., the least positive integer $m$ such that $p \mid u_m$. Moreover, if $p \geq 3$ then $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ while if $p \geq 5$ then $$v_p(u_n) = \begin{cases} v_p(n) & \text{ if } p \mid \Delta , \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n . \end{cases}$$ Actually, in [1] the theorem is stated for $a$ and $b$ relatively prime. However, as explained in [2], the result holds even if $a$ and $b$ are not coprime.

[1] C. Sanna, The $p$-Adic Valuation of Lucas Sequences, Fibonacci Quart. 54 (2016), no. 2, 118–124.

[2] N. Murru, C. Sanna, On the k-regularity of the k-adic valuation of Lucas sequences http://arxiv.org/abs/1603.09310