SECTION 2.1 Elementary Number Theory 73
m ≡ 7(mod 30)
m ≡ 4(mod 19).In this case, 7· 30 − 11 ·19 = 1 and so 3· 7 · 30 − 3 · 11 ·19 = 3 = 7− 4
which tells us to setm = 7− 3 · 7 ·30 = 4− 3 · 11 ·19 =−623. Any
other solution will be congruent to -623 modulo 30·19 = 570; apply
the division algorithm
−623 = 2·570 + 517.
It follows, therefore, that the solution we seek ism= 517.
We conclude this section with a simple corollary to the Chinese Re-
mainder Theorem; see Exercise 16c on page 63.
Corollary to Chinese Remainder Theorem. Let m andn be
relatively prime positive integers, Thenφ(mn) =φ(m)φ(n).
Proof. Leta, b be positive integers with 1≤a < m, 1 ≤b < n, and
gcd(a,m) = gcd(b,n) = 1. By the Chinese Remainder Theorem, there
is a unique integerk, with 1 ≤ k < mn satisfyingkm = a, kn = b.
Clearly gcd(k,mn) = 1. Conversely, if the positive integer k is given
with 1≤k < mn, and gcd(k,mn) = 1, then settinga =km, b=kn
produces integers satisfying 1 ≤ a < m, 1 ≤ b < n and such that
gcd(a,m) = gcd(b,n) = 1.
Exercises
- Letn be a positive integer and assume thata 1 ≡b 1 (modn) and
thata 2 ≡b 2 (modn).Show thata 1 +b 1 ≡a 2 +b 2 (modn) and that
a 1 b 1 ≡a 2 b 2 (modn). - Compute the least positive integernsuch thatn≡ 12 , 245 ,367(mod 11).
(Hint: this isveryeasy! Don’t try a direct approach.) - Compute the least positive integernsuch thatn≡ 12 , 245 ,367(mod 9).
- Find the least positive integer solution of the congruences