TAOCP 4.3.2 Exercise 1

Find all integers $u$ such that u \bmod 7 = 1,\qquad u \bmod 11 = 0,\qquad u \bmod 13 = 5,

taocpmathematicsalgorithmsvolume-2project

Section 4.3.2: Modular Arithmetic

Exercise 1. [39] Find all integers $u$ that satisfy all of the following conditions: $u \bmod 7 = 1$, $u \bmod 11 = 0$, $u \bmod 13 = 5$, $0 \le u < 1000$.

Verified: yes
Solve time: 4m13s

Setup

Find all integers $u$ such that

$$ u \bmod 7 = 1,\qquad u \bmod 11 = 0,\qquad u \bmod 13 = 5, $$

with

$$ 0 \le u < 1000. $$

Since

$$ 7 \perp 11,\qquad 7 \perp 13,\qquad 11 \perp 13, $$

the moduli are relatively prime in pairs. By Theorem C, there is exactly one solution modulo

$$ m = 7\cdot 11\cdot 13 = 1001. $$

Because the interval $0 \le u < 1000$ contains exactly one representative of each residue class modulo $1001$ except $1000$, it suffices to determine the unique solution modulo $1001$.

Solution

Let

$$ u=11k. $$

The condition $u \bmod 7=1$ becomes

$$ 11k \equiv 1 \pmod 7. $$

Since $11\equiv 4\pmod 7$,

$$ 4k\equiv 1\pmod 7. $$

Because

$$ 4\cdot 2=8\equiv 1\pmod 7, $$

multiplication by $2$ gives

$$ k\equiv 2\pmod 7. $$

Write

$$ k=2+7t. $$

Then

$$ u=11(2+7t)=22+77t. $$

Now impose the condition $u \bmod 13=5$:

$$ 22+77t\equiv 5\pmod{13}. $$

Reducing modulo $13$,

$$ 22\equiv 9,\qquad 77\equiv 12, $$

hence

$$ 9+12t\equiv 5\pmod{13}. $$

Therefore

$$ 12t\equiv -4\equiv 9\pmod{13}. $$

Since $12\equiv -1\pmod{13}$,

$$ -t\equiv 9\pmod{13}, $$

so

$$ t\equiv -9\equiv 4\pmod{13}. $$

Write

$$ t=4+13s. $$

Substituting,

$$ u=22+77(4+13s) =22+308+1001s =330+1001s. $$

Thus the complete set of solutions is

$$ u\equiv 330\pmod{1001}. $$

The interval $0\le u<1000$ contains only the value

$$ u=330. $$

Hence the required integer is

$$ \boxed{330}. $$

Verification

Compute the three residues:

$$ 330 \bmod 7 = 1, $$

because $330=7\cdot 47+1$;

$$ 330 \bmod 11 = 0, $$

because $330=11\cdot 30$;

$$ 330 \bmod 13 = 5, $$

because $330=13\cdot 25+5$.

All conditions are satisfied.

By Theorem C, there is exactly one solution modulo

$$ 1001=7\cdot 11\cdot 13. $$

Since $330$ lies in the prescribed interval $0\le u<1000$, no other integer in that interval can satisfy the conditions.

Therefore

$$ \boxed{u=330}. $$

Notes

Using the constructive proof of Theorem C, one may also form the solution from equation (9). Both methods yield the same residue class

$$ u\equiv 330\pmod{1001}. $$

Thus the unique integer in the required range is

$$ \boxed{330}. $$