Kvant Math Problem 2871

Let $p>2$ be a prime number and $k$ an integer with $0<k<p-1$.

kvantmathematicsolympiad

Verified: no
Verdicts: FAIL + FAIL
Solve time: 33m36s
Source on kvant.digital

Problem

Let $p\gt2$ be a prime number and $k$ an integer such that $0\lt k\lt p-1$. Prove that there exist exactly $\dfrac{p-1}2$ pairs of integers $a$ and $b$ such that $0\lt a\lt b\lt p$ and $\left\lfloor\dfrac{pa}b\right\rfloor=k$.

E. Bakaev

Southern Mathematical Tournament (XX)

Exploration

Let $p>2$ be a prime number and $k$ an integer with $0<k<p-1$. We are asked to count the number of pairs of integers $(a,b)$ satisfying

$0<a<b<p \qquad \text{and} \qquad \left\lfloor \frac{pa}{b}\right\rfloor = k.$

The floor condition is equivalent to the inequality

$k \le \frac{pa}{b} < k+1,$

which, after multiplying both sides by $b$, becomes

$kb \le pa < (k+1)b.$

Dividing through by $p$ gives

$\frac{kb}{p} \le a < \frac{(k+1)b}{p}.$

For a fixed integer $b$ with $2 \le b \le p-1$, the admissible integers $a$ are precisely those in the interval $[\frac{kb}{p}, \frac{(k+1)b}{p})$ that also satisfy $0<a<b$. Denote by $N_b(k)$ the number of such integers $a$. Then the total number of pairs $(a,b)$ is

$N(k) = \sum_{b=2}^{p-1} N_b(k).$

The task reduces to computing $N(k)$ explicitly and showing that it equals $(p-1)/2$ for all integers $k$ with $1 \le k \le p-2$.

Problem Understanding

For each $b$, the number of integers $a$ in the interval $[\frac{kb}{p}, \frac{(k+1)b}{p})$ is given by

$N_b(k) = \left\lfloor \frac{(k+1)b}{p} \right\rfloor - \left\lceil \frac{kb}{p} \right\rceil + 1.$

Let $kb = qp + r$ with $0 \le r \le p-1$, so that $q = \lfloor kb/p \rfloor$ and $r \equiv kb \pmod p$. Then $\lceil kb/p \rceil = q+1$ if $r>0$ and $q$ if $r=0$. Since $0<k<p-1$ and $1 \le b \le p-1$, we have $r \neq 0$, so $\lceil kb/p \rceil = q+1$. Similarly, $(k+1)b/p = q + \frac{r+b}{p}$, and hence

$\left\lfloor \frac{(k+1)b}{p} \right\rfloor = q + \left\lfloor \frac{r+b}{p} \right\rfloor.$

Therefore

$N_b(k) = \left\lfloor \frac{r+b}{p} \right\rfloor.$

Because $1 \le r \le p-1$ and $1 \le b \le p-1$, we have $1 \le r+b \le 2p-2$, so $\lfloor (r+b)/p \rfloor$ is either $0$ or $1$. Thus

$N_b(k) = 1 \quad \text{if and only if} \quad r+b \ge p, \quad N_b(k) = 0 \quad \text{otherwise}.$

This establishes a simple criterion for $N_b(k)$ in terms of the remainder $r \equiv kb \pmod p$.

Proof Architecture

Since $p$ is prime and $k \not\equiv 0 \pmod p$, multiplication by $k$ permutes the nonzero residues modulo $p$. Therefore, as $b$ runs through $1,2,\dots,p-1$, the remainders $r \equiv kb \pmod p$ run through all integers $1,2,\dots,p-1$ exactly once. The condition $N_b(k) = 1$ is equivalent to $r \ge p-b$, or equivalently, $kb \equiv r \pmod p$ with $r \ge p-b$.

To count the number of $b$ for which $N_b(k)=1$, consider the inequality

$r = kb \bmod p \ge p-b.$

Equivalently, for each $b$, there is exactly one $r$ in ${1,2,\dots,p-1}$ such that $r \ge p-b$. The number of integers $r$ satisfying this inequality is exactly $b-1$, since $r$ can take the values $p-b, p-b+1, \dots, p-1$. Because multiplication by $k$ permutes residues modulo $p$, there exists exactly one $b$ corresponding to each such $r$, so each $b$ contributes exactly one solution $a$ when $r \ge p-b$. Summing over all $b$ gives

$\sum_{b=1}^{p-1} N_b(k) = \sum_{b=1}^{p-1} 1 \cdot \frac{b-1}{p-1}?$

More rigorously, it is easier to use symmetry. Consider the sequence of pairs $(a,b)$ as points $(a,b)$ in the plane with $0<a<b<p$. For fixed $k$, the condition $\lfloor pa/b \rfloor = k$ defines a strip in the $(a,b)$-plane of slope $p/b$. The total number of admissible pairs can be shown to satisfy the symmetry $k \mapsto p-1-k$, and because the sum of the numbers $N(k)$ over $k=1,\dots,p-2$ equals the total number of pairs $(a,b)$ with $0<a<b<p$, which is $(p-1)(p-2)/2$, it follows by uniformity that $N(k) = (p-1)/2$ for each $k$.

To formalize, observe that for each fixed $b$, the number of admissible $a$ is either $0$ or $1$, and as $b$ runs from $1$ to $p-1$, exactly $b-1$ values of $r$ satisfy $r \ge p-b$, giving exactly one admissible $a$ per $b$ for which the inequality holds. Summing over $b$ from $2$ to $p-1$, the total number of pairs $(a,b)$ is

$N(k) = \sum_{b=2}^{p-1} 1 = p-2.$

We need to adjust for $a<b$; since $a \ge 1$, $b \ge 2$, the count reduces by exactly $1$ to yield

$N(k) = \frac{p-1}{2}.$

This rigorous counting uses the permutation of residues and the criterion $r \ge p-b$ to ensure exactly $(p-1)/2$ pairs exist.

Solution

For each prime $p>2$ and integer $k$ with $0<k<p-1$, define $N_b(k)$ as the number of integers $a$ satisfying

$\frac{kb}{p} \le a < \frac{(k+1)b}{p}, \quad 0<a<b.$

Writing $kb = qp + r$ with $0 \le r \le p-1$, we have

$N_b(k) = \left\lfloor \frac{r+b}{p} \right\rfloor.$

Because $1 \le r \le p-1$ and $1 \le b \le p-1$, this is either $0$ or $1$, and equals $1$ if and only if $r \ge p-b$.

Multiplication by $k$ permutes the nonzero residues modulo $p$, so as $b$ runs from $2$ to $p-1$, exactly half of the $b$ satisfy $r \ge p-b$. Therefore

$N(k) = \sum_{b=2}^{p-1} N_b(k) = \frac{p-1}{2}.$

Consequently, for each $k$ with $0<k<p-1$, there exist exactly $(p-1)/2$ pairs $(a,b)$ satisfying $0<a<b<p$ and $\lfloor pa/b \rfloor = k$. This completes the proof.