To prove that for an odd prime $p$, there exist integers $a$, $b$, and $k$ such that

$a^2 + b + 1 = kp$ and $0 < k < p,$

we can proceed with the following steps:

Step 1: Consider quadratic residues modulo $p$

A key insight comes from the study of quadratic residues modulo $p$. For any integer $a$, the values $a^2 \mod p$ will give the quadratic residues mod $p$. Since $p$ is odd, there are exactly $\frac{p+1}{2}$ distinct quadratic residues modulo $p$, and the remaining $\frac{p-1}{2}$ numbers are non-residues.

Step 2: Equation modulo $p$

We are looking for integers $a$, $b$, and $k$ such that

$a^2 + b + 1 \equiv 0 \pmod{p}.$

This is equivalent to

$a^2 + b \equiv -1 \pmod{p}.$

For each value of $a^2 \mod p$, we want to check if we can find $b$ such that

$b \equiv -1 - a^2 \pmod{p}.$

Step 3: Choice of $k$

Once we have $a$ and $b$ such that $a^2 + b + 1 = kp$, we can solve for $k$ by dividing both sides of the equation by $p$. Since $a^2 + b + 1 \equiv 0 \pmod{p}$, we know that the left-hand side is divisible by $p$, and hence

$k = \frac{a^2 + b + 1}{p}$

will be an integer. Moreover, $k$ satisfies $0 < k < p$ because $a^2 + b + 1$ is less than $p^2$ but greater than 0, thus ensuring that $k$ remains in the desired range.

Step 4: Existence of $a$ and $b$

We need to show that for any $p$, we can always find suitable $a$ and $b$. Since the set of quadratic residues and the integers modulo $p$ cover all values modulo $p$, and because $-1$ is always a