1
$\begingroup$

This is a follow up question to my previous question.

Let $$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

Let $[v_i]$ be a residue modulo $p_k\#$ so that: $$v_ip_{k+1} \equiv [v_i] \pmod {p_k\#}$$

Is it correct to conclude that each $[v_i]$ is odd and distinct?

Here's my reasoning:

  • By the argument here:

$$[v_i] = (p_{k+1} - r_{ik}) + (c_i-1)p_{k+1}$$

  • Assume that $r_{ik} = r_{jk}$ so that:

$$i\, p_k\# - j\, p_k\#= q_{ik}\cdot p_{k+1} - q_{jk}\cdot p_{k+1}$$

  • Then $i=j$ since if $i \neq j$, then $q_{ik} \neq q_{jk}$ and $p_{k+1} \nmid p_k\#(i - j)$

  • If $q_{ik}$ is odd, then $r_{ik}$ is odd and $p_{k+1} - r_{ik}$ is even but not $0$, $c_{ik} = 2$, so $p_{k+1} - r_{ik} + (c_i-1){p_{k+1}} > p_{k+1}$ and is odd.

  • If $q_{ik}$ is even, then $r_{ik}$ is even and $p_{k+1} - r_{ik}$ is odd, $c_{ik} = 1$, so $p_{k+1} - r_{ik} < p_{k+1}$ and is odd.

  • So, in all cases, each $[v_i]$ is odd, distinct and $1 \le [v_i] < 2\cdot{p_{k+1}}$

$\endgroup$
  • 2
    $\begingroup$ Yes, that's correct. $\endgroup$ – Daniel Fischer Aug 12 '13 at 5:33

Your Answer

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

Browse other questions tagged or ask your own question.