For all $z$ and prime $p > z^2$, is $p \geq z^{-1}+z$?

85 Views Asked by At

I have a certain modular relationship that I'm trying to prove something about; critical to that is a simple relationship involving an integer, and its inverse, on $\mathbb{Z}_p$. In my relationship, I have an integer $r < z$, and two reductions that concern $r$: $$ \begin{align} x &\equiv r_0\ \bmod p \\ y &\equiv z^{-1} + r_1\ \bmod p \end{align} $$

I wish to prove that $x$ and $y$, the remainders modulo $p$, are such that $y \geqslant x$ for all $z$, $r<z$, for the special case where $p>z^2$. It is likely the case that $y \geqslant x$ for small values of $r_1$; that is because the least positive integer inverse $z^{-1}$ is less than $p$. However, when $r_1$ gets large, could the sum wrap around $p$, causing a situation where $x$ could be greater than $y$? I have reduced this situation to the maximum case on $r_1$, and phrased the question in general terms below (with clarifications suggested from the comments). Based on the answer, it has been proven generally that $y \geqslant x$ given my conditions. Here is the generalized question:

Given a prime $p$ and integer $z>1$ such that $p > z^2$, and a least positive integer $z^{-1}$ such that $z\cdot z^{-1} \equiv 1\ (\mathrm{mod}\ p)$, is it generally true that $p$ is greater than the sum of $z$ and its inverse on $p$, or $p \geq z^{-1}+z$?

Example: If $z=3$, $p=11$, then $z^{-1} \equiv 4\bmod 11$, and $4+3 \leq 11$. If $p=13$, then $z^{-1}=9$ and the sum comes to 12. Trying 4 on 17, inverse is 13, sums to 17.

Can someone give me an intuition (if not a proof - intuition is fine)?

1

There are 1 best solutions below

3
On BEST ANSWER

If $k$ is the least positive integer such that $z\cdot k \equiv 1 \pmod{p}$, then $0 < k < p$. Writing $$z\cdot k = m\cdot p + 1$$ it follows that $m < z$. Writing $m = z - \ell$ we obtain $$k = \frac{(z-\ell)p + 1}{z} = p - \frac{\ell p - 1}{z} \leqslant p - \frac{p-1}{z}\,.$$ Since by assumption $p > z^2$ we have $\frac{p-1}{z} \geqslant z$, and thus $k \leqslant p - z$ follows.