Bounding solutions of a diophantine equation

Question

Let $k$ and $s$ be natural numbers such that $s^2-s+1 \equiv 0 \pmod{k}$. Consider the equation $$ -si+(s-1)j \equiv 0 \pmod{k} $$

In all examples of pairs $(s,k)$ that I've tested, I got $(i+j)^2>k$ for every solution with $0<i,j$. Is there a way to establish such a bound? Alternatively, can one prove that there is no positive solution with $i+j <\sqrt{k}$?

This problem comes from searching for invariant polynomials in two variables under a diagonal group action. I'm trying to bound the degree of a invariant monomial $x^iy^j$ from below.

Answer 1

Note that $s^2-s+1\equiv0$ mod $k$ can be rewritten in two ways:

$$s(s-1)\equiv-1 \mod k$$ and

$$s^2\equiv s-1\mod k$$

The first rewriting shows that $s$ is invertible mod $k$, which means the congruence

$$si\equiv(s-1)j\equiv s^2j \mod k$$ (where we've used the second rewriting) simplifies to

$$i\equiv sj\mod k$$

Squaring this gives

$$i^2\equiv s^2j^2\equiv(s-1)j^2=(sj)j-j^2\equiv ij-j^2\mod k$$

or

$$i^2-ij+j^2\equiv0\mod k$$

which means that $k$ divides $i^2-ij+j^2$. Now if $i$ and $j$ are positive integers satisfying this congruence, then $i^2-ij+j^2=(i-j)^2+ij$ is a positive number, hence cannot be less than $k$. Consequently

$$k\le i^2-ij+j^2\lt i^2+2ij+j^2=(i+j)^2$$

Answer 2

As noted in the comments, because $s$ satisfies $s^2-s+1\equiv0\pmod{k}$ we have $$-si+(s-1)j\equiv0\pmod{k}\qquad\Leftrightarrow\qquad i\equiv sj\pmod{k},$$ as $-s(s-1)\equiv1\pmod{k}$. So if $i,j>0$ then $s>0$, and $$(i+j)^2\geq(sj+j)^2=(s+1)^2j^2=(s^2+2s+1)j^2,$$ where $s^2+2s+1>s^2-s+1\geq k$. Hence $i+j>\sqrt{k}$.