2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ Thanks very much! Now, it's very clear. :-) $\endgroup$ – Larry Freeman Aug 12 '13 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.