I've been reviewing the following:
$$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$
where:
- $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} > ip_k\# > (v_i-c)p_{k+1}$
- $i$ is an integer such that $1 \le i \le p_{k+1}-1$
- $\left\lfloor\frac{a}{b}\right\rfloor$ is a floor function
I hit a result that surprises me.
Let $[v_i]$ be a residue modulo $p_k\#$ so that: $$v_ip_{k+1} \equiv [v_i] \pmod {p_k\#}$$
Let $[v_l]$ be the lowest value and $[v_h]$ be the highest value in the set $\left\{[v_1], [v_2], \cdots, [v_{p_{k+1}-1}]\right\}$
I have found that $[v_h] - [v_l] \le 2*p_{k+1}$ for $3 \le p_k \le 1997$
(Note: I have not yet tested $p_k > 1997$).
For example:
Let $p_{k+1} = 1999$ and $p_k = 1997$
The highest residue is $[v_{223}]$ where $1999*v_{223} \equiv 3999 \pmod {1997\#}$
The lowest residue is at $[v_{669}]$ where $1999*v_{669} \equiv 3 \pmod {1997\#}$
So that:
$$[v_{223}] - [v_{660}] = 3999 - 3 = 3996 \le 2*1999 = 3998$$
Are my calculations correct? Does this pattern hold for all primes? If not, at what point, does the pattern stop? If my calculations are correct, can someone help me to understand why this is true?
Thanks very much!
-Larry
Let us write $i\, p_k\# = q_{ik}\cdot p_{k+1} + r_{ik}$, with the remainder satisfying $0 \leqslant r_{ik} < p_{k+1}$.
Then you have $v_i = q_{ik} + c_i$, and hence
$$v_i p_{k+1} = q_{ik}p_{k+1} + c_i p_{k+1} = (i\ p_k\# - r_{ik}) + c_ip_{k+1} = i \, p_k\# + (p_{k+1} - r_{ik}) + (c_i-1)p_{k+1},$$
thus the remainder of $v_i p_{k+1}$ modulo $p_k\#$ is
$$(p_{k+1} - r_{ik}) + (c_i-1)p_{k+1}$$
and the first summand is always positive and at most $p_{k+1}$, and the second is either $0$ or $p_{k+1}$, depending on whether $c_i = 1$ or $c_i = 2$, whence
$$0 < [v_i] \leqslant 2p_{k+1}.$$