# Proving inequation with ceilings in Finite Field of characteristic $p$

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:

$$it_r - rt_i + i \le r$$

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

$$i\left \lceil{\frac{ur}{p}}\right \rceil \le r\left \lceil{\frac{ui}{p}}\right \rceil$$

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

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

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