# Bounding solutions of a diophantine equation

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.

• The displayed equation is equivalent to $$i\equiv sj\pmod k$$ – Barry Cipra Jul 6 '16 at 5:53

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

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

• How do you get from the congruence $i\equiv sj$ to the equality $(i+j)^2=(sj+j)^2$? For example, if $s=10$, $k=13$, and $j=4$, then $i=1$ solves the congruence, not just $i=40$. – Barry Cipra Jul 6 '16 at 12:05
• You are absolutely right, let me give it some thought. – Inactive - Objecting Extremism Jul 6 '16 at 13:47
• Sorry, I still don't think that's right. In the example I gave, $(i+j)^2=(1+4)^2=25$, while $(sj+j)^2=(10\cdot4+4)^2=44^2=1936$. – Barry Cipra Jul 6 '16 at 16:03