(^96) 3. Factors and Zeros
is also a solution of the congruence
q(t) q 0 (modp’).
- Find all the positive integers less than 100 which leave a remainder 1
when divided by 3, remainder 2 when divided by 4 and remainder 2
when divided by 5. Perform this task in the following way: (1) write
out in increasing order those numbers congruent to 2 modulo 5; (2)
cross out those which are not congruent to 2 modulo 4; (3) cross out
those which are not congruent to 1 modulo 3.
How many answers are there? Suppose we remove the restriction that
the number be positive and less than 100; what would the answers
be? - Find a positive integer not exceeding 1000 which leaves a remainder
3 upon division by 7, 4 upon division by 11 and 2 upon division by
- Suppose that the positive integer m is the product of two integers
u and v with greatest common divisor 1. Let a and b be any two
integers. Prove that there exists exactly one integer c such that
O<c<m-1cEa (modu) c E b (modv).
(You will need the result of Exercise 1.6.6(d).)- Chinese Remainder Theorem. Let m = m1m2... m, be the product
of r integers mi, each pair of which has greatest common divisor 1.
Suppose al, a2,... ,a, are any r integers. Show that there is exactly
one integer c for which
c E ai (mod mi).One way to prove this is to use induction on r, building on Exercise- However, another proof can be devised along the following lines:
(a) Any number which is divisible by all the numbers mj except
rni has the form timlmz ~1. riti... m, (where the hat indicates
a deleted entry).
(b) ti can be chosen in such a way that the number in (a) is con-
gruent to 1 modulo rni (see Exercise 1.6.6). Thus, we can find
an integer ci for which
ci~O(modmj) when jfiCi E 1 (mod mi).