Take $ui = pt_i +j_i$ where $p$ is a prime number and $u(p-r) \equiv 1 $ $(\mbox{mod p})$ for positive integers $1 \le i, r, j_i\le p-1$ and $t_i \ge 0$. How can I prove that:

\begin{equation} it_r - rt_i + i \le r \end{equation}

I guess that an other way to look at it is:

\begin{equation} i\left \lceil{\frac{ur}{p}}\right \rceil \le r\left \lceil{\frac{ui}{p}}\right \rceil \end{equation}

I ran this on sage and I believe it to be true for any $p$.

  • $\begingroup$ Are you sure you mean $u\left(p-r\right) \equiv 1 \mod p$ ? The first $p$ looks redundant. $\endgroup$ Jul 7 '15 at 1:12
  • $\begingroup$ Yes, I was using $p-r$ somewhere else in my equations, I guess looking at it this way helps! Thank you. $\endgroup$ Jul 7 '15 at 2:53

We have $1\equiv u\left( p-r\right) \equiv u\left( -r\right) =-ur\operatorname{mod}p$, so that $p\mid1+ur=ur+1$. Hence, $\left\lceil \dfrac{ur}{p}\right\rceil =\dfrac{ur+1}{p}$.

We need to prove that $i\left\lceil \dfrac{ur}{p}\right\rceil \leq r\left\lceil \dfrac{ui}{p}\right\rceil $. We transform this inequality equivalently:

$i\left\lceil \dfrac{ur}{p}\right\rceil \leq r\left\lceil \dfrac{ui} {p}\right\rceil $

$\Longleftrightarrow\ i\cdot\dfrac{ur+1}{p}\leq r\left\lceil \dfrac{ui} {p}\right\rceil $ (since $\left\lceil \dfrac{ur}{p}\right\rceil =\dfrac {ur+1}{p}$)

$\Longleftrightarrow\ i\left( ur+1\right) \leq pr\left\lceil \dfrac{ui} {p}\right\rceil $ (here, we have multiplied both sides of our inequality by $p$).

$\Longleftrightarrow\ iur+i\leq pr\left\lceil \dfrac{ui}{p}\right\rceil $

$\Longleftrightarrow\ i\leq pr\left\lceil \dfrac{ui}{p}\right\rceil -iur$.

Now, $pr\left\lceil \dfrac{ui}{p}\right\rceil -iur\equiv -iur=i\underbrace{\left( -ur\right) }_{\equiv1\operatorname{mod}p}\equiv i\operatorname{mod}p$. Hence, the residue of $pr\left\lceil \dfrac{ui} {p}\right\rceil -iur$ modulo $p$ is $i$ (because $0\leq i\leq p-1$). But this residue must be $\leq pr\left\lceil \dfrac{ui}{p}\right\rceil -iur$ (because $pr\underbrace{\left\lceil \dfrac{ui}{p}\right\rceil }_{\geq\dfrac{ui}{p} }-iur\geq pr\cdot\dfrac{ui}{p}-iur=0$). Hence, we obtain $i\leq pr\left\lceil \dfrac{ui}{p}\right\rceil -iur$. This proves the inequality in question.

  • $\begingroup$ Nice catch on the $u\left(p-r\right) \equiv u\left(-r\right)\operatorname{mod}p$ and basing the proof on the residue. $\endgroup$
    – BoppreH
    Jul 7 '15 at 2:44

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.