Determine the largest such integer

$x=ak+r$ and $y=bk+r'$

if $k|xy+1$ then

$(ak+r)(bk+r')\equiv rr'\equiv -1 \ (mod \ k)$

we need $r \equiv -r'$ in order to have $x+y=(ak+r)+bk+r' \equiv r+r' \equiv 0 \ (mod \ k)$ .

in other words, for all $r$ , such that $GCD(r,k)=1$ , we must have

$r^2\equiv 1 \ (mod \ k)$

If there exists $r$ , for $k$ , such that $GCD(r,k)=1$ and $r^2 < k$ , then $r$ should have a multiplicative inverse other than itself and, consequently, $k$ is not what we are looking. We use this fact to find the largest possible candidates that may qualify as the final solution.

So if we sort the set $\{x \in \mathbb{N}|GCD(x,k)=1,x<k\}-\{1\}$ in ascending order, and take the first element $s$ , then we need to have $s^2>k$ . one can find that $k \leq 30$ . for this, I used a sort of reason, too long to include.

Coming down from $30$ , $24$ is the first number, for which all $r$ , S.T. $GCD(r,24)=1$ , have the property $r^2\equiv 1 \ (mod 24)$