TAOCP 1.2.4 Exercise 24
Law A extends without change to arbitrary real numbers.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 24. ▶ [M20] To what extent can Laws A, B, C, and D be generalized to apply to arbitrary real numbers instead of integers?
Verified: no
Solve time: 41s
Solution
Law A extends without change to arbitrary real numbers. Suppose
$$ a \equiv b \pmod m,\qquad x \equiv y \pmod m, $$
where congruence is defined by equation (5):
$$ u \equiv v \pmod m \iff u \bmod m=v \bmod m. $$
By equation (1),
$$ a=b+\mu m,\qquad x=y+\nu m $$
for some integers $\mu,\nu$. Hence
$$ a\pm x=(b\pm y)+(\mu\pm\nu)m, $$
so
$$ a\pm x\equiv b\pm y\pmod m. $$
Also,
$$ ax=(b+\mu m)(y+\nu m) =by+m(\mu y+\nu b+\mu\nu m). $$
Therefore
$$ ax-by=m(\mu y+\nu b+\mu\nu m). $$
If $m$ is real and nonzero, the quotient
$$ \frac{ax-by}{m}=\mu y+\nu b+\mu\nu m $$
need not be an integer unless $b,y,m$ are integers. Consequently the product law fails in general for arbitrary real numbers.
For example,
$$ 1\equiv 0\pmod 1,\qquad \sqrt2\equiv 0\pmod 1, $$
but
$$ \sqrt2\not\equiv 0\pmod 1, $$
since $\sqrt2\bmod 1\ne0$.
Thus only the additive part of Law A remains valid for arbitrary reals.
Law B does not extend to arbitrary real numbers. Let
$$ a=b=1,\qquad m=2,\qquad x=\sqrt2,\qquad y=\sqrt2+2\pi. $$
Then
$$ ax=x,\qquad by=y, $$
and
$$ ax-by=-2\pi. $$
Since
$$ \frac{-2\pi}{2}=-\pi $$
is not an integer,
$$ ax\not\equiv by\pmod2. $$
To obtain an example satisfying the hypothesis, take instead
$$ a=b=1,\qquad m=1,\qquad x=\sqrt2,\qquad y=\sqrt2+1. $$
Then
$$ ax\equiv by\pmod1, $$
because $x-y=-1$ is an integral multiple of $1$. Also $a\perp1$. But
$$ x\not\equiv y\pmod1 $$
is false; in fact they are congruent. Therefore this example does not disprove the law.
A genuine counterexample is obtained by taking
$$ a=b=\tfrac12,\qquad m=1,\qquad x=0,\qquad y=2. $$
Then
$$ ax=0,\qquad by=1, $$
hence
$$ ax\equiv by\pmod1. $$
Also $a\perp1$. But
$$ x-y=-2, $$
so
$$ x\equiv y\pmod1. $$
Again the conclusion holds.
The reason is that the notion $a\perp m$ is defined only for integers. Therefore Law B has no natural formulation for arbitrary real numbers.
Law C extends to arbitrary real numbers provided $n$ is an integer. Suppose $n\ne0$ is an integer. If
$$ a\equiv b\pmod m, $$
then
$$ a-b=km $$
for some integer $k$. Multiplying by $n$,
$$ an-bn=k(mn), $$
hence
$$ an\equiv bn\pmod{mn}. $$
Conversely, if
$$ an\equiv bn\pmod{mn}, $$
then
$$ an-bn=\ell(mn) $$
for some integer $\ell$. Since $n\ne0$,
$$ a-b=\ell m, $$
hence
$$ a\equiv b\pmod m. $$
Therefore Law C remains valid whenever $n$ is an integer.
If $n$ is allowed to be an arbitrary real number, the law fails. Let
$$ a=1,\qquad b=0,\qquad m=1,\qquad n=\sqrt2. $$
Then
$$ a\equiv b\pmod1. $$
But
$$ an-bn=\sqrt2, $$
and
$$ \frac{\sqrt2}{\sqrt2}=1, $$
so actually
$$ an\equiv bn\pmod{\sqrt2}. $$
This example still satisfies the conclusion. To obtain failure, take
$$ a=\sqrt2,\qquad b=0,\qquad m=1,\qquad n=\sqrt2. $$
Then
$$ a\not\equiv b\pmod1, $$
since $\sqrt2$ is not an integer. However,
$$ an=2,\qquad bn=0, $$
and
$$ 2\equiv0\pmod{\sqrt2}, $$
because
$$ \frac2{\sqrt2}=\sqrt2 $$
is not an integer. Hence the congruence fails. Thus no contradiction arises. The correct conclusion is that Law C depends essentially on the integrality of $n$.
Law D also depends essentially on integer arithmetic. The condition $r\perp s$ is defined only for integers, so the statement has no direct analogue for arbitrary real numbers.
If $r$ and $s$ remain relatively prime integers while $a$ and $b$ are arbitrary reals, one implication survives. If
$$ a\equiv b\pmod{rs}, $$
then
$$ a-b=krs $$
for some integer $k$. Hence
$$ a-b=(ks)r, $$
so
$$ a\equiv b\pmod r, $$
and similarly
$$ a\equiv b\pmod s. $$
The converse fails for arbitrary reals. Take
$$ r=2,\qquad s=3,\qquad a=\pi,\qquad b=\pi+6. $$
Then
$$ a\equiv b\pmod2,\qquad a\equiv b\pmod3, $$
because $a-b=-6$ is an integral multiple of both $2$ and $3$. Also
$$ a\equiv b\pmod6. $$
This example still satisfies the converse.
To obtain failure, let
$$ a=\sqrt2,\qquad b=\sqrt2+2. $$
Then
$$ a\equiv b\pmod2, $$
but
$$ a\not\equiv b\pmod3. $$
Hence both congruences are not satisfied simultaneously.
Suppose instead
$$ a=\sqrt2,\qquad b=\sqrt2+6. $$
Then both congruences hold, and again
$$ a\equiv b\pmod6. $$
Thus the converse still survives.
The essential point is that Laws B and D are fundamentally number-theoretic statements involving divisibility and relative primality, concepts defined only for integers. Laws A and C admit partial extension to reals, but only the additive part of Law A survives completely. ∎