TAOCP 3.2.1.1 Exercise 10

Section 3.2.1.1: Choice of Modulus

Exercise 10. [M26] The solution to exercise 9(b) sometimes works also when $a^2 > m$. Exactly how many multipliers $a$ are there for which the intermediate results in that method never exceed $m$, for all $x$ between $0$ and $m$?

Verified: yes
Solve time: 6m12s

---

Let

$$ m=aq+r,\qquad q=\left\lfloor \frac{m}{a}\right\rfloor,\qquad 0\le r<a. $$

Exercise 9(b) computes $ax \bmod m$ by writing

$$ x=q\left\lfloor \frac{x}{q}\right\rfloor +(x\bmod q) $$

and using

$$ ax = a(x\bmod q)+(aq)\left\lfloor \frac{x}{q}\right\rfloor \equiv a(x\bmod q)-r\left\lfloor \frac{x}{q}\right\rfloor \pmod m . $$

We seek all multipliers $a$ for which every intermediate quantity occurring in this method is $\le m$, for every $x$ with $0\le x\le m$.

First,

$$ 0\le x\bmod q<q, $$

hence

$$ 0\le a(x\bmod q)\le a(q-1)=aq-a<m. $$

Therefore the first product is always $<m$.

The only possible difficulty is the product

$$ r\left\lfloor \frac{x}{q}\right\rfloor . $$

Since $0\le x\le m=aq+r$,

$$ \left\lfloor\frac{x}{q}\right\rfloor \le \left\lfloor\frac{m}{q}\right\rfloor . $$

Now the method of Exercise 9(b) requires $r<q$. Therefore

$$ \left\lfloor\frac{m}{q}\right\rfloor = \left\lfloor a+\frac rq\right\rfloor =a, $$

and the maximum value of $r\lfloor x/q\rfloor$ is $ra$.

Hence the method is safe for all $x$ if and only if

$$ ra\le m. $$

Using $m=aq+r$,

$$ ra\le aq+r $$

which is equivalent to

$$ r(a-1)\le aq. $$

Since $r,q$ are nonnegative integers, this is equivalent to

$$ r\le q. $$

Indeed, if $r\le q$, then

$$ ra\le aq\le aq+r=m; $$

conversely, if $ra\le aq+r$, then

$$ r(a-1)\le aq, $$

and because $r,q$ are integers this forces $r\le q$.

Thus the exact condition is

$$ \boxed{,m\bmod a\le \left\lfloor\frac ma\right\rfloor, }. $$

It remains to count the integers $a$ satisfying this condition.

Write

$$ m=aq+r,\qquad 0\le r\le q. $$

Then

$$ m=aq+r\le aq+q=(a+1)q, $$

so

$$ \frac{m}{a+1}\le q\le \frac{m}{a}. $$

Conversely, if an integer $q$ satisfies

$$ \frac{m}{a+1}\le q\le \frac{m}{a}, $$

then

$$ m-aq\le q, $$

hence $r\le q$. Therefore the admissible multipliers are exactly those for which the interval

$$ \left[\frac{m}{a+1},,\frac{m}{a}\right] $$

contains an integer.

Now let

$$ d=\left\lfloor \frac{m}{a}\right\rfloor=q. $$

The interval contains an integer precisely when $d$ lies in it, namely when

$$ \frac{m}{a+1}\le d\le \frac{m}{a}. $$

Multiplying by positive quantities gives

$$ \frac{m}{d}-1\le a\le \frac{m}{d}. $$

Since $a$ is an integer, the admissible values corresponding to a fixed positive divisor $d$ of $m$ are exactly

$$ a=\frac{m}{d}-1 \qquad\text{or}\qquad a=\frac{m}{d}. $$

Indeed, if $d\mid m$, then $m/d$ is an integer and both values satisfy $r\le q$:

$$ a=\frac{m}{d} \implies r=0, $$

$$ a=\frac{m}{d}-1 \implies m=(a+1)d=ad+d, \quad r=d=q. $$

Conversely, every admissible $a$ arises in exactly one of these two ways, with $d=q$.

Thus the admissible multipliers are precisely

$$ a=\frac{m}{d} \quad\text{or}\quad a=\frac{m}{d}-1, \qquad d\mid m. $$

There are $\tau(m)$ values of the first type and $\tau(m)$ values of the second type. The only possible overlap occurs when

$$ \frac{m}{d_1} = \frac{m}{d_2}-1, $$

which is equivalent to

$$ m=d_1(d_1+1), $$

impossible because consecutive integers are coprime and both would have to divide $m$. Hence the two sets are disjoint except when

$$ \frac{m}{d}-1=\frac{m}{d}, $$

which cannot occur.

However, the value $a=0$ arises from $d=m$ in the second family:

$$ a=\frac{m}{m}-1=0. $$

Since a multiplier must satisfy $a\ge1$, this single value must be excluded.

Therefore the number of admissible multipliers is

$$ \tau(m)+(\tau(m)-1) = 2\tau(m)-1. $$

Hence the answer is

$$ \boxed{2\tau(m)-1}. $$

Equivalently, the admissible multipliers are exactly those $a$ for which

$$ m\bmod a\le \left\lfloor \frac{m}{a}\right\rfloor . $$

The count of such multipliers is

$$ \boxed{2\tau(m)-1}. $$