$p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Question

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$.

I believe I've shown the above but for $0<x,y<{p}$. We have that $c$ and $p$ are relatively prime. This implies that $[c]$ has a multiplicative inverse in $\mathbb{Z}_p$. We can then choose $[y]=[1]$ and in $\mathbb{Z}_p$ we get $$[c]\cdot [x]=[y] \implies [x] = [c]^{-1} \cdot [1] = [c]^{-1}$$

$$ \implies x \equiv c^{-1} \bmod p \implies p \text{ divides } cx - y.$$ Where we choose $c^{-1} \in [c]^{-1}$ such that $0<c^{-1}<p$.

I'm not sure how to approach the case for $p>3,0<x,y<\sqrt{p}$ though.

Answer 1

Your assertion doesn't hold. If we consider $p=5$ and $c=4$ then, with the assumptions $0<x,y<\sqrt{5},$ we have $x,y\in\{1,2\}.$ Now:

• $x=y=1\implies cx-y=4-1=3,$ which is not divisible by $5,$
• $x=1,y=2\implies cx-y=4-2=2,$ which is not divisible by $5,$
• $x=2,y=1\implies cx-y=8-1=7,$ which is not divisible by $5,$
• $x=y=2\implies cx-y=8-2=6,$ which is not divisible by $5.$