2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Are you sure you mean $u\left(p-r\right) \equiv 1 \mod p$ ? The first $p$ looks redundant. $\endgroup$ Jul 7, 2015 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, 2015 at 2:53

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2015 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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