Colloquium Mathematicum

Show description

Pr ) − (p1 q2 . . qs ) = p1 (p2 . . pr − q2 . . qs ), (3) n = (q1 q2 . . qs ) − (p1 q2 . . qs ) = (q1 − p1 )(q2 . . qs ). (4) Since p1 < q1 , it follows from (4) that n is a positive integer, which is smaller than n. Hence the prime decomposition for n must be unique and, apart from the order of the factors, (3) and (4) coincide. From (3) we learn that p1 is a factor of n and must appear as a factor in decomposition (4). Since p1 < q1 ≤ qi , we see that p1 = qi , i = 2, 3, . . , s. , q1 − p1 = p1 m or q1 = p1 (m + 1), which is impossible as q1 is prime and q1 = p1 .

Part 1 follows from equation (4), parts 2 and 3 follow from part 1, and part 4 follows from Theorem 4. Theorem 5 (The Chinese remainder theorem). Let a and b be two relatively prime numbers, 0 ≤ r < a and 0 ≤ s < b. , N has remainder r on dividing by a and remainder s on dividing by b. 5 Proof. Let us prove first, that there exists at most one integer N with the conditions required. Assume, on the contrary, that for two integers N1 and N2 we have 0 ≤ N1 < ab, 0 ≤ N2 < ab and r = N1 (mod a) = N2 (mod a) and s = N1 (mod b) = N2 (mod b).

Now the number N1 = N −r = d1 + d2 b + d3 b2 + · · · + dn bn−1 = e1 + e2 b + e3 b2 + · · · + en bn−1 b has two different representations which contradicts the inductive assumption, since we have assumed the truth of the result for all N1 < N. Corollary 1. We use the notation N = (dn dn−1 . . d1 d0 )(b) (3) to express (2). The digits di can be found by the repeated application of the division algorithm as follows: N = q1 b + d0 , q1 = q2 b + d1 , .. qn = 0 · b + dn (0 ≤ d0 < b) (0 ≤ d1 < b) (0 ≤ dn < b) For example, the positional system with base 5 employ the digits 0, 1, 2, 3, 4 and we can write 1998(10) = 3 · 54 + 0 · 53 + 4 · 52 + 4 · 5 + 3 = 30443(5) .